Конспект: простые сортировки

Понятия

Сортировка выбором - на каждом шаге ищет минимум неразложенного остатка и ставит на место. Θ(n²) сравнений ВСЕГДА (быстрого случая нет), но лишь Θ(n) обменов. Не устойчива, не адаптивна.

Сортировка пузырьком - многократно проходит массив, меняя местами соседей не по порядку; большие элементы всплывают в конец. Θ(n²) сравнений, до Θ(n²) обменов. Умеет рано выйти (проход без обменов = массив упорядочен). Устойчива.

Сортировка вставками - вставляет каждый элемент в отсортированный префикс, сдвигая большие вправо. Θ(n²) в худшем (перевёрнутый вход), Θ(n) в лучшем (почти упорядочен). Адаптивна и устойчива, работает на месте.

Адаптивность - цена сортировки падает с упорядоченностью входа (пропорциональна числу инверсий - пар не по порядку).

Устойчивость - равные элементы сохраняют относительный порядок.

Сортировка Шелла - вставки по убывающим шагам gap, оканчивающимся на 1. Крупные шаги двигают элементы дальними прыжками, финальный gap=1 доводит порядок. Быстрее Θ(n²) (около Θ(n^1.5)), не устойчива.

Что унести

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

Выбором минимизирует ОБМЕНЫ - её берут, когда перемещения дороги (большие элементы). Вставками - лучшая из простых: адаптивна (цена = беспорядок входа) и устойчива (знак >, не ≥). Реальные данные часто почти упорядочены, поэтому адаптивность вставок - причина скорости Timsort и переключения быстрых сортировок на вставки для маленьких кусков.

Шелла - урок «маленькая правка меняет асимптотику»: крупные шаги убирают по многу инверсий за обмен, снимая главную слабость вставок (движение по одной позиции).

Ловушки джокера

Применил квадратичную сортировку к большим данным. На миллионе элементов Θ(n²) - часы там, где n·log n справится за секунду.

Ждал быстрого случая от сортировки выбором. Его нет: она всегда Θ(n²), потому что каждый раз просматривает весь остаток.

Взял ≥ вместо > во вставках. Правильность цела, но устойчивость потеряна: равные меняются местами.

Не завершил шаги Шелла единицей. Соседи из разных подпоследовательностей не сравнятся - массив вернётся неотсортированным, хотя код «отработал».

Взял для Шелла плохую последовательность шагов (только степени двойки). Оценка деградирует к Θ(n²).

Проверь себя

Чем выбором отличается от пузырька, если сравнений у них поровну?

Почему у сортировки выбором нет быстрого случая, а у вставок он есть?

Что значит «адаптивная» и «устойчивая» и от чего зависит устойчивость вставок?

Что такое сортировка Шелла и почему её последний шаг обязан быть 1?

Почему крупные шаги Шелла позволяют побить Θ(n²)?