Содержание
- Краткое резюме
- Задача сортировки: определение и требования
- Пузырьковая сортировка: базовый метод
- Сортировка вставками: идея и эффективность
- Итог
Краткое резюме
- Задача сортировки заключается в упорядочивании элементов по значению ключевого поля, которое должно подчиняться линейному порядку (меньше, больше, равно).
- Классические методы сортировки — пузырьковая и сортировка вставками — имеют квадратичную временную сложность в худшем случае.
- Пузырьковая сортировка последовательно сравнивает соседние элементы и «всплывает» самый крупный элемент на конец массива за каждый проход.
- Сортировка вставками строит отсортированный массив постепенно, вставляя каждый следующий элемент в правильную позицию внутри уже упорядоченной части.
Задача сортировки: определение и требования
Сортировка — это процесс перестановки элементов множества так, чтобы их ключевые поля образовали неубывающую последовательность. Ключевое поле — это критерий упорядочивания (например, дата создания заказа), при этом на нем должно существовать отношение линейного порядка — способность сравнивать значения между собой.
Иначе говоря, если у нас есть массив элементов, мы хотим переставить их так, чтобы каждое ключевое поле было не меньше предыдущего.
Пузырьковая сортировка: базовый метод
Пузырьковая сортировка — самый известный простейший способ сортировки, который часто изучают вначале. Его суть:
- На каждом проходе по массиву сравниваются соседние элементы.
- Если левый элемент больше правого, они меняются местами.
- После первого прохода самый большой элемент «всплывает» в конец.
- Процедуру повторяют примерно N раз (где N — размер массива), чтобы отсортировать все элементы.
В итоге пузырьковая сортировка имеет квадратичную сложность — ( O(n^2) ), поскольку использует вложенные циклы и в худшем случае приходится делать максимальное количество сравнений и перестановок.
«За один проход по массиву в худшем случае ставится на свое место только один элемент — наибольший.»
Можно немного улучшить алгоритм, например, используя флаг, который сообщает, были ли перестановки на последнем проходе. Если перестановок не было — значит массив уже отсортирован, и можно завершить работу раньше. Также можно отслеживать границу последней перестановки и игнорировать уже отсортированные элементы в следующих проходах. Но существенного улучшения в худшем случае это не дает.
Пример работы пузырьковой сортировки
В примере показан проход по массиву, где после сери х сравнений и перестановок самый большой элемент (93) оказывается в конце массива. Следующий проход переносит 77 ближе к концу и так далее, пока массив не станет полностью отсортирован.
Сортировка вставками: идея и эффективность
Сортировка вставками — это более эффективный среди простых методов способ. Его идея:
- Считать, что первые несколько элементов уже отсортированы.
- Далее новый элемент вставлять в правильную позицию внутри уже отсортированной части массива.
- Для вставки элемента нужно сдвигать вправо все элементы, большие нового.
Время одной вставки в худшем случае линейно — нужно сдвинуть все элементы. Поэтому общая сложность — также ( O(n^2) ).
«В худшем случае для вставки одного элемента необходимо сдвинуть все предыдущие — это заметно увеличивает время.»
Пример
Когда первые пять элементов отсортированы, мы рассматриваем шестой элемент (31). Для вставки 31 нужно подвинуть вправо элементы 93, 77 и 54, чтобы освободить под него подходящее место.
Итог
- Задача сортировки требует упорядочить элементы по ключевому полю с линейным сравнением.
- Пузырьковая сортировка — понятный, но неэффективный метод с квадратичной сложностью.
- Сортировка вставками — более «интеллектуальный» подход, постепенно расширяющий отсортированную часть, но также имеющий квадратичную сложность в худшем случае.
- Улучшения классических методов бывают, но не меняют фундаментальную сложность.
👌 Оба метода отлично подходят для учебных целей и понимания принципов сортировки, но на практике используются более сложные и эффективные алгоритмы.