81
правка
Изменения
Нет описания правки
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(n \log\nlog(log n))</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
Данная статья писалась на основе брошюры Хана, посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.
|statement=
Если принять, что каждый контейнер содержит <tex>logm > logn</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(logm)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((nlog(logn))/g)</tex> с использованием <tex>O(n/g)</tex> места.
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
|proof=
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>(logn)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Мы можем переместить каждую группу контейнеров для чисел.
Если у нас длина контейнеров больше, сортировка может быть ускорена, как показано в следующей лемме.
{{Лемма
|id=lemma6.
|statement=
предположим, что каждый контейнер содержит <tex>logmloglogn > logn</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(logm)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)</tex>, с использованием <tex>O(n/g)</tex> памяти.
|proof=
}}
