Flashsort

Проблема

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

Решение

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

Как это работает

Возьмём массив [35, 12, 89, 4, 67, 23, 55, 91, 8, 42] (n = 10). Число классов m = max(2, floor(0.45 · 10)) = 4. Диапазон значений min = 4, max = 91, коэффициент c1 = (4 - 1) / (91 - 4) = 3 / 87 ≈ 0.0345.

Класс каждого элемента считается по формуле floor(c1 · (значение - min)). Например, для 35: floor(0.0345 · 31) = floor(1.07) = 1. Пересчитав так все 10 элементов, получаем распределение по классам: 4, 12, 23, 8 - класс 0 (4 элемента); 55, 42, 35 - класс 1 (3 элемента); 89, 67 - класс 2 (2 элемента); 91 - класс 3 (1 элемент).

Раскладка L = [4, 3, 2, 1] (счётчики по классам) после накопления сумм становится L = [4, 7, 9, 10] - последнее значение, 10, равно n, как и в счётчике сортировки подсчётом. Это означает: элементы класса 0 займут индексы 0-3, класса 1 - индексы 4-6, класса 2 - индексы 7-8, класса 3 - индекс 9.

После цепочки циклических перестановок массив становится [12, 8, 4, 23, 42, 55, 35, 67, 89, 91] - все 10 элементов переставлены (move доходит до n - 1 = 9, плюс последний становится верным автоматически). Классы уже верны (первые 4 - действительно наименьшие, следующие 3 - средние, и так далее), но внутри класса 1 порядок `42, 55, 35` неверен - это и есть тот «мелкий беспорядок», который остаётся после классификации.

Финальная сортировка вставками проходит по всему массиву и приводит его к [4, 8, 12, 23, 35, 42, 55, 67, 89, 91]. Поскольку каждый элемент теперь стоит не дальше чем в пределах своего класса от финальной позиции, jj в цикле вставки почти никогда не уходит далеко назад - именно поэтому этот проход стоит близко к O(n), а не к O(n²), характерным для вставок на случайном массиве.

Худший случай возникает, когда распределение сильно скошено: если, например, 9 из 10 элементов попадают в один класс (сильно неравномерные данные), классификация почти ничего не даёт, и финальная сортировка вставками фактически сортирует весь массив заново - деградация до O(n²), совпадающая с обычной сортировкой вставками.

Флэш-сортировку опубликовал Карл-Дитрих Нойбер (Karl-Dietrich Neubert) в статье 1998 года в Dr. Dobb's Journal, представив её как алгоритм, объединяющий скорость распределяющих сортировок с работой прямо в исходном массиве, без выделения отдельных списков-корзин, как в bucket sort.

Итог: выигрыш Флэш-сортировки - линейное среднее время за счёт классификации плюс дешёвая доводка сортировкой вставками, а не отказ от сравнений вовсе (в отличие от counting sort). Она платит за это гарантией: без предположения о распределении данных её худший случай не лучше обычной сортировки вставками.

Нюансы выбора

Вместо bucket sort, когда важна память - Флэш-сортировка использует лишь вспомогательный массив размером m (порядка 0.45n), тогда как bucket sort выделяет под каждую корзину отдельный список, суммарно занимающий O(n) дополнительной памяти на списки плюс их накладные расходы.

Вместо quicksort на большом массиве заведомо равномерных числовых данных - в среднем случае O(n) обгоняет O(n log n), но выигрыш ощутим только на действительно больших n (десятки тысяч и больше), где константы классификации окупаются.

Не выбирать при неизвестном или сильно скошенном распределении - без гарантии равномерности риск деградации до O(n²) реален; для таких данных лучше merge sort/heap sort с гарантированным O(n log n) в худшем случае.

Против radix sort - когда ключи не разбиваются на разряды естественно - Флэш-сортировка классифицирует по линейной формуле от значения целиком, тогда как radix sort требует представления числа как последовательности разрядов; для чисел с плавающей точкой Флэш-сортировка зачастую проще применить напрямую.

Примеры в коде

Статья Карла-Дитриха Нойберта «Flashsort: A Distribution Sorting Algorithm» (Dr. Dobb's Journal, февраль 1998) - оригинальная публикация, представившая алгоритм и его сравнение по скорости с quicksort на равномерных данных.

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

Библиотеки и бенчмарки сортировок на C/C++, сравнивающие распределяющие сортировки (flashsort, bucket sort, radix sort) между собой на синтетических равномерных наборах данных, часто включают Флэш-сортировку как эталон «сортировки почти без сравнений».

Учебные курсы по продвинутым алгоритмам сортировки используют Флэш-сортировку как пример двухфазного алгоритма - грубая классификация плюс точная доводка, - демонстрируя общий паттерн, который также лежит в основе intro sort и других гибридных схем.

Когда применять

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

Примеры из практики

• Обработка больших массивов сенсорных или измерительных данных с известным диапазоном значений - классификация по классам хорошо ложится на такие данные.
• Академические сравнения алгоритмов сортировки часто включают Флэш-сортировку как пример распределяющей сортировки, конкурирующей по скорости с быстрой сортировкой на подходящих данных.