81
правка
Изменения
Нет описания правки
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(nlog(log nloglog n))</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
Данная статья писалась на основе брошюры Хана, посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.
|id=def2.
|definition=
Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм не консервативныйнеконсервативный.
}}
{{Определение
|id=def3.
|definition=
Если мы сортируем целые числа из множества {0, 1, ..., <tex>m</tex> - 1} с длиной контейнера <tex>klog(m + n)</tex> с <tex>k</tex> >= 1, тогда мы сортируем с не консервативным неконсервативным преимуществом <tex>k</tex>.
}}
{{Определение
|id=lemma2.
|statement=
<tex>n</tex> целых чисел можно отсортировать в <tex>\sqrt{n}</tex> наборов <tex>S_{1}</tex>, <tex>S_{2}</tex>, ..., <tex>S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex>\sqrt{n}</tex> чисел и <tex>S_{i}</tex> < <tex>S_{j}</tex> при <tex>i</tex> < <tex>j</tex>, за время <tex>O(nlog(logn)nloglogn/logk)</tex> и место <tex>O(n)</tex> с не консервативным преимуществом <tex>klog(logn)kloglogn</tex>
|proof=
Доказательство данной леммы будет приведено далее в тексте статьи.
}}
{{Лемма
}}
Заметим, что когда <tex>g = O(logn)</tex> мы сортируем <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров за время <tex>O((n/g)log(logn)loglogn)</tex>, с использованием O(n/g) места. Выгода очевидна.
{{Лемма
|id=lemma5.
|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)nloglogn)/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=
Заметим, что если длина контейнера <tex>logmloglogn</tex> и только <tex>logm</tex> бит используется для упаковки <tex>g <= logn</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.
==Сортировка <tex>n</tex> целых чисел в <tex>\sqrt{n}</tex> наборов==
Постановка задачи и решение некоторых проблем:
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества {0, 1, ..., <tex>m</tex> - 1} в <tex>\sqrt{n}</tex> наборов как во второй лемме. Мы предполагаем, что в каждом контейнере <tex>kloglognlogm</tex> бит и хранит число в <tex>logm</tex> бит. Поэтому неконсервативное преимущество <tex>kloglogn</tex>. Мы так же предполагаем, что <tex>logm >= lognloglogn</tex>. Иначе мы можем использовать radix sort для сортировки за время <tex>O(nloglogn)</tex> и линейную память. Мы делим <tex>logm</tex> бит, используемых для представления каждого числа, в <tex>logn</tex> блоков. Таким образом каждый блок содержит как минимум <tex>loglogn</tex> бит. <tex>i</tex>-ый блок содержит с <tex>ilogm/logn</tex>-ого по <tex>((i + 1)logm/logn - 1)</tex>-ый биты. Биты считаются с наименьшего бита начиная с нуля. Теперь у нас имеется <tex>2logn</tex>-уровневый алгоритм, который работает следующим образом:
