Сортировки: от insertion sort до quick sort

Перед началом: сложность и измерения (модуль 1), срезы (модуль 2), бинарный поиск (модуль 10 — понадобится позже). Инструменты: Go 1.27, slices, sort, cmp. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Отчёт отсортировался и потерял порядок»

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

Технически всё было правильно: sort.Slice не обещает стабильность — порядок равных элементов может измениться. Для отчёта это была функциональность, а не деталь: равные суммы должны шли в исходном порядке. В модуле — сортировки изнутри: от insertion sort до partition quick sort, понятие стабильности и то, что именно делает slices.Sort в современном Go.

📖 Теория

8.1 Квадратичные сортировки: insertion, selection, bubble

O(n²) звучит как приговор, но у каждой из «детских» сортировок есть своя роль.

Insertion sort — вставка каждого элемента в уже отсортированный префикс сдвигом. Он адаптивен: на почти отсортированных данных делает почти n операций, а не n². Именно поэтому insertion sort живёт внутри промышленных сортировок как финишер для коротких подмассивов (пороговые «маленькие хвосты» — типовая оптимизация).

go
// insertion: на уже отсортированном срезе — один проход без сдвигов.
func insertionSort(a []int) int { // возвращает число сдвигов
	shifts := 0
	for i := 1; i < len(a); i++ {
		key, j := a[i], i-1
		for j >= 0 && a[j] > key {
			a[j+1] = a[j] // сдвиг большего вправо
			j--
			shifts++
		}
		a[j+1] = key
	}
	return shifts
}

Selection sort — на минимум обменов (n−1), но неадаптивен. Изредка нужен там, где обмен дорог (внешняя память), и никогда — на почти отсортированных данных.

Bubble sort — учебная: в реальном коде её роль нулевая, зато на ней удобно объяснять «почему n²». В продакшене не используйте.

8.2 Merge sort: стабильность как гарантия

Merge sort делит срез пополам, рекурсивно сортирует половины (модуль 7, рекурсия логарифмической глубины) и сливает: берёт меньший из голов двух отсортированных потоков.

go
func merge(a, b []int) []int {
	out := make([]int, 0, len(a)+len(b))
	for i, j := 0, 0; i < len(a) || j < len(b); {
		switch {
		case i == len(a):
			out = append(out, b[j]); j++
		case j == len(b):
			out = append(out, a[i]); i++
		case a[i] <= b[j]: // <= — вот она, стабильность: равные слева
			out = append(out, a[i]); i++
		default:
			out = append(out, b[j]); j++
		}
	}
	return out
}

Ключевые свойства: всегда Θ(n log n), стабильность (равные элементы приходят в исходном порядке) и O(n) дополнительной памяти. Последнее — причина, по которой в проде предпочитают in-place сортировки там, где память дорога.

8.3 Quick sort: partition и цена пивота

Quick sort выбирает опорный элемент (pivot) и разбивает массив: слева меньше, справа больше, затем рекурсивно сортирует части. Схема Lomuto:

go
func partition(a []int, lo, hi int) int {
	pivot := a[hi] // опорный — последний (для учебного примера)
	i := lo
	for j := lo; j < hi; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	a[i], a[hi] = a[hi], a[i]
	return i
}

Главная опасность — худший случай: уже отсортированный срез при «последний элемент как пивот» даёт разбиения 0/n−1 — и O(n²). Первый реальный инцидент с этим ловится на данных, которые часто уже отсортированы. Лечение — рандомизация пивота (случайный или median-of-three): вероятностная гарантия O(n log n) и in-place без дополнительной памяти. Стабильности quick sort не даёт никогда.

8.4 Сравнение сортировок

Практический вывод: теоретический лидер — merge, но на реальном железе quick выигрывает за счёт последовательного доступа к памяти. Поэтому промышленные сортировки — гибриды: quick + вставки на мелких отрезках

• heap fallback при плохой рекурсии.

8.5 Что на самом деле делает slices.Sort

Go-рантайм использует pdqsort — pattern-defeating quick sort: квази-quick с тремя добавками: insertion sort на коротких отрезках, heap sort как «страховка» против квадратичного вырождения, детектор паттернов (если разбиение подозрительно однобокое — пивот перемешивается).

go
slices.Sort(a)                       // int, string, float — быстрый путь
slices.SortFunc(users, func(x, y User) int {
	return cmp.Compare(x.Age, y.Age) // компаратор «меньше/равно/больше»
})
sort.Slice(a, less)                  // legacy: reflection, медленнее SortFunc
sort.SliceStable(a, less)            // стабильный вариант general-purpose

Правила выбора:

• отсортировать []T по встроенному порядку (числа, строки) — slices.Sort;
• свой компаратор — slices.SortFunc (не sort.Slice: reflection дорог);
• порядок равных важен — sort.SliceStable (инцидент модуля именно об этом);
• ключ дорогой (например, вычисляемый) — приём decorate-sort-undecorate: посчитать ключи один раз, отсортировать пары, вернуть значения.

8.6 Компромиссы

💻 Практика

1. Три сортировки со счётчиком. Реализуйте insertion, merge и quick с числом сравнений. Прогоните на 1 000 элементах в трёх формах: отсортированный, обратный, случайный (seed фиксирован). Ожидание: insertion почти отсортирован — резко дешевле; quick дешевле merge на случайных данных.
2. Ломаем quick сортировку. Возьмите пивот «последний элемент» и подайте отсортированный массив на 10 000: посчитайте сравнения и сравните с рандомизированным пивотом. Числа должны различаться на порядки.
3. Тест стабильности. Составьте срез пар {key, id} и отсортируйте по key merge sort и quick sort; посчитайте «нарушения порядка равных». Объясните результат: у merge — гарантия, у quick — нет.
4. Два ключа и stdlib. Отсортируйте людей по «фамилия, затем имя» через slices.SortFunc и через два прохода sort.SliceStable. Сравните читаемость и число сравнений (обёртка-счётчик).
5. Decorate-sort-undecorate. Задача: отсортировать строки по их длине, при равенстве — лексикографически, а вычисление длины «дорогое» (эмулируйте счётчиком вызовов). Покажите, что предвычисленный ключ уменьшает число дорогих операций в разы.

🧩 Quiz

✅ Итоги модуля

• Квадратичные сортировки не мусор: insertion адаптивен и живёт внутри гибридных сортировок; selection — минимум обменов; bubble — только учебный.
• Merge sort даёт гарантию Θ(n log n) и стабильность, платя O(n) памяти; quick sort in-place и быстрее на практике, но нестабилен и требует защиты от вырождения.
• Стабильность — не деталь: порядок равных элементов бывает частью контракта (инцидент с отчётом).
• slices.Sort/SortFunc — pdqsort с улучшениями; для равных, sort.SliceStable, а reflection-sort.Slice в новом коде не нужен.

🔗 Мостик к Модулю 9

Осталась структура, которая одновременно и сортирует частично, и живёт в рантайме самостоятельной жизнью: куча. В модуле 9 — «Куча и приоритетные очереди»: sift-up/down, сборка кучи за O(n), top-K без полной сортировки, k-way merge и медиана потока — и знакомство с container/heap, без которого не обходится ни один планировщик.