Сортировка по ячейкам

Сортировка по ячейкам

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(N+n)$, где N — диапазон значений ключа, а n — размер входных данных.
Наихудшая пространственная сложность	$O(N+n)$
Оптимальный	Если и только если $N=O(n)$

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

Алгоритм «ячейки» работает следующим образом:

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 намного больше n , сортировка сегментами — это обобщение, более эффективное с точки зрения пространства и времени.

См. также

• Принцип «ячейки»
• счастливый корень
• Очередь сегментов , связанная структура данных приоритетной очереди.