Сортировки выбором, вставками и пузырьком с визуализацией состояния

Бинарный поиск требует отсортированного входа. Получить такой вход можно разными способами: сортировки выбором, вставками и пузырьком имеют один квадратичный худший случай, но по-разному используют сравнения, обмены и структуру исходного массива.

Лента состояний массива как инструмент трассировки

Когда алгоритм сортировки работает, он последовательно меняет массив. Чтобы понять, что именно происходит на каждом шаге — сколько сравнений было сделано, что переставилось, какая часть уже готова — удобно зафиксировать каждое промежуточное состояние отдельной строкой. Такую запись называют лентой состояний.

Каждая строка ленты соответствует одному завершённому проходу или шагу алгоритма. В строке записывается весь массив целиком. Дополнительно маркируются:

• активные позиции — элементы, которые на этом шаге сравнивались или переставлялись (обычно подчёркиваются или выделяются скобками);
• граница отсортированной части — разделитель между уже готовым префиксом (или суффиксом) и остатком.

Посмотрим на простой пример — массив [5, 3, 1, 4]. Лента для первого прохода некоего алгоритма, который переставил 1 и 5:

Шаг 0 (исходный):  [ 5  3  1  4 ]
Шаг 1 (после):     [ 1  3  5  4 ]   ^ граница после позиции 0
                      ─────────
                      активны: 0, 2

По этой ленте сразу видно: был один обмен между позициями 0 и 2. Граница отсортированной части сдвинулась на одну позицию вправо.

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

Ещё важнее: лента позволяет проверять инвариант алгоритма — утверждение о том, что гарантированно выполнено после каждого шага. Если инвариант нарушен в какой-то строке, значит, в реализации ошибка. Это превращает ленту из просто наглядного пособия в инструмент отладки.

Формат ленты не стандартизирован жёстко — в разных источниках используют скобки, стрелки или цвет. Главное, чтобы из записи однозначно читались активные позиции, граница готовой части и уровень детализации: отдельная операция или целый проход.

Сортировка выбором: инвариант, трассировка, сложность

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

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

Прогоним на [5, 3, 1, 4, 2] и запишем ленту — каждая строка после завершения итерации i, в скобках помечены элементы, участвовавшие в обмене:

i=0: [ (1)  3  (5)  4  2 ]  | min найден на позиции 2, обмен 0↔2
      ─────────────────────
      готово: [1]
i=1: [  1  (2)  5  4  (3) ]  | min найден на позиции 4, обмен 1↔4
      ─────────────────────
      готово: [1, 2]
i=2: [  1   2  (3)  4  (5) ]  | min найден на позиции 4, обмен 2↔4
      ─────────────────────
      готово: [1, 2, 3]
i=3: [  1   2   3  (4)  5  ]  | min уже на месте, обмена нет
      ─────────────────────
      готово: [1, 2, 3, 4, 5]

Инвариант: после завершения итерации i подмассив arr[0..i] содержит i+1 наименьших элементов в отсортированном порядке, и они уже никогда не сдвинутся.

Число сравнений считается точно. На итерации i внутренний цикл делает n-1-i сравнений. Суммируем по всем итерациям:

(n-1) + (n-2) + ... + 1 = n(n-1)/2

Это всегда n(n-1)/2 — независимо от того, отсортирован массив или нет, в прямом порядке или в обратном. Выбором не умеет «заметить», что работа уже сделана.

Число обменов — не более n-1: одна операция swap на каждую итерацию, и только если min_idx != i. На уже отсортированном массиве обменов ноль.

Теперь про нестабильность. Посмотрим на массив [(2a), (2b), 1], где 2a и 2b — два элемента со значением 2, в исходном порядке a перед b. На первой итерации минимум — 1 на позиции 2. Алгоритм меняет (2a) и 1 местами: результат [1, (2b), (2a)]. Элемент (2a) перепрыгнул через (2b) — их относительный порядок нарушен. Именно «дальний» обмен (arr[i] меняется с arr[min_idx], а между ними могут стоять равные элементы) и делает сортировку выбором нестабильной.

Итого: минимальное число операций с памятью (O(1) дополнительно), гарантированно мало обменов, но ровно n(n-1)/2 сравнений при любом входе — и нет стабильности.

Сортировка вставками: сдвиги, инверсии и поведение на почти отсортированных данных

Вставками работает иначе: мы не ищем минимум во всём остатке, а берём следующий элемент и находим ему место в уже готовом префиксе, сдвигая всё большее вправо.

def insertion_sort(arr: list) -> list:
    a = arr
    n = len(a)
    for i in range(1, n):
        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

Лента для [4, 2, 5, 1, 3]:

i=1: key=2  [ (4→) (2)  5  1  3 ]  сдвигов: 1  →  [ 2  4  5  1  3 ]
i=2: key=5  [  2   4  (5) 1  3 ]  сдвигов: 0  →  [ 2  4  5  1  3 ]
i=3: key=1  [ (2→)(4→)(5→)(1) 3 ]  сдвигов: 3  →  [ 1  2  4  5  3 ]
i=4: key=3  [  1 (2→)(4→)(3) 5 ]  сдвигов: 2  →  [ 1  2  3  4  5 ]

Инвариант: в начале итерации i подмассив arr[0..i-1] отсортирован.

Теперь ключевой механизм. Каждый сдвиг a[j+1] = a[j] устраняет ровно одну инверсию — пару (j, i) такую, что j < i и a[j] > a[i] (до вставки). Потому что именно этот a[j] стоит левее key и больше него. Значит:

Суммарное число сдвигов за весь алгоритм = суммарное число инверсий I в исходном массиве.

Отсюда время работы — Θ(n + I): n итераций внешнего цикла плюс I сдвигов.

Крайние случаи:

• Отсортированный массив: инверсий нет, I = 0, время Θ(n). Внутренний while не выполняется ни разу.
• Обратно отсортированный: каждая пара — инверсия, I = n(n-1)/2, время Θ(n²).

Теперь «почти отсортированный» — это не просто красивые слова. Сопоставим каждому элементу его позицию в стабильном отсортированном порядке. Если модуль смещения каждого элемента не превосходит k, сумма модулей смещений не превосходит n·k. Число инверсий I не больше этой суммы, поэтому I ≤ n·k, а время работы — O(n·(k+1)). При фиксированном k это O(n) — линейное время.

Пример: данные датчика, где показания почти в порядке, но иногда приходят с задержкой на 1–2 позиции. Вставками разберётся с таким массивом практически за линейное время.

Стабильность: в условии while стоит строгое a[j] > key, а не >=. Это означает, что равный элемент остановит сдвиг — key встанет сразу после него. Относительный порядок равных элементов сохраняется.

Дополнительная память — O(1): только переменная key и индекс j.

Сортировка пузырьком: всплытие максимума, early exit, стабильность

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

def bubble_sort(arr: list) -> list:
    a = arr
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:   # early exit
            break
    return a

Лента для [3, 1, 4, 2]:

Проход i=0 (j: 0..2):
  j=0: (3↔1) → [ 1  3  4  2 ]
  j=1: (3,4) без обмена → [ 1  3  4  2 ]
  j=2: (4↔2) → [ 1  3  2  4 ]
  после прохода: [ 1  3  2 | 4 ]  ← 4 на финальной позиции

Проход i=1 (j: 0..1):
  j=0: (1,3) без обмена → [ 1  3  2  4 ]
  j=1: (3↔2) → [ 1  2  3  4 ]
  после прохода: [ 1  2 | 3  4 ]

Проход i=2 (j: 0..0):
  j=0: (1,2) без обмена, swapped=False → early exit
  после прохода: [ 1  2  3  4 ]  ✓

Инвариант: перед проходом i суффикс arr[n-i..n-1] содержит i наибольших элементов на финальных позициях. После прохода готовый суффикс расширяется: arr[n-i-1..n-1] содержит уже i+1 наибольших элементов.

Почему наибольший «всплывает»? Он не меньше каждого следующего соседа: если сосед меньше, элементы меняются местами и максимум сдвигается правее; с равным соседом обмен не нужен. Так максимум достигает границы неотсортированной части.

Без флага swapped алгоритм всегда делает (n-1) + (n-2) + ... + 1 = n(n-1)/2 сравнений — то же самое число, что и выбором, но теперь ещё и обменов может быть O(n²) (каждый обмен — между соседями, и для того чтобы переместить элемент на k позиций, нужно k обменов).

Флаг early exit меняет картину для лучшего случая: если за проход не было ни одного обмена, массив уже отсортирован, и можно остановиться. На уже отсортированном входе — ровно n-1 сравнений и 0 обменов, то есть Θ(n). Худший случай при этом остаётся Θ(n²) — флаг не помогает, если инверсии распределены по всему массиву.

Важно: пузырёк с early exit завершит работу сразу после первого «чистого» прохода, но не умеет детектировать, сколько инверсий осталось — в отличие от вставками он не устраняет все инверсии элемента за один шаг.

Стабильность: условие a[j] > a[j+1] — строгое. Равные соседи не переставляются, относительный порядок сохраняется. Пузырёк стабилен.

Сравнительный анализ трёх алгоритмов и критерии выбора

Три алгоритма удобно сравнить по четырём осям: сравнения, обмены, стабильность и зависимость от структуры входа.

Алгоритм	Сравнений	Обменов	Стабилен	Зависит от входа
Выбором	всегда n(n-1)/2	≤ n-1	нет	нет
Вставками	Θ(n + I)	— (сдвиги = I)	да	да
Пузырьком	n(n-1)/2 без оптимизации; Θ(n) на отсортированном с early exit	O(n²)	да	частично

Вставками подходит для почти упорядоченных данных. Число операций прямо пропорционально числу инверсий I, и если I = O(n), алгоритм работает за линейное время. Сортировка игральных карт в руке — классическая аналогия: новую карту вставляем на место, сдвигая несколько соседей, а не перекладываем всю руку каждый раз. Кроме того, вставками стабильна, что важно, когда нужно сохранить вторичный порядок при равных ключах.

Выбором стоит рассмотреть в редкой, но реальной ситуации: когда операция записи (обмена) дорогая, а чтение (сравнение) — дешёвое. Например, если данные лежат на медленной памяти с ограниченным числом перезаписей. Выбором гарантирует не более n-1 обменов при любом входе, тогда как вставками на обратно отсортированном массиве сделает Θ(n²) сдвигов (каждый сдвиг — запись). Платить за это приходится тем, что n(n-1)/2 сравнений выполняется всегда, и нестабильностью.

Пузырёк с early exit гарантирует Θ(n) на уже отсортированном входе — как и вставками. Разница в том, что вставками достигает Θ(n + I) в общем случае: она эффективно работает при любом малом I. Пузырёк же завершает работу только после прохода без обменов; если инверсии есть, но «размазаны» по массиву, он пройдёт столько раз, сколько нужно для всплытия всех максимумов — и это в общем случае не Θ(n + I), а хуже. Поэтому небольшой остаток инверсий сам по себе не гарантирует пузырьку время Θ(n + I).

Все три реализации работают in-place (O(1) дополнительной памяти), и у всех худший случай Θ(n²). Алгоритмы с другой структурой вычислений, например сортировка слиянием, достигают Θ(n log n) за счёт разбиения массива на подзадачи.