Сортировка царя Соломона :: Solomon sort
Другие алгоритмы, использующие принципы приблизительного распределения и последующей вставки - флеш-сортировка и сортировка аппроксимацией.
Разновидность сортировки подсчётом, предложенная хабрапользователем V2008n.
Алгоритм назван в честь царя Соломона, являющийся автором библейской Книги Екклесиаста, 3-я глава которой начинается с таких слов:
1 Всему свое время, и время всякой вещи под небом:
2 время рождаться и время умирать;время насаждать и время вырывать посаженное;
3 время убивать и время врачевать; время разрушать и время строить;
4 время плакать и время смеяться; время сетовать и время плясать;
5 время разбрасывать камни и время собирать камни; время обнимать и время уклоняться от объятий;
6 время искать и время терять; время сберегать и время бросать;
7 время раздирать и время сшивать; время молчать и время говорить;
8 время любить и время ненавидеть; время войне и время миру.
Алгоритм
Этап 1. Минимум, максимум, дельта. В массиве ищутся наибольший и наименьший элементы. С помощью них вычисляется специальная величина, называемая дельтой.
delta = (Amax - Amin) / N
Этап 2. Время разбрасывать камни. С помощью дельты для каждого элемента массива оценивается на каком месте он должен находиться.
NewIndex(Ai) = (Ai - Amin) / delta + 1
При этом получаются группировки из 1-го, 2-х, 3-х, иногда - 4-х (а в вырожденных случаях - и из большего количества) элементов, которые одновременно "претендуют" на определённый индекс в массиве.
Этап 3. Время собирать камни. Эти небольшие подмножества быстро сортируются и из них склеивается финальный упорядоченный массив.
Характеристики алгоритма
| Название | Сортировка царя Соломона(Соломонова сортировка, Solomon sort) | |
|---|---|---|
| Автор | Хабрапользователь V2008n | |
| Год | 2013 | |
| Класс | Сортировки распределением | |
| Подкласс | Сортировки подсчётом | |
| Устойчивость | Да | |
| Сравнения | Нет | |
| Сложность по времени | Худшая | O(n2) |
| Средняя | O(n × k) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n × k) |
Ссылки
Подсчёт с приблизительным распределением — чаще всего переизобретаемая сортировка