Мелькающая сортировка :: 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

The FlashSort Algorithm on Neubert's Home Page

FlashSort on Dr. Dobb's Journal