Флеш-сортировка :: FlashSort
Метод изобрёл профессор физики Карл-Дитрих Нойберт. Обрабатывая результаты экспериментов, он пришёл к выводу, что огромные массивы статистических данных вполне логично сортировать, прибегнув к теории вероятностей.Общая суть такова. Проходим по массиву и каждый элемент переставляем примерно на своё место. Сформировав достаточно быстро почти отсортированный массив, затем доупорядочиваем вставками.
Другие алгоритмы, использующие принципы приблизительного распределения и последующей вставки - сортировка царя Соломона и сортировка аппроксимацией.
Алгоритм
Этап 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