Зачем junior DE знать про O(n^2) сортировки

Можно задать резонный вопрос: зачем учить bubble sort в 2026 году, когда в Python есть sorted(), в Postgres есть ORDER BY, в Spark есть sort_values(), и все они работают за O(n log n)?

Три причины:

1. Понимание базовых концепций. Эти три простые сортировки — естественный мостик к более сложным. Bubble показывает идею «обменов». Insertion — основу Timsort, главной сортировки Python. Selection — паттерн «выбрать минимум, повторить» используется в heapsort и в priority queue.

2. Они применяются. В Timsort (Python sort) маленькие сегменты сортируются insertion-ом — это эффективнее merge для длин до 64. В quicksort на маленьких partition’ах часто переключаются на insertion. Если вы случайно реализуете «сортировку 10 элементов» через рекурсивный merge — это медленнее, чем простой insertion.

3. Cache-friendly и in-place. Все три сортировки используют O(1) дополнительной памяти и работают линейно в памяти, что важно для маленьких массивов.

Этот урок — про эти три сортировки, их особенности и когда insertion sort внезапно становится O(n).

Bubble sort: меняем соседей

Идея: проходим по массиву, на каждом шаге сравниваем соседей. Если предыдущий больше следующего — меняем местами. Один такой проход «всплывает» максимум один большой элемент в конец. Повторяем, пока не пройдёт без обменов.

def bubble_sort(arr: list[int]) -> None:
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break   # массив уже отсортирован

Шаги на [5, 1, 4, 2, 8]:

• проход 1: [1, 4, 2, 5, 8] (8 поднялся в конец).
• проход 2: [1, 2, 4, 5, 8] (5 на месте, 2 поднимается).
• проход 3: без обменов — стоп.

Сложность:

• worst case: O(n^2) — обратно отсортированный массив,
• average: O(n^2),
• best case: O(n) — уже отсортированный (с проверкой swapped).

Стабильность: да. Меняем местами только когда arr[j] > arr[j+1] — равные сохраняют относительный порядок.

Память: O(1) — in-place.

Bubble — самая медленная из трёх в среднем. На практике почти не используется.

Selection sort: ищем минимум

Идея: на шаге i найти минимум в части arr[i:], поменять местами с arr[i]. После n-1 шагов массив отсортирован.

def selection_sort(arr: list[int]) -> None:
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

Шаги на [5, 1, 4, 2, 8]:

• i=0: min в [5,1,4,2,8] — это 1, index 1. Меняем: [1, 5, 4, 2, 8].
• i=1: min в [5,4,2,8] — это 2, index 3. Меняем: [1, 2, 4, 5, 8].
• i=2: min — 4, уже на месте.
• i=3: min — 5, на месте.
• Готово.

Сложность:

• worst, average, best: O(n^2). Всегда. Даже на уже отсортированном — мы всё равно перебираем хвост, чтобы убедиться в минимуме.

Стабильность: нет. Перестановка с min_idx может «перепрыгнуть» через равные элементы. Пример: [2a, 1, 2b]. После i=0 min=1 (index 1), меняем: [1, 2a, 2b]. Тут ОК. Но в [3, 2, 3, 1]: i=0 min=1, меняем arr[0] и arr[3] — [1, 2, 3, 3]. Изначальный «3 первый» оказался после «3 третьего» — relative order для дублей нарушен.

Память: O(1) — in-place.

Главный плюс selection — минимум обменов. Всего n-1 обменов в любом случае. Это полезно, если перестановка дорогая (например, элементы — большие структуры в C-коде).

Insertion sort: вставляем в готовое

Идея: представляем, что левая часть массива уже отсортирована. Берём следующий элемент и вставляем его в правильное место в левой части (сдвигая большие вправо).

def insertion_sort(arr: list[int]) -> None:
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # сдвигаем все элементы > key вправо
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Шаги на [5, 1, 4, 2, 8]:

• i=1, key=1: 5>1, сдвигаем 5. Вставляем 1 в позицию 0. [1, 5, 4, 2, 8].
• i=2, key=4: 5>4, сдвигаем 5. 1<4, стоп. [1, 4, 5, 2, 8].
• i=3, key=2: 5>2, 4>2, 1<2. [1, 2, 4, 5, 8].
• i=4, key=8: 5<8, ничего не сдвигаем.
• Готово.

Сложность:

• worst case: O(n^2) — обратно отсортированный массив, каждый key проходит до начала.
• average: O(n^2).
• best case: O(n) — уже отсортированный или почти отсортированный массив. Внутренний while сразу не входит, потому что arr[j] <= key.

Стабильность: да. Сдвигаем arr[j] > key, при равенстве — не сдвигаем, значит key остаётся справа от равных предшественников.

Память: O(1).

Insertion sort на «почти отсортированном»

Это главная фишка insertion sort. Если массив почти отсортирован (каждый элемент стоит близко к своему правильному месту), insertion работает быстро. Формально: если каждый элемент находится не дальше чем на k позиций от своего места, insertion sort работает за O(n * k). Для k = константа это O(n).

Пример: массив [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]. Только последний элемент не на месте.

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
insertion_sort(arr)
# 10 итераций: 9 ничего не делают (key <= prev), последняя — сдвигает 10 элементов
# итого 19 операций, не 121 (как было бы у bubble)

Это сильный аргумент в пользу insertion в реальных данных. Реальные потоки данных (логи, события) часто почти отсортированы — приходят с небольшими задержками, и небольшая часть нужна для перестановки. Timsort использует это: разбивает массив на куски, сортирует insertion-ом до длины 32-64, потом сливает.

Сравнительная таблица

Когда O(n^2) приемлемо

Маленькие массивы. 10-50 элементов — sorting любым из трёх занимает микросекунды на современном железе. Накладные расходы более сложных сортировок (вызовы функций, дополнительная память) могут оказаться больше выигрыша от O(n log n).

Эмпирически: в Timsort переключаются на insertion при длине партиции <= 32. В Java Arrays.sort переключается при <= 7. В C++ std::sort — варьируется.

Для junior DE правило простое: если массив маленький (< 100 элементов), любая сортировка достаточно быстра. Используйте встроенный sorted() — он сам выберет оптимум. Свои реализации простых сортировок пишите только в учебных задачах или в очень специфических случаях.

Cache-friendly

Все три простые сортировки — cache-friendly. Они читают и пишут по соседним адресам массива, prefetcher и cache-line работают эффективно. На малых массивах это перевешивает асимптотику.

Сравните с merge sort: для слияния нужен дополнительный массив, переход между «оригинал» и «копия» — это два разных адреса. Cache misses чаще.

На массивах 32-64 элемента insertion sort на современном x86 обгоняет mergesort, который теоретически O(n log n). Это и есть причина гибридных алгоритмов (Timsort, Introsort).

DE-кейс: сортировка маленькой партиции

Допустим, вы пишете свой шафлер партиций для Spark-like системы. Каждая партиция — несколько десятков элементов, нужно их отсортировать перед merge. Какой алгоритм взять?

Ответ: использовать sorted() или встроенный Arrays.sort() — они написаны на C и оптимизированы. Никаких ручных insertion sort. Но знать, что внутри них для маленьких сегментов идёт insertion — полезно для понимания производительности.

DE-кейс: дедупликация почти отсортированных событий

Сценарий: у вас поток событий, каждое имеет timestamp. События приходят почти в порядке, но иногда переставляются на 1-2 позиции из-за сетевых задержек. Нужно отсортировать перед записью в Parquet.

Если использовать Python sorted() — Timsort сделает это очень быстро (внутри использует insertion для уже-почти-отсортированных runs). На 1М почти-отсортированных событий — десятки миллисекунд. На случайных — 200-500 мс.

Без Timsort, на чистом merge sort, разница была бы меньше — merge всегда n log n, без скидки за «почти отсортированность».

Урок 14.01 разбирает Timsort подробно — почему он использует это свойство.

Попробуй сам

import random
import time

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

# тест на случайных данных
random.seed(42)
arr_random = [random.randint(0, 1000) for _ in range(10000)]
arr_sorted = sorted(arr_random)
arr_almost = arr_sorted[:]
# делаем «почти отсортированный»: 5 пар обменов
for _ in range(5):
    i = random.randint(0, 9998)
    arr_almost[i], arr_almost[i+1] = arr_almost[i+1], arr_almost[i]

for name, arr in [("random", arr_random), ("sorted", arr_sorted), ("almost", arr_almost)]:
    a = arr[:]
    t = time.perf_counter()
    insertion_sort(a)
    elapsed = time.perf_counter() - t
    print(f"{name}: {elapsed*1000:.1f} ms")

Ожидаемое:

• random: 8-15 секунд (О(n^2) на 10к — это 10^8 операций),
• sorted: миллисекунды (O(n)),
• almost: тоже миллисекунды (O(n + swaps) — линейный плюс мелкие сдвиги).

Эта таблица очень важна для понимания, почему Timsort так быстр на реальных данных.

В следующем уроке — merge sort: O(n log n) гарантированно, классика divide-and-conquer.