Сортировка царя Соломона :: 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)

Ссылки

Хабрахабр: Соломонова сортировка

GitHub: Тестовая реализация на Fort

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