Алгоритмы сортировки: пузырьком, слиянием, быстрая и другие

Короткий ответ

Сортировка — это упорядочивание элементов по ключу. Алгоритмы различаются тремя свойствами:

• Временная сложность — как растёт время работы с ростом числа элементов n.
• Память — нужен ли дополнительный массив или всё делается на месте (in-place).
• Устойчивость (stability) — сохраняют ли равные элементы исходный порядок.

Для учёбы полезно понимать каждый алгоритм. Для работы почти всегда достаточно встроенной функции sort вашего языка.

Сортировка пузырьком

Проходим по массиву и меняем местами соседние элементы, если они стоят неправильно. После каждого прохода самый большой элемент «всплывает» в конец.

1. Сравнить a[0] и a[1], при необходимости поменять.
2. Сравнить a[1] и a[2] и так до конца.
3. Повторять проходы, пока за проход не было ни одного обмена.

Сложность — O(n²), устойчива. На практике почти не используется: это учебный пример.

Сортировка вставками

Берём элементы по одному и вставляем на правильное место в уже отсортированной левой части — как карты в руке.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

В худшем случае O(n²), но на почти отсортированных данных близка к O(n). Устойчива и работает на месте. Поэтому её используют внутри гибридных алгоритмов для маленьких кусков.

Сортировка выбором

На каждом шаге ищем минимум в неотсортированной части и ставим его в начало. Всегда O(n²) сравнений, но мало обменов. В обычной реализации неустойчива.

Сортировка слиянием (merge sort)

Принцип «разделяй и властвуй»:

1. Делим массив пополам.
2. Рекурсивно сортируем каждую половину.
3. Сливаем две отсортированные половины в одну, сравнивая их первые элементы.

Всегда O(n log n), устойчива. Минус — нужна дополнительная память O(n). Хорошо подходит для связных списков и внешней сортировки больших файлов.

Быстрая сортировка (quicksort)

1. Выбираем опорный элемент (pivot).
2. Переставляем элементы: меньшие — влево, большие — вправо.
3. Рекурсивно сортируем обе части.

В среднем O(n log n) и очень быстро на практике благодаря работе с памятью. Худший случай — O(n²), если pivot постоянно оказывается крайним (например, на уже отсортированном массиве при выборе первого элемента). Лечится случайным pivot или медианой из трёх. Неустойчива.

Пирамидальная сортировка (heapsort)

Строим из массива двоичную кучу (heap), затем многократно извлекаем максимум. Гарантированно O(n log n), работает на месте, но неустойчива и на практике обычно медленнее quicksort.

Сравнение

Что используют встроенные сортировки

Стандартные библиотеки применяют гибридные алгоритмы:

• Timsort — слияние плюс вставки, умеет находить уже упорядоченные участки. Используется в Python и для сортировки объектов в Java. Устойчив.
• Introsort — начинает как quicksort, при слишком глубокой рекурсии переключается на heapsort, а маленькие куски досортировывает вставками. Типичен для std::sort в C++.
• В JavaScript спецификация требует, чтобы Array.prototype.sort была устойчивой; движки обычно используют Timsort.

Частые ошибки

• Писать свою сортировку в продакшене — встроенная почти всегда быстрее и протестирована.
• Забывать про устойчивость при сортировке по нескольким полям.
• Неверный компаратор: в JavaScript [10, 9, 1].sort() сравнивает элементы как строки. Нужно sort((a, b) => a - b).