Отсортировать данные приходится постоянно: имена по алфавиту, товары по цене, события по времени. К тому же сортировка — обязательный подготовительный шаг для быстрого двоичного поиска, который работает только на упорядоченных данных. Начнём с трёх простейших алгоритмов. Они не самые быстрые, но на них удобно понять, как сортировка устроена вообще и как алгоритмы сравнивают между собой. Быстрые методы разберём позже.
Две операции, из которых всё собрано
Представьте, что нужно построить людей в шеренге по росту. Человек видит всех сразу и переставляет их «на глаз». Программа так не умеет: она сравнивает только двух за раз. Поэтому любая сортировка складывается из двух повторяющихся действий:
- сравнить два элемента;
- поменять их местами (или скопировать один).
Все три алгоритма ниже делают именно это — различие лишь в том, как они выбирают, кого с кем сравнивать и переставлять.
Пузырьковая сортировка
Самый простой (и самый медленный) метод. Идём слева направо и сравниваем соседние пары: если левый больше правого — меняем их местами. Дойдя до конца, мы «протолкнули» самый большой элемент в правый край — он всплыл, как пузырёк. Потом повторяем проход, но уже до предпоследней позиции (последняя уже на месте), и так далее.
void bubbleSort(long[] a) {
for (int out = a.length - 1; out > 0; out--)
for (int in = 0; in < out; in++)
if (a[in] > a[in + 1])
swap(a, in, in + 1);
}
Внешний цикл отмечает границу «уже отсортированного хвоста» справа, внутренний гоняет пары к этой границе. Каждый проход ставит на место один элемент. Понятно и наглядно, но медленно: сравнений примерно N², и перестановок много.
Сортировка выбором
Здесь мы уменьшаем число перестановок. Идея: за один проход находим минимальный элемент среди ещё не отсортированных и ставим его на первое свободное место слева. Потом ищем минимум среди оставшихся и ставим на второе место, и так далее.
Сравнений столько же, сколько у пузырька, — около N². Но перестановка всего одна на проход: нашли минимум — переставили его один раз, а не гоняли пары туда-сюда. Всего перестановок порядка N вместо N². Если перестановка дорогая (например, переставляются большие объекты), это заметный выигрыш.
Сортировка вставками
Обычно лучший из трёх простых методов. Аналогия — как раскладывают карты в руке. Слева держим уже упорядоченную часть. Берём очередной элемент справа и вставляем его на нужное место в левой части, сдвигая большие элементы вправо, чтобы освободить ему щель.
Сравнений в среднем примерно вдвое меньше, чем у пузырька (около N²/4), потому что при вставке мы сдвигаемся влево только до нужного места, а не по всей длине. Но у сортировки вставками есть особый козырь: на почти упорядоченных данных она работает почти за линейное время O(N) — если элемент уже стоит правильно, вставка не двигает ничего. Именно поэтому её используют как составную часть более сложных алгоритмов — например, для маленьких кусочков внутри быстрой сортировки.
Все три — O(N²)
Несмотря на различия, у всех трёх методов одинаковый порядок роста — O(N²) (квадратичное время): удвоили объём данных — учетверили работу. Это терпимо на десятках и сотнях элементов, но на миллионе O(N²) — это триллион операций, что уже неприемлемо. Разница между тремя методами — в константах и числе перестановок, а не в порядке роста:
| Метод | Сравнения | Перестановки | Особенность |
|---|---|---|---|
| Пузырёк | ~N² | до ~N² | простейший, но медленный |
| Выбор | ~N² | ~N | мало перестановок |
| Вставки | ~N²/4 | ~N²/4 | быстра на почти упорядоченных данных |
Практический вывод: из простых методов по умолчанию берут сортировку вставками — она быстрее пузырька и отлично ведёт себя, когда данные уже почти в порядке. Но для больших массивов ни один из трёх не годится: нужны алгоритмы уровня O(N·log N).
Устойчивость
Ещё одно свойство, важное на практике, — устойчивость (stability). Сортировка устойчива, если элементы с одинаковым ключом сохраняют исходный взаимный порядок. Это нужно, когда сортируют по нескольким полям по очереди: сначала по имени, потом по фамилии — и хочется, чтобы люди с одинаковой фамилией остались в порядке по имени. Пузырьковая сортировка и сортировка вставками устойчивы; сортировка выбором в наивном виде — нет, потому что дальняя перестановка может обогнать равный элемент.
Коротко
- Любая сортировка — это повторяющиеся сравнение и перестановка двух элементов.
- Пузырёк гоняет соседние пары, самый большой всплывает в конец; просто, но медленно.
- Выбор ищет минимум и ставит в начало; столько же сравнений, но мало перестановок.
- Вставки держат упорядоченную часть слева и вставляют туда следующий элемент; обычно лучший из трёх, особенно на почти отсортированных данных (там близко к O(N)).
- Все три — O(N²): годятся для малых объёмов, но не для больших. Устойчивость сохраняет порядок равных элементов — важна при сортировке по нескольким полям.
Дальше — стеки и очереди: структуры-инструменты, где доступ к элементам намеренно ограничен, чтобы упростить и ускорить типовые задачи.