Сорт голубятни - Pigeonhole sort

Сорт голубятни

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${displaystyle O(N+n)}$, куда N это диапазон ключевых значений и п размер ввода
Худший случай космическая сложность	${displaystyle O(N+n)}$

Сортировка голубятни это алгоритм сортировки что подходит для сортировки списков элементов, в которых количество элементов (п) и длину диапазона возможных значений ключа (N) примерно одинаковы.^[1] Это требует О (п + N) время. Это похоже на счетная сортировка, но отличается тем, что он «перемещает элементы дважды: один раз в массив корзин и еще раз в конечный пункт назначения [тогда как] подсчетная сортировка создает вспомогательный массив, а затем использует массив для вычисления конечного пункта назначения каждого элемента и перемещения элемента туда».^[2]

Алгоритм пеленга работает следующим образом:

1. Имея массив значений для сортировки, настройте вспомогательный массив изначально пустых «ячеек», по одной ячейке для каждого ключа в классифицировать ключей в исходном массиве.
2. Перебирая исходный массив, поместите каждое значение в ячейку, соответствующую его ключу, так, чтобы каждая ячейка в конечном итоге содержала список всех значений с этим ключом.
3. Выполните итерации по массиву ячеек в возрастающем порядке ключей и для каждой ячейки поместите его элементы в исходный массив в порядке возрастания.

Пример

Предположим, кто-то сортирует эти пары значений по первому элементу:

• (5, "привет")
• (3, «пирог»)
• (8, «яблоко»)
• (5, "король")

Для каждого значения от 3 до 8 мы настраиваем ячейку, а затем перемещаем каждый элемент в свою ячейку:

• 3: (3, «пирог»)
• 4:
• 5: (5, «привет»), (5, «король»)
• 6:
• 7:
• 8: (8, «яблоко»)

Затем массив палитры перебирается по порядку, и элементы возвращаются в исходный список.

Разница между сортировкой по ячейкам и сортировкой с подсчетом состоит в том, что при сортировке с подсчетом вспомогательный массив не содержит списков входных элементов, а только подсчитывает:

• 3: 1
• 4: 0
• 5: 2
• 6: 0
• 7: 0
• 8: 1

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

Реализация Python

def pigeonhole_sort(lst) -> Никто:    "" "Сортировать список пар (ключ, значение) по ключу." ""    основание = мин(ключ за ключ, ценить в lst)    размер = Максимум(ключ за ключ, ценить в lst) - основание + 1    почтовые ящики = [[] за _ в классифицировать(размер)]    за ключ, ценить в lst:        я = ключ - основание        голубятня = почтовые ящики[я]        голубятня.добавить((ключ, ценить))    я = 0    за голубятня в почтовые ящики:        за элемент в голубятня:            lst[я] = элемент            я += 1

Смотрите также

• Принцип голубятни
• Radix sort
• Очередь ведра, связанная структура данных очереди приоритетов

Рекомендации

1. Словарь алгоритмов и структур данных NIST: сортировка по ячейкам
2. Блэк, Пол Э. «Словарь алгоритмов и структур данных». NIST. Получено 6 ноября 2015.