Algorithms
January 2014 9

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

Доброго Нового Года!

В копилку экзотических способов сортировки предложу еще один, немного своеобразный, но обещающий приличную скорость при хорошо случайных данных.

Пусть имеется набор N из n целых положительных чисел от 1 до n.
Самоочевидно, что для хранения n чисел необходимо иметь n ячеек. Вне зависимости от порядка, в котором числа будут записаны.

Исходный массив
3 5 2 1 8 4 7 6 9 10

Несложно представить, что неупорядоченный набор N достаточно просто заменить упорядоченным (по возрастанию, или по убыванию), записав упорядоченный набор на место неупорядоченного.

Упорядоченный массив
1 2 3 4 5 6 7 8 9 10


Таким же образом можно «сортировать» наборы чисел (ограничимся целыми положительными), удовлетворяющие условию nmax-nmin = n.

Рассмотрим более сложный случай.

Пусть набор N (опять же целых положительных чисел) таков, что nmax-nmin > n, и все числа n(i) в наборе разные.
30 55 21 17 82 46 79 63 94 108

Чтобы отсортировать данный набор, нужно:
1) найти nmax, nmin
2) вычислить дельта d=(nmax-nmin) /n
3) для каждого n(i) (следующую процедуру назовем условно «разбрасыванием камней»):
3а) вычислить индекс indx=( n(i)-nmin)/d+1(так как вычисления также предполагаются в целых числах, единица добавляется для компенсации округления и исключения нулевого индекса)

Числа n(i) и индексы indx ака места, на которых должны стоять эти числа.
30 55 21 17 82 46 79 63 94 108
2 5 1 1 7 4 7 5 9 10

3б) в заранее подготовленном, заполненном нулями массиве «индексы» Indxs инкрементируем ячейку с индексом, полученным в предыдущем шаге
2 1 0 1 2 0 2 0 1 1

3в) считываем получившееся значение
3г) умножаем его на n и складываем с индексом, записываем по этому адресу число n(i) в массиве Nnew
Если попадаются одинаковые индексы, n(i) в массив N new записываем не рядом, а снизу.
21 30 46 55 82 94 108
17 63 79

4) далее приступаем к «сбору камней»
Кладем i=1 и последовательно считываем массив индексов Indxs пока i ≤ n
4а) если Indxs(i) = 0, переходим к следующему i
4б) если Indxs(i) = 1, считываем число из массива Nnew, выводим его в отсортированный массив, переходим к следующему i
4в) если Indxs(i) = 2, считываем числа из Nnew записанные «по-вертикали», сравниваем их и выводим сперва меньшее, затем большее, переходим к следующему i
4г) если Indxs(i) = 3, считываем 3 числа, находим среди них минимальное, выводим его и исключаем из списка, затем сравниваем два оставшихся и выводим уже их.
4д) для Indxs(i) = 4, все то же, сначала находим минимальное из четырех, вычеркиваем его, затем делаем тоже что и для индекса 3.
4е) если Indxs(i) больше 4, вызываем алгоритм рекурсивно.
Отсортированный массив
17 21 30 46 55 63 79 82 94 108


Попробуем оценить количество операций.
На поиск минимального и максимального нужен один проход — n операций.
На «разбрасывание камней» еще n операций.
«Сбор камней» по затратам зависит от входных данных. В данном случае нужно n копирований и 3 операции сравнения пары чисел.

При тестировании на наборах с n=10000, полученных с random.org (ресурс не дает больше 10000 чисел в одном наборе) алгоритм показывает следующую статистику:
При nmax=10000. Все индексы = 1, сортировка производится за 3 прохода по массиву.
При nmax=11000. Нулей почти половина: 4547, единиц 906, двоек :4547, троек и более:0 Те же три прохода плюс почти половина от n сравнений 2-х чисел.
При nmax=21000 Zeroes:3967 Ones:2845 Twos:2409 Threes:779 Fours:0
При nmax=31000 Zeroes:3881 Ones:3134 Twos:2197 Threes:680 Fours:108 More_than_four:0
При nmax=101000 max in index:6 Zeroes:3729 Ones:3541 Twos:1923 Threes:643 Fours:139 More_than_four:25
всего 25 вызовов второй итерации.

Интуитивно, в самом худшем случае будет совершено n/5 итераций.
В среднем, навскидку, число операций порядка 4n

Этот способ сортировки относится к группе сортировок без сравнений и является промежуточной версией между карманной и сортировкой с подсчетом.

Главная проблема сортировки подсчетом — необходимость дополнительно сортировать значения, попадающие в одну ячейку, имеет значимость при количестве чисел в ячейке больше 4-х.
Но, во-первых, мы имеем хороший гандикап за счет единиц и пар чисел.
Во-вторых, число бурстов обычно относительно невелико, менее одного процента.
В-третьих, уже на второй итерации бурсты очень хорошо отрабатываются. К тому же автоматически снимается ограничение на отсутствие повторов во входных данных. Если нам попадается бурст из одинаковых значений, то для него дельта d=(nmax-nmin) /n=0 и мы можем смело весь бурст скопировать на выход.

Проблема применимости этого способа сортировки не только для целых положительных чисел тоже вполне решаема.

Безусловно, данный способ требует большей обкатки и выявления подводных камней.

Преимущества:
Скорость, легкость понимания и программирования.
Недостатки:
Довольно большие требования к памяти, зависящие от входных данных. Что можно попытаться скомпенсировать более рациональной организацией массива Nnew. В любом случае памяти нужно не менее 3n.

UPD:
Тестовый Форт код на GitHub
+32
27.1k 158
Comments 26
Top of the day