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

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

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

Пусть имеется набор 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
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 26
  • +11
    Ничто не ново под Луной — FlashSort.

    Но всё равно Вы молодец, если самостоятельно додумались.
    • +2
      Соглашусь, очень похоже. Но есть принципиальные отличия, меняющие картину. Пресловутая досортировка здесь сводится к минимуму. Она производится для массивчиков из 2-х, 3-х и 4-х чисел, где она тривиальна и мало затратна.
      Во вторую итерацию попадают подмассивы с разностью n max — n min близкой к n, то-есть уже во второй итерации слипаний, а значит и операций сравнения будет немного. То-есть даже на плохих данных сложность не должна превосходить n log n.
      Одна простая, но очень важная мысль: «В массиве из n чисел всегда не более чем n различных значений».
      • +6
        То-есть даже на плохих данных сложность не должна превосходить n log n.

        Это вряд ли. Если исходный массив содержит числа 1!, 2!, ..., n! (в произвольном порядке), или какой-нибудь более случайный набор, у которого log(log(n_k)) равномерно распределены на достаточно длинном отрезке, то на каждом шаге все числа, кроме одного, попадут в одну ячейку. И сложность будет n^2. Факториалы являются целыми положительными числами (хотя и произвольной длины), так что это условие не нарушено.
        • 0
          Да, верно. Математический склад ума все-таки отличается от обывательского. Никогда бы не пришло в голову сортировать факториалы. У факториалов и прочих сильно растущих функций есть один недостаток — сложно выписать достаточно много значений. Разрядность ограничена.
          Кроме того, можно применить «ход конем». Если имеются предположения о функции, порождающей отсортированный массив, можно применить нелинейное распределение значений по местам. Перемешанные факториалы, экспоненты и подобные сильно меняющиеся значения довольно специфичны.
          • –3
            Еще, КМК, нет особого смысла сортировать сами факториалы — очевидно же (?), что если x!>y!, то x>y для любых целых положительных чисел, т.е. сортировка оснований даст такой же результат, как сортировка их факториалов.
          • 0
            В принципе, даже не обязательно генерировать ряды с помощью быстрорастущих функций.

            Достаточно только неудачного минимума/максимума, чтобы сделать дельту не соответствующей среднему значению. Тогда подлый экстремум окажется на одном полюсе распределения, все остальные элементы — на противоположном.

            Анимация

            • +1
              Но тогда эти «остальные элементы» будут распределены уже более-менее равномерно, и при рекурсивном вызове алгоритм отсортирует их за линейное время. В случае факториалов распределение «один против всех» будет при каждом вызове.
              • +1
                Да, факториалы крайне неприятны для сортировки. Интересно, есть ли алгоритм сортирующий их за время меньше квадратичного? Навскидку, для неприятностей хватает даже не факториального роста, а лишь степенного.
              • +1
                Обдумываю тоже эту тему. Надо каким-то образом выявить сильную нелинейность. Пока осмысливается критерий того что что-то не так — вызов второй итерации, для которой количество значений несущественно меньше, чем начальное n. Раз так, то вместо того чтобы дальше сортировать с квадратичной сложностью, нужно либо интерполировать поточнее, либо использовать какой-то другой алгоритм сортировки.
        • –1
          >>> Преимущества:
          >>> Скорость, легкость понимания и программирования.

          А также: православный способ сортировки. )))

          • +1
            Родилось решение по сортировке факториалов и быстрого роста.
            Вычисление индекса надо производить над логарифмами сортируемых значений.
            delta=(log(n max)-log(n-min))/n+1
            indx=(log(n i)-log(n min))/delta+1
            Подходящее основание логарифма от 1,1 до 2.
            Логарифмирование не отменяет следующих итераций, которые уже можно делать над самими значениями, но исключает квадратичную сложность.
            • 0
              Надо будет поиграться с этими логарифмами (было бы время)… А если обычное линейное распределение, не пробовали? Эти формулы тоже подойдут?
              • 0
                В принципе, при линейном распределении тоже более-менее.

                Вот такой вот массив двузначных чисел:


                С помощью логарифмической дельты распределила следующим образом:


                С помощью обычной дельты раскидала так:


                То есть большие элементы логарифмическая дельта распределяет качественнее.

                А вот так логарифмы расфасовали набор из 10-ти чисел от 0 до 9.


                Без логарифмов бы каждое число попало бы в отдельную корзину.

                • 0
                  UPD. Чтобы у меня VBA не ругалось на логарифмы чисел <= 0 я поставил значение таких функций 0 (что неверно, разумеется)
                  Массив из 10 чисел от 1 до 10 логарифмическая дельта так бы распределила:

                  • +1
                    Главная фишка в том, что наборы чисел, которые в отсортированном виде ложатся на прямую delta*i+n min, i=0..n сортировать вообще не нужно. Достаточно сгенерировать заново этот набор.

                    Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.

                    Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
                    1) Если данные линейны или близки к линейным, оперируем со значениями.
                    2) Если нелинейны, причем сильно — логарифмируем. Натуральные логарифмы вполне годятся.
                    Вообще в нелинейном случае стоит задача сжать динамический диапазон значений. Может быть, арктангенс подойдет даже лучше.

                    Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.

                    • 0
                      >>>Главная фишка в том, что наборы чисел, которые в отсортированном виде ложатся на прямую delta*i+n min, i=0..n сортировать вообще не нужно. Достаточно сгенерировать заново этот набор. Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.

                      Сильно оторвано от практики. Идеально вписывающихся в функцию наборов значений почти не встречаются.

                      Кроме того Вы попадаете в порочный круг. Чтобы придти к выводу, что элементы нет надобности сортировать — их нужно отсортировать, чтобы увидеть вписываются ли они в какую-нибудь выхолощенную формулу.

                      >>> Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?

                      Если заранее есть точные сведения (ну или с высокой долей вероятности), то такая логика — ещё куда ни шло.

                      Но если набор пока не отсортирован, то понять степень нелинейности весьма затруднительно, если вообще возможно. Всё от чего можно оттолкнуться (после предварительного однократного прогона по структуре и не впадая в какие-то дополнительные расходы по памяти) — минимум, максимум и среднее арифметическое/геометрическое. Но этого, скорее всего, не хватит. Поведение нелинейности может напоминать вообще какую-нибудь хитрую недосинусоидную псевдоэкспоненту, которая станет очевидна только в конце процесса.

                      >>> Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.

                      В этом направлении можно сгенерировать несколько интересных идей.
                      Например, можно распределить небольшую часть массива (а ещё лучше — несколько, чтобы свести к минимуму влияние вырожденных ситуаций) обоими способами и сравнить по каким-то критериям насколько качественным вышло распределение по карманам в обоих случаях.

                      В целом, в гибридных (и вообще) сортировках я не припомню подхода, чтобы для решения по какому пути двигаться — нужно предугадать уровень энтропии в результате (хотя сортировки в основном придумывают программисты знающие толк в математике). Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
                      • +1
                        В целом, в гибридных (и вообще) сортировках я не припомню подхода, чтобы для решения по какому пути двигаться — нужно предугадать уровень энтропии в результате

                        В каком-то смысле это происходит, когда quicksort, решив, что случай неблагоприятный, переключается на heapsort. Там реакция идёт не на размер массива, а на уже обнаруженные статистические свойства порядка элементов.
                        • 0
                          Я только шапочно ознакомился с интроспективной сортировкой (не дошли пока руки разобраться в ней подробно), но насколько помню, что действительно «в каком-то смысле». Переключение происходит в результате достижения заранее оговоренной глубины рекурсии. Грубо говоря, переключаемся через изначально планируемое количество итераций, а не по результатам анализа характера распределения текущего набора данных. Повторюсь, в алгоритм я по сути не вникал, так что, может, я и не прав.
                          • +1
                            Правильно. Но то, что глубина рекурсии превысила планируемое число итераций — это и есть следствие того, что распределение (точнее, порядок) оказался неблагоприятным. А дальше авторы предположили, что раз уж случилось такое невероятное событие, то логично считать, что враги подсунули алгоритму набор-киллер, и теперь надо от него застраховаться (хотя, возможно, весь ущерб уже нанесён, а дальше было бы всё хорошо).
                            • 0
                              Как страшно жить сортировать. Никому нет доверия. )))
                        • +1
                          >> Поведение нелинейности может напоминать вообще какую-нибудь хитрую недосинусоидную псевдоэкспоненту, которая станет очевидна только в конце процесса.
                          Проще. Отсортированный рост является неубывающим. А если договориться о неразличимости одинаковых чисел, то и строго возрастающим. И чаще всего его вид будет кусочно линейно-нелинейным.

                          Этот алгоритм сортировки сам в некоторой степени являет собой кусочно-линейную аппроксимацию. С разрывами на стыках кусков. Естественно, что в линейной версии он спотыкается на экспоненте, которую как ни дифференцируй — она остается экспонентой. Но не страшно, для нее у нас припасен логарифм. Вопрос, похоже, становится чисто организационным. Когда выгоднее логарифмировать, в первом проходе, во втором или вообще запускать обе версии параллельно.

                          Что касается расходов по памяти — их можно сильно уменьшить. Массив количества индексов никуда не денется, конечно. Но вместо копирования самих чисел мы сохраняем указатели на них. Особенно выгодно получается, если работаем с действительными числами полной точности. (Само число — 10 байт, ссылка на него — 2 или 4 байта). Итого — памяти нужно не более 4n. В байтах: 10*n+ 2*3 n.

                          >>Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.

                          Вот. Именно. Еще одна фундаментальная мысль. Если имеется дополнительная информация об обрабатываемых неким алгоритмом данных, то она позволяет снизить сложность алгоритма. Как пример — таблицы Брадиса. Можно считать синусы с помощью рядов, а можно выбрать значение из таблицы.
                          • 0
                            Хорошо, что Вы сказали про аппроксимацию. Я припомнил, что есть же метод с однокоренным названием.

                            en.wikipedia.org/wiki/Proxmap_sort

                            Ещё не разбирался с ним, но по-моему что-то родственное тому что мы здесь обсуждаем.
                            • +1
                              Все сортировки без сравнений похожи. Суть — распределить n чисел по m классам. Только мало кто догадывается, что классов должно быть не менее n.
                              Кстати, свежая догадка. Если классов взять больше n, вплоть до nmax-nmin, то тогда слипаний станет существенно меньше, а при m= nmax-nmin их не будет вовсе. Разумеется, последнее справедливо для целых чисел. То-есть в массиве Indxs(i) будут только нули и единицы, вследствие чего сборка будет происходить за линейное время без дополнительных действий. Пугает расход памяти, но это решаемая проблема.
                              Конечно, реализован будет промежуточный вариант. Возможно, m=n*3 будет достаточно для существенного сокращения обычно большого количества пар и троек.
                        • 0
                          Помимо размера сортируемых подмассивов, категории которыми оперируют при переключении с одного метода на другой — «случайно перемешано» / «почти остортировано» / «реверсно отсортировано». Методов оценок линейности распределения данных ни Седжвик, ни Хоар, ни Дейкстра, ни Кнут, ни прочие мастодонты, не придумали (то есть мне об этом ничего не известно).

                          Некоторые алгоритмы заточены под определённого вида наборы данных, но при условии, что это известно до начала сортировки, а не вычисляется по ходу действия.
                      • 0
                        Ах да, ещё надо решить что с нулями делать )))

                        UPD. Ничего не делать, сортировка изначально рассчитана на натуральные числа. Или можно увеличить все элементы на число, достаточное чтобы все оказались положительными, отсортировать и затем уменьшить на это число.
                        • +1
                          Кстати, она прекрасно работает и с вещественными числами. Для логарифмов сдвигаем весь набор вправо на n min+ основание логарифма. Назад числа в наборе уменьшать не нужно. Сами числа мы не трогаем. Сдвиг нам нужен только для вычисления индексов.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.