Квадратичные сортировки

Сортировки выбором, вставками и пузырьком — три простейшие сортировки. Все работают за $O(N^2)$ и $O(1)$ дополнительной памяти.

Зачем нужно

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

Как работает

Во всех трёх for i = 0 ... N означает полуинтервал $[0,N)$, а swap — обмен двух элементов через временную переменную.

Выбором (Selection Sort)

Первые $i$ позиций уже заняты $i$ наименьшими элементами по порядку. В остатке ищем минимум и ставим его на позицию $i$.

for i = 0 ... N
    for j = i ... N
        если arr[i] > arr[j]
            swap(arr[i], arr[j])

Неустойчива: $[\dot{2},\ddot{2},1]\to [1,\ddot{2},\dot{2}]$ — обмен через весь массив перебрасывает $\dot{2}$ через $\ddot{2}$.

Вставками (Insertion Sort)

Левая часть отсортирована. Очередной элемент «проваливается» влево, пока левый сосед больше его.

for i = 0 ... N
    j = i + 1
    while (j > 0 и arr[j] < arr[j−1])
        swap(arr[j], arr[j−1])
        j = j − 1

Так на доске — с выходом за массив

При $i=N-1$ получается j = N, и while читает arr[N]. Внешний цикл должен идти до N − 1. Подробно — в конспекте L03.

Устойчива: обмен только при строгом <, через равный элемент не перепрыгивают.

Пузырьком (Bubble Sort)

Проход по соседним парам «всплывает» максимум вправо. После $i+1$ проходов последние $i+1$ позиций на месте.

for i = 0 ... N
    for j = 0 ... N−i−1
        если arr[j] > arr[j+1]
            swap(arr[j], arr[j+1])

Устойчива: меняются только соседи и только при строгом >.

Сводка

	$T(N)$	$M(N)$	Устойчива
Выбором	$O(N^2)$	$O(1)$	нет
Вставками	$O(N^2)$	$O(1)$	да
Пузырьком	$O(N^2)$	$O(1)$	да

Не из лекции: инварианты

• Выбор: перед шагом $i$ в arr[0..i) лежат $i$ наименьших элементов по порядку. Внутренний цикл сохраняет «в arr[i] минимум просмотренного».
• Вставки: перед шагом $i$ отсортирован префикс arr[0..i]. Вставка останавливается, когда слева не больше, а справа — то, через что элемент прошёл, всё больше его.
• Пузырёк: во время прохода в arr[j+1] лежит максимум arr[0..j+1]; после прохода $i$ последние $i+1$ позиций — наибольшие элементы по порядку.

Полные доказательства — в конспекте L03.

Не из лекции: сравнения и инверсии

Инверсия (inversion) — пара позиций $p<q$ с arr[p] > arr[q]. Обмен соседей, стоящих не по порядку, убирает ровно одну инверсию. Поэтому у вставок и пузырька обменов ровно столько, сколько инверсий, — от 0 до $\frac{N(N-1)}{2}$.

	Сравнений
Выбором	$\frac{N(N+1)}{2}$ на любом входе
Вставками	от $N-1$ (отсортирован) до $\approx \frac{N(N-1)}{2}$ (по убыванию)
Пузырьком	$\frac{N(N-1)}{2}$ на любом входе

Прогон на $N=1000$: выбор — 500 500 сравнений; вставки — 999 на отсортированном массиве и 499 500 на обратном; пузырёк — 499 500. Вставки — единственная из трёх, которая на почти отсортированном массиве работает почти линейно.

Тонкости

• Сортировка выбором на доске делает swap при каждом найденном меньшем элементе. Классический вариант запоминает индекс минимума и делает один обмен за шаг. Оценка та же, неустойчивы оба.
• Устойчивость вставок и пузырька держится на строгом сравнении. С ≤ (или ≥) они остаются правильными, но перестают быть устойчивыми.
• У пузырька последний проход пустой.

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

• Выход за границу: arr[j+1] при j = N − 1 в пузырьке или arr[N] во вставках с доски.
• swap без временной переменной: после a = b старое значение a потеряно.
• Считать, что раз у всех трёх $O(N^2)$, они одинаково быстры. На почти отсортированных данных вставки работают почти линейно, а выбор и пузырёк — нет.

Углубление — АиСД L04

Лекция начинается с итога: у всех трёх $T(N)=O(N^2)$, и при $N\sim 10^6$ это $10^{12}$ операций — при $10^8$ операций в секунду около $10^4$ секунд, почти три часа. Это повод для сортировки слиянием за $O(N\log N)$ — на том же входе около 0,2 секунды.