Сортировка Pigeonhole - это алгоритм сортировки, который подходит для сортировки списков элементов, в которых количество элементов ( n ) и длина диапазона возможных значений ключа ( N ) примерно одинаковы. [1] Это требует O ( n + N ) времени. Это похоже на сортировку с подсчетом , но отличается тем, что она «перемещает элементы дважды: один раз в массив ведра и снова в конечный пункт назначения [тогда как] сортировка по счету создает вспомогательный массив, а затем использует массив для вычисления конечного назначения каждого элемента и перемещения предмет там. " [2]
Класс | Алгоритм сортировки |
---|---|
Структура данных | Множество |
Наихудшая производительность | , где N - диапазон ключевых значений, а n - размер ввода. |
Сложность пространства в наихудшем случае |
Алгоритм работы с ячейками выглядит следующим образом:
- Имея массив значений для сортировки, настройте вспомогательный массив изначально пустых «ячеек», по одной ячейке для каждого ключа в диапазоне ключей в исходном массиве.
- Перебирая исходный массив, поместите каждое значение в ячейку, соответствующую его ключу, так, чтобы каждая ячейка в конечном итоге содержала список всех значений с этим ключом.
- Выполните итерации по массиву ячеек в возрастающем порядке ключей и для каждой ячейки поместите его элементы в исходный массив в порядке возрастания.
Пример
Предположим, кто-то сортирует эти пары значений по их первому элементу:
- (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 намного больше, чем n , сортировка по корзинам является обобщением, которое более эффективно в пространстве и времени.
Реализация Python
от ввода списка импорта , кортежа , любого def pigeonhole_sort ( lst : List [ Tuple [ int , Any ]]) -> None : "" " На месте сортирует список кортежей (ключ, значение) по ключу. : param lst: Список кортежей, каждый из которых имеет ключ в виде числа и значение, которое может быть любым. : return: Нет "" " base = min ( ключ для ключа , значение в lst ) size = max ( ключ для ключа , значение в lst ) - base + 1 # Создать пустой список (списков) для заполнения # Это список списков, потому что ключ может появляться дважды в ячейках : List [ List [ Tuple [ int , Any ]]] = [[] for _ in range ( size )] для ключа , значение в lst : index = key - base pigeonhole = pigeonhole [ index ] pigeonhole . добавить (( ключ , значение )) lst = [] # Повторно инициализируем список: мы собираемся повторно заполнить его из ячеек для ячеек в ящиках : lst . расширять ( ячейка )
Смотрите также
- Принцип голубятни
- Radix sort
- Bucket queue , связанная структура данных очереди приоритетов
Рекомендации
- ^ Словарь алгоритмов и структур данных NIST: сортировка по ячейкам
- ^ Блэк, Пол Э. "Словарь алгоритмов и структур данных" . NIST . Проверено 6 ноября 2015 года .