Конспект: устойчивость, ключ и библиотеки

Понятия

Ключ - поле записи, по которому её сравнивают (перемещая запись целиком). Одну структуру можно сортировать по разным ключам.

Устойчивость - записи с РАВНЫМ ключом сохраняют исходный взаимный порядок. Позволяет собирать многоключевую сортировку.

Многоключевая сортировка - от МЕНЕЕ важного ключа к БОЛЕЕ важному устойчивой сортировкой: сначала по вторичному, потом устойчиво по первичному.

Timsort - адаптивное УСТОЙЧИВОЕ слияние (объекты в Python/Java): ищет упорядоченные куски (runs), короткие добивает вставками, сливает. Θ(n·log n) в худшем, ~Θ(n) на почти упорядоченных, Θ(n) памяти.

Introsort - БЫСТРАЯ сортировка со страховкой (числа в C++): при глубокой рекурсии переключается на пирамидальную, маленькие куски - вставками. Θ(n·log n) гарантированно, на месте, НЕ устойчив.

Распознающий префикс - минимальное начало строки, по которому её уже не спутать с остальными. Строковые сортировки читают только его.

MSD-сортировка - подсчётом по старшему символу, рекурсивно в корзины; маленькие корзины - вставками, иначе съедают счётчики размером с алфавит.

Трёхпутевая поразрядная быстрая - разбиение по символу на «меньше, равно, больше», к следующему символу идёт только средняя часть.

Что унести

Устойчивость - свойство алгоритма, зависит от того, переставляет ли он ДАЛЁКИЕ элементы:

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

В библиотеках стоят ГИБРИДЫ, собранные из наших глав: - Timsort = слияние + вставки + адаптивность (объекты, нужна устойчивость); - introsort = быстрая + пирамидальная + вставки (примитивы, устойчивость не нужна, память дорога). Оба добивают маленькие куски вставками (минимум накладных расходов).

Выбор сортировки - по данным (дерево вопросов): 1. целые в малом диапазоне → подсчётом/поразрядно (Θ(n), обгоняет n·log n); 2. почти упорядочены → вставками/Timsort (~Θ(n)); 3. нужна устойчивость → слияние/Timsort; 4. дефицит памяти + гарантия → пирамидальная; 5. крохотный массив → вставками; 6. иначе → ВСТРОЕННАЯ.

По умолчанию - встроенная (она гибрид, всё учла). Своё пишут лишь под особые ключи.

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

Сортируешь строки с общим префиксом сравнениями. Каждое сравнение перечитывает префикс: на адресах - в 20 раз больше символов, чем у трёхпутевой поразрядной быстрой.

Взял неустойчивую сортировку для второго прохода многоключевой. Порядок по предыдущему ключу разрушен.

Считаешь устойчивость всегдашним требованием. Если ключ уникален или порядок равных не важен - можно неустойчивую (более быструю).

Написал свою быструю сортировку в прод. Худший случай Θ(n²) и баги; встроенная (гибрид) почти всегда лучше.

Думаешь, что «в библиотеке - быстрая сортировка». Там гибрид: Timsort для объектов, introsort для примитивов.

Выбрал сортировку по привычке. Упустил: подсчёт Θ(n) для малых целых; Timsort Θ(n) на почти упорядоченных; устойчивость для многоключевой.

Проверь себя

Что такое ключ и устойчивость?

Как собрать сортировку по двум ключам и почему идут от менее важного?

Какие сортировки устойчивы, какие нет и почему?

Что такое Timsort и introsort и почему объекты сортируют одним, а примитивы другим?

Как выбрать сортировку под данные и почему по умолчанию берут встроенную?

Почему сравнение строк не стоит единицу и что делают с этим строковые сортировки?