Мелькающая сортировка :: FlashSort

Метод изобрёл профессор физики Карл-Дитрих Нойберт. Обрабатывая результаты экспериментов, он пришёл к выводу, что огромные массивы статистических данных вполне логично сортировать, прибегнув к теории вероятностей.

Общая суть такова. Проходим по массиву и каждый элемент переставляем примерно на своё место. Сформировав достаточно быстро почти отсортированный массив, затем доупорядочиваем вставками.

Flash sort

Алгоритм

Этап 1. Находим в массиве минимум и максимум. С помощью них в дальнейшем определяется, примерно в какой части массива каждый элемент должен находиться.

Этап 2. Строим вспомогательную таблицу распределения. Все элементы, в зависимости от величины, разбиваются на классы и в этой дополнительной таблице указывается сколько элементов принадлежит тому или иному классу.

Если распределить элементы массива на m классов, то номер класса для элемента Ai определяется по формуле:

Эмпирическим путём установлено, что оптимальное количество классов m для массива из n элементов рассчитывается по формуле:
m ≈ 0.42 n

Этап 3. Используя таблицу распределения, перераскидываем элементы примерно по своим местам.

Этап 4. Почти упорядоченный массив досортировываем простыми вставками.

Характеристики алгоритма

Название Мелькающая сортировка (FlashSort)
Автор Карл-Дитрих Нойберт (Karl-Dietrich Neubert)
Год 1998
Класс Сортировки распределением
Подкласс Сортировки подсчётом
Устойчивость Нет
Сравнения Нет
Сложность по времени Худшая O(n2)
Средняя O(n + m)
Лучшая O(n)
Сложность по памяти Общая O(n + m)
Дополнительная O(m)

Ссылки

Хабрахабр: Ещё одна сортировка распределением

FlashSort on Wikipedia
The FlashSort Algorithm on Neubert’s Home Page
FlashSort on Dr. Dobb’s Journal

Добавить комментарий