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

Ссылки

Соломонова сортировка

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