В сортировках распределением элементы распределяются и перераспределяются по классам до тех пор, пока массив не отсортируется.
В самом общем случае это происходит по примерно одинаковой схеме. Элементы разбрасываются по классам по какому-либо признаку. Если это не привело к упорядочиванию массива, то происходит уточнение признаков принадлежности к классу и элементы раскидываются по уточнённым классам снова. И так происходит до тех пор, пока массив не станет упорядоченным.
В сортировках распределением почти всегда отсутствуют сравнения элементов между собой и их обмены. Главное — это принадлежит ли элемент к некоторому классу или нет, его сравнение с другими элементами редко играет роль.
Обычно у этих сортировок линейная сложность по времени (а не логарифмическая, как у эффективных сортировок обменами, слиянием, выбором или вставками). Также алгоритмы этого класса почти всегда требуют много дополнительной памяти, поскольку сгруппированные по классам элементы приходится где-то хранить.
Сортировки распределением хороши для упорядочивания целых чисел и строк. Сортировать ими же вещественные числа, обычно, неудобно. Также сортировки распределением прекрасно сортируют массивы, состоящие из повторяющихся чисел — чем больше повторений, тем меньше разных классов требуется.
Рассмотрим алгоритм, наиболее выпукло демонстрирующий вышеперечисленные свойства.
Статья написана при поддержке компании EDISON Software, которая разрабатывает ПО для микротомографии, а также системы проверки здоровья людей, ответственных за безопасность других.
Вёдерная сортировка :: Bucket sort
Другие названия — корзинная сортировка, блочная сортировка, карманная сортировка.
Раскидываем числа по корзинам, затем в каждой корзине раскидываем по более мелким корзинам и так до тех пор пока на каком-то уровне в корзинке только одинаковые элементы. Тогда из таких корзин самого нижнего уровня легко восстановить массив в упорядоченном состоянии.
Поясним на конкретном примере. Допустим, у нас есть неупорядоченный массив. Известно, что в этом массиве содержатся числа от 1 до 8.
Мы раскидываем эти числа на 2 группы: в одну группу попадают числа от 1 до 4, во вторую — от 5 до 8. Затем числа в первой корзине распределяем по двум корзинам: в одной числа 1 и 2, а в другой 3 и 4. Эти корзинки тоже распределяем по лукошкам, в которых уже находятся числа одинакового размера. К той большой корзине, где содержатся числа от 5 до 8, применяем аналогичную рекурсию.
Затем из мелких корзинок, в каждой из которых содержатся одинаковые числа, мы в порядке старшинства возвращаем элементы в основной массив.
Вёдерная сортировка в таком виде не особо применима на практике, но она эталонно демонстрирует, как вообще работают все сортировки распределением.
Сортировка Таноса :: Thanos sort
Мне иногда присылают авторские сортировки и это как раз такой случай. Автор Андрей Данилин назвал её «Русская сортировка половинками», однако я её окрестил сортировкой Таноса. Или же, если формально исходить из используемых методов, можно назвать её средне-арифметическая вёдерная сортировка.
В массиве вычисляется средне-арифметическое элементов и затем все элементы распределяются на 2 группы. В одну группу идут элементы меньшие (или равные) средне-арифметическому, во вторую группу — большие чем средне-арифметическое. Затем эти же действия рекурсивно применяются к обоим группам — и так до победного конца.
Причём тут безумный титан? Если это рандомный массив, то, по большому счёту у элемента, при сравнении со среднеарифметическим, шансы 50/50 что он отправится в одну из двух групп.
Кстати, в Интернете мне попался другой шуточный алгоритм с таким же названием. Если массив не отсортирован, то тогда щёлкаем Перчаткой Бесконечности и отправляем выбранную случайным образом половину элементов массива в небытие. Если оставшиеся в живых образуют упорядоченный массив, то на этом свою великую миссию можно считать выполненной. Если ещё нет, то можно произвести ещё несколько щелчков.
Однако вернёмся к нашим распределительным сортировкам. Всех их можно распределить только по двум группам - сортировки подсчётом и поразрядные сортировки. Ну, если хочется, можно ещё выделить подсчётно-разрядные сортировки, т.е. те, которые можно отнести и к тем и другим.
Ещё есть гибридные алгоритмы (это такие, в которых используются методы разных классов, например, сортировка Тима — это помесь сортировки слиянием и сортировки вставками, интроспективная сортировка — это быстрая сортировка переходящая в сортировку кучей и т.п.), включающие в себя сортировки распределением, однако гибриды — это отдельный раздел. О них потом.
Вёдерная сортировка и средне-арифметическая сортировка Таноса относятся к сортировкам подсчётом.
Сортировки подсчётом
Основная идея — мы подсчитываем, сколько чисел содержится в каждом классе.
Сортировка подсчётом :: Counting sort
Считаем, сколько раз встречается то или иное число в массиве. Зная эти количества, быстро формируем уже упорядоченный массив.
Для этой сортировки нужно знать минимум и максимум в массиве. Тогда генерируются ключи для вспомогательного массива, в котором и фиксируем чего и сколько раз встретилось.
Код на Python:
def CountingSort(array, mn, mx):
count = defaultdict(int)
for i in array:
count[i] += 1
result = []
for j in range(mn,mx+1):
result += [j]* count[j]
return result
Голубиная сортировка :: Pigeonhole sort
Проходим по массиву, если встречается новое число то заводим счётчик (как ключ вспомогательного списка) этого числа. Если число встречается не в первый раз, то просто срабатывает инкремент для этого счётчика.
Отличие от предыдущего метода состоит в том, что в сортировке подсчётом мы сразу заводим счётчики для всех возможных чисел, которые, возможно, встретятся в массиве (можем себе это позволить, если известен максимум и минимум в массиве). Некоторые числа так и не встречаются и их счётчики показывают ноль. В голубиной сортировке мы заводим счётчики только для таких чисел, которые действительно встречаются в массиве. В сортировке подсчётом для счётчиков используется массив, а в голубиной сортировке — двусвязный список, позволяющий на ходу добавлять новые счётчики.
Этот способ иногда альтернативно называется сортировка Дирихле, потому что сам алгоритм является иллюстрацией различных следствий из принципа Дирихле.
Если N объектов, распределены по M контейнерам, и при этом N > M, то хотя бы в одном контейнере содержится более одного элемента.
Код на Python:
def PigeOnHoleSort(a):
mi = min(a)
size = max(a) - mi + 1
holes = [0] * size
for x in a:
holes[x - mi] += 1
i = 0
for count in range(size):
while holes[count] > 0:
holes[count] -= 1
a[i] = count + mi
i += 1
Поразрядные сортировки
Мы распределяем числа в зависимости от того, какая цифра находится в том или ином разряде числа. Если мы сделаем это несколько раз для разных разрядов, то внезапно получаем отсортированный массив.
Поразрядная сортировка по младшим разрядам :: LSD radix sort
Двигаемся от младших разрядов к старшим и на каждой итерации распределяем элементы массива в зависимости от того, какая цифра содержится в разряде.
После очередного распределения мы возвращаем элементы в основной массив в том порядке, в котором элементы попали в классы при очередном перераспределении.
Для поразрядных сортировок важно, чтобы элементы рассматривались, как имеющие одинаковое количество разрядов. Если фактически количество разрядов отличается, то проблема решается припиской дополнительных нулей в качестве старших разрядов.
Поразрядная сортировка по старшим разрядам :: MSD radix sort
Сначала распределяем по старшим разрядам, от которых двигаемся к младшим.
Этот вариант сложнее в реализации, так как переход к нижним разрядам рекурсивно осуществляется внутри классов, а не среди всех элементов массива.
Но эта сложность вознаграждается тем, что MSD работает быстрее чем LSD. При проходе от младших разрядов к старшим приходится обрабатывать все разряды всех чисел, чтобы корректно отсортировать. Если же двигаться от старших к младшим, то по факту не приходится обрабатывать все разряды всех чисел, состояние отсортированности, как правило, наступает раньше.
Большинство поразрядных сортировок являются разновидностью именно более эффективной MSD. Особенно это полезно для сортировки строк, для этого как правило используется суффиксное дерево. Разберём в одной из последующих статей.
Подсчётно-поразрядные сортировки
Иногда распределительная сортировка одновременно является и подсчётной и поразрядной.
Бисерная сортировка :: Bead sort
Другие названия алгоритма: абаковая сортировка, сортировка гравитацией.
Про эту сортировку уже пару раз писал (1, 2), поэтому буду краток, только самую суть.
Допустим, каждое число в массиве — это набор шариков, количество шариков — это величина числа. Если числа расположить друг по другом как горизонтальные ряды этих шариков и затем сдвинуть до упора по вертикали, то получим упорядоченный массив.
Здесь фокус в том, что каждое число мы с помощью шариков представляем в унарной системе счисления. И фактически, мы просто подсчитываем сколько раз у всех чисел встречается каждый разряд.
BeadSort на Python в одну строчку:
#!/bin/python3
from itertools import zip_longest
def beadsort(l):
return list(map(sum, zip_longest(*[[1] * e for e in l], fillvalue=0)))
Погодя разберём более сложные подсчётно-поразрядные сортировки, среди которых видное место занимает сортировка «Американский флаг».
Ссылки
Bucket / Вёдра, Counting / Подсчёт, Pigeonhole / Діріхле, Radix / Разряды, Bead
Статьи серии:
- Excel-приложение AlgoLab.xlsm
- Сортировки обменами
- Сортировки вставками
- Сортировки выбором
- Сортировки слиянием
- Сортировки распределением
- Подсчётные сортировки с приблизительным распределением
- Сортировка «Американский флаг»
- Суффиксное дерево в поразрядных сортировках
- Сравнение сортировок распределением
Комментарии (14)
mayorovp
22.10.2019 09:19Карманная сортировка вполне применима на практике, только надо число карманов брать большим, а не две. Кстати, MSD radix sort и bucket sort — это один и тот же алгоритм.
valemak Автор
22.10.2019 10:21>>> Кстати, MSD radix sort и bucket sort — это один и тот же алгоритм.
Не совсем так, в Википедии некоторая путаница с названиями. На странице Radix sort написано, что "radix sort has also been called bucket sort and digital sort". А если перейти на страницу Bucket sort, то там утверждается, что «It is a distribution sort, a generalization of pigeonhole sort, and is a cousin of radix sort in the most-to-least significant digit flavor» (то есть, это родственные алгоритмы, но не одно и то же).mayorovp
22.10.2019 10:23А не надо смотреть Википедию, вы посмотрите на сами алгоритмы, как они работают.
valemak Автор
22.10.2019 10:32Я рассматриваю корзинную/карманную сортировку в самом общем случае — раскидываем по корзинам, потом в каждой корзине по более мелким корзинам и т.п. Если при распределении по корзинам ориентироваться на разряды числа (более крупные корзины — это старшие разряды, более дробные корзины — младшие разряды), то в принципе да, Bucket sort сводится к MSD radix sort. Или даже можно так сказать — MSD radix sort это частный случай Bucket sort.
Для меня Bucket sort это своего рода алгоритм с мета-идеей, необязательно там ориентироваться именно по разрядам чисел, можно раскидывать по корзинам исходя из каких-то других классификаций. Как пример приведена сортировка Таноса, где на каждом уровне две корзины, в одной больше, а в другой меньше средне-арифметического.mayorovp
22.10.2019 10:35А как ещё можно выбрать корзины, если не по разрядам? Предлагаете выбрать их неравномерно? Ну ок, этот странный вариант карманной сортировки и правда не является MSD radix sort.
valemak Автор
22.10.2019 10:40Ну, при изучении алгоритмов и такие варианты стоит рассмотреть, хотя бы для того, чтобы придти к выводу, что распределение по разрядам, в принципе, самое эффективное.
fapsi
22.10.2019 14:14В массиве вычисляется средне-арифметическое элементов и затем все элементы распределяются на 2 группы. В одну группу идут элементы меньшие (или равные) средне-арифметическому, во вторую группу — большие чем средне-арифметическое. Затем эти же действия рекурсивно применяются к обоим группам — и так до победного конца.
Чем-то бинарное дерево напоминает.
Рассматривал другой алгоритм. Распределение на 3-4 группы, и сортировка в них через нахождение минимального числа — первое минимальное число на первую позицию, далее поиск min в оставшейся группе, и так до конца. Но это затратнее по времени.mayorovp
22.10.2019 15:37Если этот самый "другой алгоритм" применить сам к себе рекурсивно — получится сортировка слиянием, довольно быстрое семейство алгоритмов.
sinc
а что с фоном на гифках?
valemak Автор
На ноуте у меня неяркий экран, было незаметно что фон гуляет от кадра к кадру. А теперь взглянул с планшета и сам ужаснулся :-)
Анимацию делаю с помощью PHP, потому что мне нужно добавить в низ картинки индикатор прошедшего времени. Этот индикатор нужен, так как мне раньше жаловались, что анимация попадает в поле зрения не с начала, при этом непонятно когда анимация начинается, сколько времени ждать до завершения, чтобы просмотреть её заново и понять что на ней происходит.
Конечно, я могу делать гиф-анимацию и какой-нибудь программой (например, Easy Gif Animator или ей подобной), но большая проблема в том, что там индикатора времени тогда не будет :-(
sinc
а вторая гифка в тексте нормальная и с временной шкалой.
valemak Автор
Если Вы про сортировку Таноса, то там фон то чёрный, то синий.
sinc
это не так сильно бросается в глаза, как на всех остальных.
зы: очень нравится ваш цикл про сортировки) расскажите еще про внешние сортировки.
valemak Автор
Как временное решение — поставил в статье гифки с нормальным фоном, но без индикатора времени. А гифки с плохим фоном, но с индикатором времени убрал под спойлеры.
Вообще раньше у меня PHP нормально анимацию генерировал, почему на этот раз так, надо будет выяснять…