Сортировка — это перестановка элементов массива или списка в заданном порядке: по возрастанию, по убыванию или по произвольному ключу. Задача одна, а способов ее решить много, и различаются они не результатом, а тем, как быстро работают и сколько памяти требуют. Ниже разберу пять базовых алгоритмов — пузырьком, вставками, выбором, быструю и слиянием: идею каждого, сложность в O-нотации и устойчивость. Прогоним один из них руками и кодом на Python, а в конце будет таблица сравнения и правило выбора.
Содержание
Три свойства, по которым сравнивают алгоритмы
Прежде чем сравнивать, разведу три понятия, которые часто путают.
Временная сложность O() — как растет число операций при увеличении размера массива n. O(n^2) означает: удвоили массив — работы стало вчетверо больше. O(n log n) растет намного медленнее. У одного алгоритма сложность может отличаться в лучшем, среднем и худшем случае.
Память (in-place или нет) — сколько дополнительного места нужно сверх самого массива. Алгоритм, сортирующий «на месте», тратит O(1) лишней памяти; сортировка слиянием требует O(n).
Устойчивость (стабильность) — сохраняет ли алгоритм относительный порядок элементов с одинаковым ключом. Если два человека с одинаковым возрастом шли в списке в порядке «Анна, потом Борис», устойчивая сортировка по возрасту оставит их в том же порядке. Свойство важно при сортировке по нескольким полям подряд.
Пузырьковая сортировка: прогон руками
Идея простая: идем по массиву и сравниваем каждую пару соседних элементов. Если левый больше правого — меняем их местами. За один проход самый большой элемент «всплывает» в конец. Повторяем проходы, пока не останется обменов.
Прогоним на массиве [5, 1, 4, 2, 8]. Каждый проход сравнивает соседние пары слева направо.
Проход 1: 5>1 меняем -> [1,5,4,2,8]; 5>4 меняем -> [1,4,5,2,8]; 5>2 меняем -> [1,4,2,5,8]; 5<8 не трогаем. Итог прохода: [1,4,2,5,8], число 8 встало на место.
Проход 2: 1<4 нет; 4>2 меняем -> [1,2,4,5,8]; 4<5 нет. Итог: [1,2,4,5,8].
Проход 3: ни одной перестановки — значит массив уже отсортирован, дальше идти незачем. Ранний выход по флагу «был ли обмен» — типичная оптимизация пузырька.
Теперь тот же алгоритм кодом. Флаг swapped дает ранний выход, а range(n - 1 - i) не проверяет уже отсортированный хвост.
def bubble_sort(a):
a = a[:] # копия, чтобы не портить исходный список
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i): # хвост из i элементов уже на месте
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
print(f"после прохода {i + 1}: {a}")
if not swapped: # проход без обменов - массив отсортирован
print("обменов не было - массив отсортирован, выходим")
break
return a
data = [5, 1, 4, 2, 8]
print("исходный:", data)
print("результат:", bubble_sort(data))Фактический вывод совпадает с ручным прогоном:
исходный: [5, 1, 4, 2, 8]
после прохода 1: [1, 4, 2, 5, 8]
после прохода 2: [1, 2, 4, 5, 8]
после прохода 3: [1, 2, 4, 5, 8]
обменов не было - массив отсортирован, выходим
результат: [1, 2, 4, 5, 8]
Пузырек прост и устойчив, но медленный: в среднем и худшем случае O(n^2). На практике его почти не применяют, зато он нагляден и отлично показывает саму механику перестановок.
Вставками и выбором: две другие простые сортировки
Сортировка вставками строит отсортированную часть слева, беря по одному элементу и вставляя его на нужное место среди уже упорядоченных — как раскладывают карты в руке. В худшем и среднем случае это O(n^2), но на почти отсортированных данных близка к O(n), поэтому годится для небольших и «доупорядоченных» массивов. Устойчива, работает на месте.
Сортировка выбором на каждом шаге находит минимум в неотсортированной части и ставит его в начало. Число сравнений одинаково всегда, поэтому сложность O(n^2) во всех случаях — и в лучшем тоже. Перестановок она делает мало (по одной за проход), но в базовой реализации неустойчива: обмен минимума с текущей позицией может «перепрыгнуть» равный элемент.
Все три простые сортировки — пузырьком, вставками, выбором — работают на месте с O(1) дополнительной памяти. Их потолок O(n^2) делает их непригодными для больших массивов, но на десятках элементов разница незаметна, а код короткий.
Быстрая и слиянием: сортировки за O(n log n)
Быстрая сортировка (quicksort) выбирает опорный элемент (pivot) и разбивает массив на две части: меньше опорного и больше. Затем рекурсивно сортирует каждую часть. В среднем это O(n log n) и на практике одна из самых быстрых. Но при неудачном выборе опорного (например, всегда крайний элемент на уже отсортированных данных) сложность вырождается до O(n^2). Базовая реализация неустойчива; дополнительная память — O(log n) на стек рекурсии.
Сортировка слиянием (merge sort) делит массив пополам, рекурсивно сортирует половины и сливает их в один упорядоченный список, каждый раз забирая меньший из двух текущих элементов. Ее сложность O(n log n) гарантированно во всех случаях, и она устойчива. Плата — O(n) дополнительной памяти под слияние.
Вот ядро слияния и сортировки на Python:
def merge_sort(a):
if len(a) <= 1: # база рекурсии: 0 или 1 элемент уже отсортированы
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= сохраняет порядок равных -> устойчивость
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
res.extend(left[i:]); res.extend(right[j:]) # добавляем остаток
return res
print(merge_sort([5, 1, 4, 2, 8])) # -> [1, 2, 4, 5, 8]Именно на идее слияния и вставок построен Timsort — гибридный алгоритм, который стоит за встроенными sorted() и list.sort() в Python. Он устойчив и работает за O(n log n), поэтому в реальном коде почти всегда берут встроенную сортировку, а ручные реализации нужны для учебы и нестандартных случаев.
Таблица сравнения
| Алгоритм | Лучший | Средний | Худший | Память | Устойчивость |
|---|---|---|---|---|---|
| Пузырьком | O(n) | O(n^2) | O(n^2) | O(1) | да |
| Вставками | O(n) | O(n^2) | O(n^2) | O(1) | да |
| Выбором | O(n^2) | O(n^2) | O(n^2) | O(1) | нет |
| Быстрая | O(n log n) | O(n log n) | O(n^2) | O(log n) | нет |
| Слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | да |
O(n) в лучшем случае у пузырька и вставок достигается только с оптимизацией «ранний выход» на почти отсортированных данных. Устойчивость указана для базовых реализаций — и быструю, и выбор можно сделать устойчивыми ценой усложнения или лишней памяти.
Когда какой выбирать
- Учеба, наглядность, крошечные массивы — пузырьком или вставками: код в несколько строк, легко проследить механику.
- Почти отсортированные данные — вставками: на них она близка к O(n).
- Нужна гарантия O(n log n) и устойчивость (например, сортировка по нескольким полям) — слиянием, если не жалко O(n) памяти.
- Быстро и в среднем, память ограничена — быстрая: на случайных данных она обычно обгоняет слияние за счет работы на месте.
- Реальный проект — встроенная
sorted()/list.sort()(Timsort): устойчивая, O(n log n), оптимизированная. Свою сортировку писать стоит, только если есть особые требования.
Выводы
- Алгоритмы сортировки дают одинаковый результат, но различаются по скорости, памяти и устойчивости — по этим трем свойствам их и выбирают.
- Простые сортировки (пузырьком, вставками, выбором) работают на месте за O(n^2) и подходят для учебы и малых массивов.
- Быстрая и слиянием дают O(n log n): быстрая экономит память, но в худшем случае деградирует до O(n^2); слияние стабильно быстрое и устойчивое, но требует O(n) памяти.
- Устойчивость важна при сортировке по нескольким ключам подряд; выбором и базовый quicksort неустойчивы.
- В рабочем коде почти всегда берут встроенную
sorted()/list.sort()(Timsort) — устойчивую и за O(n log n).
Где применяется / связь с практикой
Сортировка — это основа множества практических задач: поиск (бинарный поиск работает только на отсортированных данных), устранение дубликатов, группировка, ранжирование выдачи. Понимание сложности O() и устойчивости помогает не только выбирать готовую функцию, но и оценивать, почему одна операция на больших данных занимает секунды, а другая — минуты.
Освойте тему на практике
Систематически разобрать алгоритмы, их сложность и применение можно на курсе Алгоритмы и структуры данных: там сортировки идут в связке со структурами данных, на которых они работают. Посмотреть формат и темы вживую можно на открытых уроках Otus — это бесплатные занятия с разбором конкретных задач.
Смежные темы: Пузырьковая сортировка на Python и C, Сортировка массива на PHP.
FAQ
Какая сортировка самая быстрая?
Универсального ответа нет: на случайных данных обычно быстрее quicksort, на почти отсортированных — вставки, а гарантированный O(n log n) без деградации дает слияние. В большинстве задач оптимальна встроенная Timsort.
Зачем изучать пузырек, если его не применяют?
Он нагляднее всего показывает механику сравнений и перестановок и служит отправной точкой для понимания более сложных алгоритмов. В продакшене его действительно не используют.
Что значит «сортировка на месте»?
Алгоритм переставляет элементы внутри самого массива и тратит на это O(1) дополнительной памяти. Сортировка слиянием так не умеет — ей нужен отдельный буфер размером O(n).
