Изменения

Перейти к: навигация, поиск

Сортировка Хана

8514 байт добавлено, 00:14, 8 июня 2015
Нет описания правки
'''Сортировка Хана ''' (Yijie Han)англ. ''Hansort'' ) {{---}} сложный алгоритм сортировки целых чисел со сложностью <texdpi="130">O(n \log\log n)</tex>, где <texdpi="130">n</tex> {{---}} количество элементов для сортировки.
Данная статья писалась на основе брошюры Хана(англ. ''Yijie Han''), посвященной этой сортировке.
== Описание ==
Алгоритм построен на основе '''экспоненциального поискового дерева (далее {{---}} ЭП-дерево) Андерсона ''' (англ. ''Andersson's exponential search tree''). Сортировка происходит за счет вставки целых чисел в экспоненциальное поисковое дерево (''далее {{---}} ЭП-дерево'').
== Andersson's exponential search tree Экспоненциальное поисковое дерево Андерсона ==ЭП-дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (<tex>0< e < 1</tex>) ЭП-поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое ЭП-поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(n \log\log n)</tex> уровней. При нарушении баланса дерева необходимо балансирование, которое требует <tex>O(n \log\log n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.
{{Определение|definition ==Определения== # Контейнер '''ЭП-дерево''' {{---}} объектэто дерево поиска, в которым котором все ключи хранятся наши данные. Например: 32-битные в листьях этого дерева и 64-битные числа, массивы, вектораколичество детей у каждого узла уменьшается экспоненциально от глубины узла.# Алгоритм, сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex>, называется консервативным, если длина контейнера (число бит в контейнере) равна <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.} # Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m [[Файл:Exp- 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с неконсервативным преимуществом <tex>k</tex>tree.png|400px|thumb|right|Общая структура ЭП-дерева]]# Для множества <tex>S</tex> определимСтруктура ЭП-дерева:
1) Корень имеет <texdpi="130">\minTheta (Sn^e) </tex> сыновей <tex dpi= \min\limits_{a \in S} a"130">( 0 < e < 1 )</tex> . Все сыновья являются ЭП-деревьями.
2) Каждое поддерево корня имеет <texdpi="130">\maxTheta(S) = \max\limits_n^{a \in S1-e} a)</tex>сыновей.
Набор В этом дереве <texdpi="130">S1O(n \log\log n)</tex> < уровней. При нарушении баланса дерева необходимо балансирование, которое требует <texdpi="130">S2O(n \log\log n)</tex> если времени при <texdpi="130">\max(S1) \le \min(S2)n</tex>вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.
==Сортировка с использованием O(n log log n) времени Определения== {{ Определение | definition = '''Контейнер''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и памяти=64-битные числа, массивы, вектора.}}{{ Определение | definition =Для сортировки Алгоритм, сортирующий <texdpi="130">n</tex> целых чисел в диапазоне {из множества <texdpi="130">\{0, 1, \ldots, m - 1\}</tex>} предполагается, что называется '''консервативным''', если длина контейнера (число бит в нашем консервативном алгоритме используется контейнер длины контейнере) равна <texdpi="130">O(\log (m + n))</tex>. Далее везде считаетсяЕсли длина больше, что все то алгоритм '''неконсервативный'''. }}{{ Определение | definition = Если сортируются целые числа упакованы в контейнеры одинаковой длиныиз множества <tex dpi="130">\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex dpi="130">k \log (m + n)</tex> с <tex dpi="130">k \geqslant 1</tex>, тогда сортировка происходит с '''неконсервативным преимуществом''' <tex dpi="130">k</tex>. }}{{ Определение | definition = Для множества <tex dpi="130">S</tex> определим <tex dpi="130">\min(S) = \min\limits_{a \in S} a</tex>
<tex dpi="130">\max(S) = \max\limits_{a \in S} a</tex>
Берем Набор <tex>1/e dpi= 5</tex"130"> для ЭП-дерева Андерссона. Следовательно, у корня будет S1 <tex>n^{1/5}S2</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь если <tex>n^{4/5}</tex> листьев. В отличие от оригинального дерева, зараз вставляется не один элемент, а <tex>d^2</tex>, где <tex>d</tex> — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются <tex>n^{2/5}</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <tex>t_{1} dpi= n^{1/5}</tex"130"> наборов <tex>S_{1}, S_{2}, \ldots, S_{t_{1}}</tex>, в каждом из которых <tex>n^{4/5}</tex> чисел и <tex>S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex>n^{max(4/5S1)\leqslant \min(2/5S2)}</tex> чисел из <tex>S_{i}</tex> и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex>t_{2} = n^{1/5}n^{4/25} = n^{9/25}</tex> наборов <tex>T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>, аналогичных наборам <tex>S_{i}</tex>, в каждом из которых <tex>n^{16/25}</tex> чисел. Теперь числа опускаются дальше в ЭП-дереве.
Нетрудно заметить{{ Определение | definition = Предположим, что перебалансирока занимает есть набор <texdpi="130">O(n T</tex> из <tex dpi="130">p</tex> чисел, которые уже отсортированы как <tex dpi="130">a_{1}, a_{2}, \logldots, a_{p}</tex> и набор <tex dpi="130">S</tex> из <tex dpi="130">q</tex> чисел <tex dpi="130">b_{1}, b_{2}, \log n)ldots, b_{q}</tex>. Тогда '''разделением''' <tex dpi="130">q</tex> чисел <tex dpi="130">p</tex> числами называется <tex dpi="130">p + 1</tex> времени с набор <texdpi="130">O(n)S_{0}, S_{1}, \ldots, S_{p}</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссонагде <tex dpi="130">S_{0} < a_{1} < S_{1} < \ldots < a_{p} < S_{p}</tex>.}}
==Леммы==
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне {{Лемма|id = lemma1|about = № 1|statement = Даны целые числа <texdpi="130">b \geqslant s\geqslant 0</tex>. Имеется , и <tex dpi="130">T</tex>t является подмножеством множества <tex dpi= n"130">\{0, \ldots, 2^{b - 1 - (4/5)^s\}</tex> наборов по , содержащим <texdpi="130">n</tex> элементов, и <tex dpi="130">t \geqslant 2^{(4/5)-s + 1}С^sk_{n}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет Функция <texdpi="130">p = n^h_{(1/5)(4/5)^sa}</tex> детей, то на принадлежащая <texdpi="130">H_{b,s + 1}</tex> уровень опускаются , может быть выбрана за время <texdpi="130">q = nO(bn^{(2/5)(4/5)^s}</tex> чисел для каждого наборатак, или всего что количество коллизий <texdpi="130">qt \ge n^coll(h_{2/5a}, T) \leqslant t</tex> чисел для всех наборов за один раз.}}
{{Лемма
|id = lemma2
|about = № 2
|statement =
Выбор <tex dpi="130">s</tex>-ого наибольшего числа среди <tex dpi="130">n</tex> чисел, упакованных в <tex dpi="150">\frac{n}{g}</tex> контейнеров, может быть сделан за время <tex dpi="150">O(\frac{n \log g}{g})</tex> и с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти. В том числе, так может быть найдена медиана.
Спуск вниз можно рассматривать |proof = Так как сортировку возможно делать попарное сравнение <texdpi="130">qg</tex> чисел в каждом наборе вместе одном контейнере с <texdpi="130">pg</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <texdpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <texdpi="130">qg</tex> -ого чисел разделены из 5 контейнеров в один контейнер за константное время. Таким образом, набор <texdpi="130">p + 1S</tex> наборов из медиан теперь содержится в <texdpi="150">S_\frac{0n}, S_{1}, \ldots, S_{p5g}</tex> таких, что контейнерах. Рекурсивно находим медиану <texdpi="130">S_{0} < m</tex> {в <texdpi="130">a_{1}S</tex>} . Используя <texdpi="130"><m</tex> , уберем хотя бы <texdpi="150">\ldotsfrac{n}{4}</tex> чисел среди <texdpi="130"><n</tex> {. Затем упакуем оставшиеся из <texdpi="150">a_\frac{n}{pg}</tex>} контейнеров в <texdpi="150">< S_\frac{3n}{p4g}</tex>контейнеров и затем продолжим рекурсию.}}
{{Лемма
|id = lemma3
|about = № 3
|statement =
Если <tex dpi="130">g</tex> целых чисел, в сумме использующих <tex dpi="150">\frac{\log n}{2}</tex> бит, упакованы в один контейнер, тогда <tex dpi="130">n</tex> чисел в <tex dpi="150">\frac{n}{g}</tex> контейнерах могут быть отсортированы за время <tex dpi="150">O(\frac{n \log g}{g})</tex> с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.
Так как <tex>q</tex> чисел не надо полностью сортировать и <tex>q = p^2</tex>, то можно использовать '''лемму №2''' для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью signature sorting. Для этого используется линейная техника многократного деления (multi-dividing technique).
|proof =
Так как используется только <tex dpi="150">\frac{\log n}{2}</tex> бит в каждом контейнере для хранения <tex dpi="130">g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <tex dpi="150">O(\frac{n}{g})</tex> времени и памяти. Так как используется <tex dpi="150">\frac{\log n}{2}</tex> бит на контейнер, понадобится <tex dpi="130">\sqrt{n}</tex> шаблонов для всех контейнеров. Затем поместим <tex dpi="150">g < \frac{\log n}{2}</tex> контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более <tex dpi="130">g - 1</tex> контейнеров, которые не смогут образовать группу. Поэтому не более <tex dpi="130">\sqrt{n}(g - 1)</tex> контейнеров не смогут сформировать группу. Для каждой группы помещаем <tex dpi="130">i</tex>-е число во всех <tex dpi="130">g</tex> контейнерах в один. Таким образом берутся <tex dpi="130">g</tex> <tex dpi="130">g</tex>-целых векторов и получаются <tex dpi="130">g</tex> <tex dpi="130">g</tex>-целых векторов, где <tex dpi="130">i</tex>-ый вектор содержит <tex dpi="130">i</tex>-ое число из входящего вектора. Эта транспозиция может быть сделана за время <tex dpi="130">O(g \log g)</tex>, с использованием <tex dpi="130">O(g)</tex> памяти. Для всех групп это занимает время <tex dpi="150">O(\frac{n \log g}{g})</tex>, с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.
Procedure '''LinearДля контейнеров вне групп (которых <tex dpi="130">\sqrt{n}(g -Time-Sort'''1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex dpi="150">O(\frac{n}{g})</tex> времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex dpi="130">n</tex> контейнеров. Таким образом, все числа отсортированы.
Входные данные: <tex>r > = n^{2/5}</tex> чисел <tex>d_{i}</tex>, <tex>d_{i}.value</tex> — значение числа <tex>d_{i}</tex>, в котором <tex>(2 \log n)/(c \log\log n)</tex> бит, <tex>d_{i}.set</tex> — набор, в котором находится <tex>d_{i}</tex>. Следует отметить, что всего есть <tex>t</tex> наборов.
# Сортируем все Заметим, что когда <texdpi="130">d_{i}g = O( \log n)</tex> по , сортировка <texdpi="130">d_{i}.valueO(n)</tex>, используя bucket sort. Пусть все отртированные числа чисел в <texdpi="150">A[1..r]\frac{n}{g}</tex>. Этот шаг занимает линейное контейнеров произойдет за время, так как сортируется не менее <texdpi="150">O((\frac{n^}{2/5g})</tex> чисел.# Помещаем все <texdpi="130">A[j]\log\log n)</tex> в с использованием <texdpi="150">A[j].setO(\frac{n}{g})</tex>памяти.Выгода очевидна.}}
Таким {{Лемма|id = lemma4|about = № 4|statement = Примем, что каждый контейнер содержит <tex dpi="130"> \log m > \log n</tex> бит, и <tex dpi="130">g</tex> чисел, в каждом из которых <tex dpi="150">\frac{\log m}{g}</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex dpi="150">\frac{\log n}{2g}</tex> бит, и <tex dpi="130">g</tex> маркеров упакованы в один контейнер таким же образом заполняются все наборы <tex dpi="130">^*</tex>, что и числа, тогда <tex dpi="130">n</tex> чисел в <tex dpi="150">\frac{n}{g}</tex> контейнерах могут быть отсортированы по их маркерам за линейное время<tex dpi="150">O(\frac{n \log\log n}{g})</tex> с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.(*): если число <tex dpi="130">a</tex> упаковано как <tex dpi="130">s</tex>-ое число в <tex dpi="130">t</tex>-ом контейнере для чисел, тогда маркер для <tex dpi="130">a</tex> упакован как <tex dpi="130">s</tex>-ый маркер в <tex dpi="130">t</tex>-ом контейнере для маркеров.
После |proof = Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <texdpi="150">g</tex> сокращений бит в '''signature sorting''' получаем неконсервативное преимущество в <tex>(h/ \logfrac{\log n)^g}{2}</tex>бит. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на '''лемму №2''' Сортировка сгруппирует контейнеры для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборыкак в [[#lemma3|лемме №3]]. Заметим, что по природе битового сокращения начальная задача разделения Перемещаем каждую группу контейнеров для каждого набора перешла в <tex>w</tex> подзадач разделения на <tex>w</tex> поднаборов для какого-то числа <tex>w</tex>чисел.}}
{{Лемма
|id = lemma5
|about = № 5
|statement =
Предположим, что каждый контейнер содержит <tex dpi="130">\log m \log\log n > \log n</tex> бит, что <tex dpi="130">g</tex> чисел, в каждом из которых <tex dpi="150">\frac{\log m}{g}</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex dpi="150">\frac{\log n}{2g}</tex> бит, и что <tex dpi="130">g</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <tex dpi="130">n</tex> чисел в <tex dpi="150">\frac{n}{g}</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex dpi="150">O(\frac{n}{g})</tex> с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем|proof = Заметим, используя '''лемму №2'''что несмотря на то, делается разделение. Так как получено неконсервативное преимущество в что длина контейнера <texdpi="130">(h/ \log m \log\log n)^g</tex> и работа происходит на уровнях не нижебит, чем всего <texdpi="130">2 \logm</tex> бит используется для хранения упакованных чисел. Так же как в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <tex dpi="130">g \log\log n</tex>вместо <tex dpi="130">g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, то алгоритм занимает содержащей <texdpi="130">O(qt g \log\log n</(tex> контейнеров, упаковываем <tex dpi="130">g(\log h - \logn</tex> контейнеров в <tex dpi="130">g</tex>, упаковывая <tex dpi="130">\log\log n) - \log</tex> контейнеров в один. Далее делаем транспозицию над <tex dpi="130">g</tex> контейнерами. Таким образом перемещение занимает всего <tex dpi="130">O(g \log\log n)) </tex> времени для каждой группы и <tex dpi= "150">O(\frac{n}{g})</tex> времени для всех чисел. После завершения транспозиции, распаковываем <tex dpi="130">g</tex> контейнеров в <tex dpi="130">g \log\log n)</tex> времениконтейнеров.
В итоге разделились <tex>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть получилосьЗаметим, что если длина контейнера <texdpi="130">S_{0}\log m \log\log n</tex> < {и только <texdpi="130">e_{1}\log m</tex>} < <tex>S_{1}</tex> < бит используется для упаковки <texdpi="130">g \leqslant \ldots</tex> < {<tex>e_{p}</tex>} < <tex>S_{p}log n</tex>чисел в один контейнер, где тогда выбор в [[#lemma2|лемме №2]] может быть сделан за время и память <texdpi="150">e_O(\frac{in}</tex> {{---}} сегмент <tex>a_{ig})</tex>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, потому что числа хранятся упаковка в массиве доказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <texdpi="150">B</tex> так, что числа в <tex>S_O(\frac{in}</tex> предшествуют числам в <tex>S_{jg})</tex> если <tex>i < j</tex> и <tex>e_{i.}</tex> хранится после <tex>S_{i - 1}</tex>, но до <tex>S_{i}</tex>.
Пусть {{Лемма|id = lemma6|about = № 6|statement = <texdpi="130">B[i]n</tex> находится целых чисел можно отсортировать в поднаборе <tex dpi="130">\sqrt{n}</tex> наборов <tex dpi="130">S_{1}</tex>, <tex dpi="130">S_{2}</tex>B[i].subset, <tex dpi="130">\ldots</tex>, <tex dpi="130">S_{\sqrt{n}}</tex>. Чтобы позволить разделению выполнитьсятаким образом, для каждого поднабора помещаем все что в каждом наборе <texdpi="130">B[\sqrt{n}</tex> чисел и <tex dpi="130">S_{i} < S_{j]}</tex> в при <texdpi="130">B[i < j].subset</tex>, за время <tex dpi="150">O(\frac{n \log\log n} {\log k})</tex> и место <tex dpi="130">O(n)</tex> с неконсервативным преимуществом <tex dpi="130">k \log\log n</tex>.
На это потребуется линейное время и место.
|proof =
Алгоритм сортировки <tex dpi="130">n</tex> целых чисел в <tex dpi="130">\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>\log m \ge \log\log\log n</tex>, потому что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log n</tex> хешированных значений (сегментов) в себе на уровне <tex>\log h</tex> в ЭП-дереве. Полное число хешированных бит в контейнере равно <tex>(2 \log n)(c \log\log n)</tex> бит. Хешированные биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i}t_{2} \ldots t_{h/ \log\log n}</tex>, где <tex>t_{k}</tex>-ые — хешированные биты, а нули {{---}} это просто нули. Сначала упаковываем <tex>\log\log n</tex> контейнеров в один Постановка задачи и получаем <tex>w_{1} = 0^{j}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>, где <tex>t_{i, k}</tex>решение некоторых проблем: элемент с номером <tex>k = 1, 2, \ldots, h/ \log\log n</tex> из <tex>i</tex>-ого контейнера. Используем <tex>O(\log\log n)</tex> шагов, чтобы упаковать <tex>w_{1}</tex> в <tex>w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1, h/ \log\log n}t_{2, h/ \log\log n} \ldots t_{\log\log n, h/ \log\log n}</tex>. Теперь упакованные хеш-биты занимают <tex>2 \log n/c</tex> бит. Используем <tex>O(\log\log n)</tex> времени чтобы распаковать <tex>w_{2}</tex> в <tex>\log\log n</tex> контейнеров <tex>w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}0^{r}t_{k, 2} \ldots t_{k, h/ \log\log n} k = 1, 2, \ldots, \log\log n</tex>. Затем, используя <tex>O(\log\log n)</tex> времени, упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1, h/ \log\log n}0^{r}t_{2, 1} \ldots t_{\log\log n, h/ \log\log n}</tex>. Затем, используя <tex>O(\log\log n)</tex> шагов, упаковываем <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>. В итоге используется <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаем, что время, потраченное на один контейнер — константа.
==Уменьшение числа бит в числах==
Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш функция для хеширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.
Рассмотрим проблему сортировки <tex dpi="130">n</tex> целых чисел из множества <tex dpi="130">\{0, 1, \ldots, m - 1\}</tex> в <tex dpi="130">\sqrt{n}</tex> наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <tex dpi="130">k \log\log n \log m</tex> бит и хранит число в <tex dpi="130">\log m</tex> бит. Поэтому неконсервативное преимущество {{---}} <tex dpi="130">k \log \log n</tex>. Также предполагаем, что <tex dpi="130">\log m \geqslant \log n \log\log n</tex>. Иначе можно использовать radix sort для сортировки за время <tex dpi="130">O(n \log\log n)</tex> и линейную память. Делим <tex dpi="130">\log m</tex> бит, используемых для представления каждого числа, в <tex dpi="130">\log n</tex> блоков. Таким образом, каждый блок содержит как минимум <tex dpi="130">\log\log n</tex> бит. <tex dpi="130">i</tex>-ый блок содержит с
<tex dpi="150">\frac{i \log m} {\log n}</tex>-ого по <tex dpi="150">(\frac{(i + 1) \log m} {\log n - 1})</tex>-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex dpi="130">2 \log n</tex>-уровневый алгоритм, который работает следующим образом:
Алгоритм: Пусть целое число <tex>b \ge 0</tex> и пусть <tex>U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хеш-функций из <tex>U</tex> в <tex>\{0, \ldots, 2^s - 1\}</tex> определен как <tex>H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex>x</tex> из <tex>U: h_{a}(x) = (ax</tex> <tex>\bmod</tex> <tex>2^b)</tex> <tex>div</tex> <tex>2^{b - s}</tex>.
Данный алгоритм базируется На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только <tex dpi="150">\frac{\log m}{\log n}</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex dpi="130">\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex dpi="150">\frac{n}{\log n}</tex> контейнеров с <tex dpi="130">\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на '''эту упаковку, считаем, что она бесплатна. По [[#lemma2|лемме №1'№2]] находим медиану этих <tex dpi="130">n</tex> м.ч. за время и память <tex dpi="150">O(\frac{n}{\log n})</tex>. Пусть <tex dpi="130">a</tex> {{---}} это найденная медиана. Тогда <tex dpi="130">n</tex> м.ч. могут быть разделены на не более чем три группы: <tex dpi="130">S_{1}</tex>, <tex dpi="130">S_{2}</tex> и <tex dpi="130">S_{3}</tex>. <tex dpi="130">S_{1}</tex> содержит м.ч., которые меньше <tex dpi="130">a</tex>, <tex dpi="130">S_{2}</tex> содержит м.ч., равные <tex dpi="130">a</tex>, <tex dpi="130">S_{3}</tex> содержит м.ч., большие <tex dpi="130">a</tex>. Также мощность <tex dpi="130">S_{1}</tex> и <tex dpi="130">S_{3} </tex> не превосходит <tex dpi="130">n/2</tex>. Мощность <tex dpi="130">S_{2}</tex> может быть любой. Пусть <tex dpi="130">S'_{2}</tex> {{---}} это набор чисел, у которых наибольший блок находится в <tex dpi="130">S_{2}</tex>. Тогда убираем из дальнейшего рассмотрения <tex dpi="150">\frac{\log m}{\log n}</tex> бит (наибольший блок) из каждого числа, принадлежащего <tex dpi="130">S'_{2}</tex>. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex dpi="130">\log n</tex> блоков, для каждого числа потребуется не более <tex dpi="130">\log n</tex> стадий, чтобы поместить его в набор половинного размера. За <tex dpi="130">2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex dpi="150">\frac{n}{\log n}</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex dpi="130">O(n)</tex> времени из-за <tex dpi="130">2 \log n</tex> стадий.
Взяв Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex dpi="130">n</tex> чисел уже поделены в <tex dpi="130">e</tex>s наборов. Используем <tex dpi= 2 "130">\log ne</tex>, получаем хеш-функцию битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma5|лемме №5]]. Полный размер маркера для каждого контейнера должен быть <texdpi="150">h_\frac{\log n}{a2}</tex>, которая захеширует и маркер использует <texdpi="130">n\log e</tex> чисел из бит, значит количество маркеров <texdpi="130">Ug</tex> в таблицу размера каждом контейнере должно быть не более <texdpi="150">O(\frac{\log n^}{2)\log e}</tex> без коллизий. ОчевидноВ дальнейшем, что так как <texdpi="150">h_g = \frac{\log n}{a2 \log e}(x)</tex> , м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex dpi="130">k \log\log n \log n</tex> блоков, каждое м.ч. может быть посчитана для любого содержать <texdpi="150">xO(\frac{k \log n}{g}) = O(k \log e)</tex> за константное времяблоков. Если упаковать несколько чисел Заметим, что используется неконсервативное преимущество в один контейнер так<tex dpi="130">\log\log n</tex> для [[#lemma5|лемме №5]] Поэтому предполагается, что они разделены несколькими битами нулей, спокойно применяется <texdpi="150">h_\frac{\log n}{a2 \log e}</tex> ко всему контейнерум.ч., а в результате все хеш-значения для всех чисел каждом из которых <tex dpi="130">k \log e</tex> блоков битов числа, упакованны в контейере были посчитаныодин контейнер. Для каждого м.ч. Заметимиспользуется маркер из <tex dpi="130">\log e</tex> бит, который показывает, что это возможно только потомук какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в вычисление хеш-знчения вовлечены только (контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит <texdpi="150">\bmodfrac{\log n}{2 \log e}</tex> маркеров, то для каждого контейнера требуется <texdpi="150">\frac{\log n}{2^b}</tex>) и (бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <texdpi="150">divO(\frac{n \log e}{ \log n})</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <texdpi="150">2^O(\frac{n \log e}{b - s\log n})</tex>).
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma5|леммы №5]].
Такая хеш-функция может быть найдена за <tex>O(n^3)</tex>.
Следует отметить, что, несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex> потому, что хеширование используется только для уменьшения количества бит в числеПри таком помещении сразу возникает следующая проблема.
Рассмотрим число <tex dpi="130">a</tex>, которое является <tex dpi=Signature sorting"130">i</tex>-ым в наборе <tex dpi="130">S</tex>. Рассмотрим блок <tex dpi="130">a</tex> (назовем его <tex dpi=Предположим"130">a'</tex>), что который является <texdpi="130">ni</tex> чисел должны быть сортированы, и -ым м.ч. в каждом <texdpi="130">\log mS</tex> бит. РассматриваетсяКогда используется вышеописанный метод перемещения нескольких следующих блоков <tex dpi="130">a</tex> (назовем это <tex dpi="130">a''</tex>) в <tex dpi="130">S</tex>, что <tex dpi="130">a''</tex> просто перемещен на позицию в каждом числе есть наборе <texdpi="130">hS</tex> сегментов, в каждом из которых но не обязательно на позицию <tex dpi="130">i</tex>\log (mгде расположен <tex dpi="130">a'</htex>). Если значение блока <tex dpi="130">a'</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем одинаково для всех чисел в <tex dpi="130">S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex dpi="130">S</tex> помещен <texdpi="130">2h \log na''</tex> бит хешированных значений для каждого числа. После Иначе у нас возникает проблема дальнейшей сортировки . Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на хешированных значениях общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех начальных чисел начальная задача по сортировке в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <texdpi="130">nk \log e</tex> чисел по блоков {{---}} это текущий блок. Таким образом, после того, как эти <texdpi="130">mk \log e</tex> бит блоков помещены в каждом стала задачей по сортировке набор, изначальный текущий блок удаляется, потому что известно, что эти <texdpi="130">nk \log e</tex> чисел по блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <texdpi="130"> k \log (m/h)e</tex> бит в каждомблоках.
Так жеСтоит отметить, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, <tex>\ldots</tex>, <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Необходимо разделить <tex>S</tex> в <tex>p + 1</tex> что после нескольких уровней деления размер наборов, таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.кстанет маленьким. используется '''signature sorting'''Леммы [[#lemma3|3]], до того как делать вышеописанное разделение[[#lemma4|4]], необходимо поделить биты в <tex>a_{i}</tex> [[#lemma5|5]] расчитаны на <tex>h</tex> сегментов, и взять некоторые из нихне очень маленькие наборы. Так же делим биты для каждого числа Но поскольку сортируется набор из <texdpi="130">Sn</tex> и оставляем только один элементов в каждом числе. По существу для каждого наборы размера <texdpi="130">a_\sqrt{i}</tex> берутся все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{in}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые берутся для числа в <tex>S</tex> {{---}} сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом преобразуется начальная задача о разделении <tex>n</tex> чисел в <tex>\log m</tex> бит в несколько задач на разделение с числами в <tex>\log (m/h)</tex> битпроблем быть не должно.
Пример:===Алгоритм сортировки===
Algorithm <tex>a_{1}Sort(advantage</tex> = 3, <tex>a_{2}level</tex> = 5, <tex>a_{30}</tex> = 7, <tex>a_{41}</tex> = 10, S = <tex>\ldots</tex>, <tex>a_{1, 4, 6, 8, 9, 13, 14\t}</tex>.)
Делим числа на 2 сегмента. Для <tex>a_{1}advantage</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2{---}}</tex> верхний 1, нижний 1; это неконсервативное преимущество равное <tex>a_{3}k\log\log n</tex> верхний 1, нижний 3; <tex>a_{4i}</tex> верхний 2-ые это входящие целые числа в наборе, которые надо отсортировать, нижний 2. Для элементов из S получим: для 1: нижний 1 т.к. он выделяется из нижнего сегмента <tex>a_{1}level</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделениеэто уровень рекурсии.
# Если <tex>level</tex> равен <tex>1</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\leqslant</tex> 3 набора, используя [[#lemma2|лемму №2]], чтобы найти медиану, а затем используем [[#lemma5|лемму №5]] для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.
# От <tex dpi="130">u = 1</tex> до <tex dpi="130">k</tex>
## Упаковываем <tex dpi="130">a^{(u)}_{i}</tex>-ый в часть из <tex dpi="130">1/k</tex>-ых номеров контейнеров. Где <tex dpi="130">a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex dpi="150">\frac{1}{k}</tex>-ых битов <tex dpi="130">a_{i}</tex>. При этом у <tex dpi="130">a^{(u)}_{i}</tex> текущий блок это самый крупный блок.
## Вызываем <tex>Sort(advantage</tex>, <tex>level - 1</tex>, <tex dpi="130">a^{(u)}_{0}</tex>, <tex dpi="130">a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex dpi="130">a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это число относится, уже направлен назад к месту, где число находится во входных данных. Число, имеющее наибольшее число бит в <tex dpi="130">a_{i}</tex>, показывающее на текущий блок в нем, так же направлено назад к <tex dpi="130">a_{i}</tex>.
## Отправляем <tex dpi="130">a_{i}</tex>-ые к их наборам, используя [[#lemma5|лемму №5]].
Использование '''signature sorting''' в данном алгоритме:Algorithm IterateSortCall <tex>Sort(advantage</tex>, <tex dpi="130">\log_{k}((\log n)/4)</tex>, <tex dpi="130">a_{0}</tex>, <tex dpi="130">a_{1}</tex>, <tex dpi="130">\ldots</tex>, <tex dpi="130">a_{n - 1}</tex>);
Предположим, у есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как от 1 до 5# Помещаем <texdpi="130">a_{1}, a_{2}, \ldots, a_{pi}</tex>в соответствующий набор с помощью блочной сортировки (англ. ''bucket sort''), и хотется использовать числа в <tex>T</tex> для разделения потому что наборов около <texdpi="130">S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_sqrt{qn}</tex> в .# Для каждого набора <texdpi="130">p + 1S = </tex> наборов {<texdpi="130">S_a_{i_{0}}, S_a_{i_{1}}, \ldots, S_a_{p}</tex> что <tex>S_i_{0t}</tex> < {<tex>a_{1}</tex>} < , если <texdpi="130">S_{1}</tex> < <text >\ldots</tex> < sqrt{<tex>a_{pn}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть , вызываем <tex>h = \log n/Sort(c \log p)</tex> для константы <tex>c > 1advantage</tex>. <tex>h/ \log\log n \log p</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <texdpi="130">(\log n)/log_{k}(c \logfrac{\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i4})</tex> как сегменты одинаковой длины <tex>h/ \log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, хешируются числа в этих контейнерах (<texdpi="130">a_{ii_{0}</tex>-ом и <tex>b_{i}</tex>-ом), чтобы получить <tex>h/ \log\log n</tex> хешированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяются в один. Пусть <tex>a'_a_{i}</tex> хеш-контейнер для <tex>a_i_{i1}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хеш-значения имеют <tex>(2 \log n)/(c \log\log n)</tex> бит. Хотя эти значения разделены на сегменты по <tex>h/ \log\log n</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex>(2 \log n)/(c \log\log n)</tex> бит. Потом рассматриваются каждый хеш-контейнер как число и сортируются эти хеш-контейнеры за линейное время (сортировка рассмотрена чуть позже). После этой сортировкиldots, биты в <tex>a_{ii_{t}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex>. Таким образом, получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).
После того, как повторится вышеописанный процесс <tex>g</tex> раз, получится неконсервативное преимущество в Время работы алгоритма <texdpi="150">O(h/ \frac{n \log\log n}{\log k})^g</tex> раз, в то время, как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся за линейное время <tex>O(qt)</tex>что доказывает лемму.}}
Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, которые <tex>\log\log n/h</tex>-ые, <tex>(\log\log n/h)^2</tex>-ые, <tex>\ldots</tex> от всего числа. Для сегментов вида <tex>(\log\log n/h)^t</tex>, получаем нарезанием всех <tex>p</tex> чисел на <tex>(\log\log n/h)^t</tex> сегментов. Рассматривая каждый сегмент как число, получится <tex>p(\log\log n/h)^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex>t < \log n</tex> то, получится не более <tex>\log n</tex> хеш-функций.
==Уменьшение числа бит в числах==
Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex dpi="130">O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex dpi="130">O(n)</tex>. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования <tex dpi="130">n</tex> чисел в таблицу размера <tex dpi="130">O(n^2)</tex> за константное время без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.
Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упаковались в <tex>(2 \log n)/(c \log\log n)</tex> бит. Есть <tex>t</tex> наборов в каждом из которых <tex>q + p</tex> хешированных контейнеров по <tex>(2 \log n)/(c \log\log n)</tex> бит в каждом. Эти числа должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.
==Лемма №1==Даны целые числа Алгоритм: Пусть целое число <texdpi="130">b\geqslant 0</tex> и пусть <texdpi="130">U = \{0, \ldots, 2^b - 1\ge}</tex> . Класс <texdpi="130">H_{b,s}</tex> хеш-функций из <texdpi="130">\geU</tex> 0 и <tex>T</tex> является подмножеством в <texdpi="130">\{0, \ldots, 2^b s - 1\}</tex>, содержащим определен как <texdpi="130">n</tex> элементовH_{b, и s} = \{h_{a} \mid 0 <tex>ta </tex> <tex>2^b, a \equiv 1 (\bmod 2)\ge}</tex> и для всех <texdpi="130">2^{-s + 1}x</tex>Сиз <texdpi="130">^k_{n}U</tex>. Функция : <texdpi="130">h_{a}(x) = (ax</tex> принадлежащая <texdpi="130">H_{b,s}\bmod</tex> может быть выбрана за время <texdpi="130">O(bn2^2b)</tex> так, что количество коллизий <texdpi="130">coll(h_{a}, T)div</tex> <texdpi="130">\le</tex> t2^{b - s}</tex>.
==Лемма №2==<tex>n</tex> целых чисел можно отсортировать в <tex>\sqrt{n}</tex> наборов <tex>S_{1}</tex>, <tex>S_{2}</tex>, <tex>\ldots</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(n \log\log n/ \log k)</tex> и место <tex>O(n)</tex> с не консервативным преимуществом <tex>k \log\log n</tex>Данный алгоритм базируется на [[#lemma1|лемме №1]].
Доказательство:Взяв <tex dpi="130">s = 2 \log n</tex>, получаем хеш-функцию <tex dpi="130">h_{a}</tex>, которая захеширует <tex dpi="130">n</tex> чисел из <tex dpi="130">U</tex> в таблицу размера <tex dpi="130">O(n^2)</tex> без коллизий. Очевидно, что <tex dpi="130">h_{a}(x)</tex> может быть посчитана для любого <tex dpi="130">x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <tex dpi="130">h_{a}</tex> ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<tex dpi="130">\bmod</tex> <tex dpi="130">2^b</tex>) и (<tex dpi="130">div</tex> <tex dpi="130">2^{b - s}</tex>).
Алгоритм сортировки <tex>n</tex> целых чисел в <tex>\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.
Такая хеш-функция может быть найдена за <tex dpi==Сортировка n целых чисел в sqrt"130">O(n^3) наборов==Постановка задачи и решение некоторых проблем:</tex>.
Следует отметить, что, несмотря на размер таблицы <tex dpi="130">O(n^2)</tex>, потребность в памяти не превышает <tex dpi="130">O(n)</tex>, потому что хеширование используется только для уменьшения количества бит в числе.
Рассмотрим проблему сортировки ==Сортировка по ключу==Предположим, что <texdpi="130">n</tex> целых чисел из множества <tex>\{0должны быть отсортированы, 1, \ldots, m - 1\}</tex> и в каждом <texdpi="130">\sqrt{n}log m</tex> наборов, как в '''лемме №2'''бит. ПредполагаяБудем считать, что в каждом контейнере числе есть <texdpi="130">k \log\log n \log mh</tex> бит и хранит число сегментов, в каждом из которых <texdpi="130">\log m</tex> бит. Поэтому неконсервативное преимущество <texdpi="150">k \log \log nfrac{m}{h}</tex>бит. Так же предполагаем, что Теперь применяем хеширование ко всем сегментам и получаем <texdpi="130">\log m \ge \log n \log2h \log n</tex>бит хешированных значений для каждого числа. Иначе можно использовать radix sort После сортировки на хешированных значениях для сортировки за время всех начальных чисел начальная задача по сортировке <texdpi="130">O(n \log\log n)</tex> и линейную память. Делим чисел по <texdpi="130">\log m</tex> бит, используемых для представления каждого числа, в каждом стала задачей по сортировке <texdpi="130">\log n</tex> блоков. Таким образом каждый блок содержит как минимум чисел по <texdpi="130">\log\log n</tex> бит. <texdpi="150">i</tex>-ый блок содержит с <tex>i \log frac{m/ \log n}{h}</tex>-ого по <tex>((i + 1) \log m/ \log n - 1)</tex>-ый битыбит в каждом. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex>2 \log n</tex>-уровневый алгоритм, который работает следующим образом:
На каждой стадии работаем с одним блоком битТакже рассмотрим проблему последующего разделения. Назовем эти блоки маленькими числами (далее м.ч.) потому, что каждое м.ч. теперь содержит только Пусть <texdpi="130">\log m/ \log na_{1}</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самыми большим блоком (блок номер <texdpi="130">\log n - 1a_{2}</tex>). Предполагаем, что биты этих м.ч. упакованы в <texdpi="130">n/ \log nldots</tex> контейнеров с , <texdpi="130">\log na_{p}</tex> м.ч. упакованных в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считается, что она бесплатна. По '''лемме №3''' находим медиану этих {{---}} <texdpi="130">np</tex> м.ч. за время чисел и память <texdpi="130">O(n/ \log n)S</tex>{{---}} множество чисeл. Пусть Необходимо разделить <texdpi="130">aS</tex> это найденная медиана. Тогда в <texdpi="130">np + 1</tex> м.ч. могут быть разделены на не более чем три группынаборов, таких, что: <texdpi="130">S_{0} < a_{1}</tex>, <tex>S_{21}</tex> и <tex>S_a_{32}</tex>. \ldots <tex>S_a_{1p}</tex> содержит м.ч. которые меньше <tex>a</tex>, <tex>S_{2p}</tex> содержит м.чТак как используется '''сортировка по ключу''' (англ. равные <tex>a</tex>''signature sorting'') то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <texdpi="130">S_a_{3i}</tex> содержит м.ч. большие на <texdpi="130">ah</tex>сегментов и взять некоторые из них. Так же мощность делим биты для каждого числа из <texdpi="130">S_{1}S</tex> и оставляем только один в каждом числе. По существу, для каждого <texdpi="130">S_a_{3i} </tex> {{---}} берутся все <texdpi="130">n/2h</tex>сегментов. Мощность Если соответствующие сегменты <texdpi="130">S_a_{2i}</tex> может быть любой. Пусть и <texdpi="130">S'_a_{2j}</tex> это набор чиселсовпадают, то нам понадобится только один. Сегмент, у которых наибольший блок находится который берется для числа в <texdpi="130">S_{2}S</tex>. Тогда убираем <tex>\log m/ \log n</tex> бит (наибольший блок) это сегмент, который выделяется из каждого числа, принадлежащего <texdpi="130">S'_a_{2i}</tex>, из дальнейшего рассмотрения. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только начальная задача о разделении <texdpi="130">\log n</tex> блоков, для каждого числа потребуется не более чисел по <texdpi="130">\log nm</tex> стадий, чтобы поместить его бит преобразуется в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированы. Так как несколько задач на каждой стадии работаем разделение с числами по <texdpi="150">n/ \log n</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex>O(n)</tex> времени из-за <tex>2 frac{\log nm}{h}</tex> стадийбит.
Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать '''лемму №6'''. Полный размер маркера для каждого контейнера должен быть <tex>\log n/2</tex>, и маркер использует <tex>\log e</tex> бит, количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>\log n/(2\log e)</tex>. В дальнейшем т.к. <tex>g = \log n/(2 \log e)</tex> м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <tex>O(k \log n/g) = O(k \log e)</tex> блоков. Заметим, что используем неконсервативное преимущество в <tex>\log\log n</tex> для использования '''леммы №6'''. Поэтому предполагается, что <tex>\log n/(2 \log e)</tex> м.ч. в каждом из которых <tex>k \log e</tex> блоков битов числа упакованный в один контейнер. Для каждого м.ч. используется маркер из <tex>\log e</tex> бит, который показывает к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит <tex>\log n/(2 \log e)</tex> маркеров, то для каждого контейнера требуется <tex>(\log n)/2</tex> бит. Таким образом, '''лемма №6Пример''' может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров то время необходимое для помещения м.ч. в их наборы потребуется <tex>O((n \log e)/ \log n)</tex> времени:[[Файл:Han-example.png|500px|thumb]]
Стоит отметить<tex dpi="130">a_{1} = 3, что процесс помещения нестабиленa_{2} = 5, т.к. основан на алгоритме из '''леммы №6'''a_{3} = 7, a_{4} = 10, S = \{1, 4, 6, 8, 9, 13, 14\}</tex>.
Делим числа на два сегмента. Для <tex dpi="130">a_{1}</tex> получим верхний сегмент <tex dpi="130">0</tex>, нижний <tex dpi="130">3</tex>; <tex dpi="130">a_{2}</tex> {{---}} верхний <tex dpi="130">1</tex>, нижний <tex dpi="130">1</tex>; <tex dpi="130">a_{3}</tex> {{---}} верхний <tex dpi="130">1</tex>, нижний <tex dpi="130">3</tex>; <tex dpi="130">a_{4}</tex> {{---}} верхний <tex dpi="130">2</tex>, нижний <tex dpi="130">2</tex>. Для элементов из S получим: для <tex dpi="130">1</tex> нижний <tex dpi="130">1</tex>, так как он выделяется из нижнего сегмента <tex dpi="130">a_{1}</tex>; для <tex dpi="130">4</tex> нижний <tex dpi="130">0</tex>; для <tex dpi="130">8</tex> нижний <tex dpi="130">0</tex>; для <tex dpi="130">9</tex> нижний <tex dpi="130">1</tex>; для <tex dpi="130">13</tex> верхний <tex dpi="130">3</tex>; для <tex dpi="130">14</tex> верхний <tex dpi="130">3</tex>. Теперь все верхние сегменты, нижние сегменты <tex dpi="130">1</tex> и <tex dpi="130">3</tex>, нижние сегменты <tex dpi="130">4, 5, 6, 7,</tex> нижние сегменты <tex dpi="130">8, 9, 10</tex> формируют <tex dpi="130">4</tex> новые задачи на разделение.
При таком помещении сразу возникает следующая проблема.
Рассмотрим число <tex>a</tex>, которое является <tex>i</tex>-ым в наборе <tex>S</tex>. Рассмотрим блок <tex>a</tex> (назовем его <tex>a'</tex>), который является <tex>i</tex>-ым м.ч. в <tex>S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex>a</tex> (назовем это <tex>a''</tex>) в <tex>S</tex>, <tex>a''</tex> просто перемещен на позицию в наборе <tex>S</tex>, но не обязательно на позицию <tex>i</tex> (где расположен <tex>a'</tex>). Если значение блока <tex>a'</tex> одинаково для всех чисел в <tex>S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex>S</tex> помещен <tex>a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, помещаются последующие блоки вместе с текущим блоком в набор. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex>k \log e</tex> блоков это текущий блок. Таким образом, после того, как помещены эти <tex>k \log e</tex> блоков в набор, удаляется изначальный текущий блок, потому, что известно, что эти <tex>k \log e</tex> блоков перемещены в правильный набор и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex>k \log e</tex> блоках.
Использование '''сортировки по ключу''' в данном алгоритме:
Стоит отметитьЕсть набор <tex dpi="130">T</tex> из <tex dpi="130">p</tex> чисел, которые отсортированы как <tex dpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex>. Используем числа в <tex dpi="130">T</tex> для разделения набора <tex dpi="130">S</tex> из <tex dpi="130">q</tex> чисел <tex dpi="130">b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex dpi="130">p + 1</tex> наборов <tex dpi="130">S_{0}, S_{1}, \ldots, S_{p}</tex>. Пусть <tex dpi="150">h = \frac{\log n}{c \log p}</tex> для константы <tex dpi="130">c > 1</tex>. (<tex dpi="150">\frac{h}{\log\log n \log p}</tex>)-битные числа могут храниться в одном контейнере, содержащим <tex dpi="150">\frac{\log n}{c \log\log n}</tex> бит. Сначала рассматриваем биты в каждом <tex dpi="130">a_{i}</tex> и каждом <tex dpi="130">b_{i}</tex> как сегменты одинаковой длины <tex dpi="150">\frac{h} {\log\log n}</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (<tex dpi="130">a_{i}</tex>-ом и <tex dpi="130">b_{i}</tex>-ом) хешируются, и получается <tex dpi="150">\frac{h}{\log\log n}</tex> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что после нескольких уровней деления размер наборов станет маленькимхеш-значения считаются за константное время. '''Леммы №4Затем, №5посчитав значения, №6два контейнера объединяем в один. Пусть <tex dpi="130">a'_{i}</tex> {{---}} хеш-контейнер для <tex dpi="130">a_{i}</tex>, аналогично <tex dpi="130">b'' расчитаны _{i}</tex>. В сумме хеш-значения имеют <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, хотя эти значения разделены на не очень маленькие наборысегменты по <tex dpi="150">\frac{h}{ \log\log n}</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Но поскольку сортируется набор из Сначала упаковываются все сегменты в <texdpi="150">\frac{2 \log n}{c \log\log n}</tex> элементов бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в наборы размера <texdpi="130">a_{i}</tex> и <tex dpi="130">b_{i}</tex> разрезаны на <tex dpi="150">\sqrtfrac{\log\log n}{h}</tex>сегментов. Таким образом, то проблем не должно бытьполучилось дополнительное мультипликативное преимущество (англ. ''additional multiplicative advantage'') в <tex dpi="150">\frac{h} {\log\log n}</tex>.
После того, как вышеописанный процесс повторится <tex dpi="130">g</tex> раз, получится неконсервативное преимущество в <tex dpi="150">(\frac{h} {\log\log n})^g</tex> раз, в то время как потрачено только <tex dpi="130">O(gqt)</tex> времени, так как каждое многократное деление происходит за линейное время <tex dpi="130">O(qt)</tex>.
Собственно алгоритм:
Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, <tex dpi="150">\frac{\log\log n}{h}</tex>-ые, <tex dpi="150">(\frac{\log\log n}{h})^2</tex>-ые, <tex dpi="130">\ldots</tex> по счету в числе. Хеш-функцию для <tex dpi="150">(\frac{\log\log n}{h})^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex dpi="130">p</tex> чисел на <tex dpi="150">(\frac{\log\log n}{h})^t</tex> сегментов. Рассматривая каждый сегмент как число, получаем <tex dpi="150">p(\frac{\log\log n}{h})^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex dpi="130">t < \log n</tex>, то получится не более <tex dpi="130">\log n</tex> хеш-функций.
Algorithm Sort(<tex>k \log\log n</tex>, <tex>level</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{t}</tex>)
Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <texdpi="150">k \frac{2 \log n}{c \log\log n}</tex> это неконсервативное преимуществобит. Есть <tex dpi="130">t</tex> наборов, в каждом из которых <texdpi="130">a_{i}q + p</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, хешированных контейнеров по <texdpi="150">level\frac{2 \log n}{c \log\log n}</tex> это уровень рекурсиибит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.
# <tex>if level == 1</tex> тогда изучить размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе разделить этот набор в <tex>\le</tex> 3 набора используя '''лемму №3''', чтобы найти медиану, а затем использовать '''лемму №6''' для сортировки. Для набора, где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</tex>.
# От <tex>u = 1</tex> до <tex>k</tex>
## Упаковать <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров, где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>-ых битов <tex>a_{i}</tex> и у которого текущий блок это самый крупный блок.
## Вызвать Sort(<tex>k \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данных. Число, имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на ткущий блок в нем, так же отправлено назад к <tex>a_{i}</tex>.
## Отправить <tex>a_{i}-ые к их наборам, используя '''лемму №6'''.</tex>
endОперация '''сортировки за линейное время''' (англ.''Linear-Time-Sort'')
Входные данные: <tex dpi="150">r \geqslant n^{\frac{2}{5}}</tex> чисел <tex dpi="130">d_{i}</tex>, <tex dpi="130">d_{i}.value</tex> — значение числа <tex dpi="130">d_{i}</tex>, в котором <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, <tex dpi="130">d_{i}.set</tex> — набор, в котором находится <tex dpi="130">d_{i}</tex>. Следует отметить, что всего есть <tex dpi="130">t</tex> наборов.
Algorithm IterateSortCall Sort(# Сортируем все <texdpi="130">k \log\log nd_{i}</tex>, по <texdpi="130">\log_d_{ki}((\log n)/4).value</tex>, используя bucket sort. Пусть все отсортированные числа в <texdpi="130">a_{0}A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <texdpi="150">a_n^{1\frac{2}{5}}</tex>, чисел.# Помещаем все <texdpi="130">\ldotsA[j]</tex>, в <texdpi="130">a_{n - 1}A[j].set</tex>);.
от 1 до 5# Поместить <tex>a_{i}</tex> в соответствующий набор ==Сортировка с помощью bucket sort потому, что наборов около <tex>\sqrt{использованием O(n log log n}</tex>) времени и памяти==# Для каждого набора сортировки <texdpi="130">S = n</tex>{целых чисел в диапазоне <texdpi="130">a_{i_\{0}}, a_{i_{1}}, \ldots, a_{i_{t}m - 1\}</tex>}предполагается, если что в нашем консервативном алгоритме используется контейнер длины <texdpi="130">t > sqrt{n}</tex>, вызвать SortO(<tex>k \log\log n</tex>, <tex>\log_{k}((\log m + n)/4)</tex>. Далее везде считается, <tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>)что все числа упакованы в контейнеры одинаковой длины.
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает '''лемму №2'''.
Берем <tex dpi="130">1/e =Лемма №35</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex dpi="150">n^{\frac{1}{5}}</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь <tex dpi="150">n^{\frac{4}{5}}</tex> листьев. В отличие от оригинального дерева, за раз вставляется не один элемент, а <tex dpi=Выбор "130">d^2</tex>s, где <tex dpi="130">d</tex>-ого наибольшего — количество детей узла дерева, в котором числа среди должны спуститься вниз. Алгоритм полностью опускает все <texdpi="130">d^2</tex> чисел на один уровень. В корне опускаются <tex dpi="150">n^{\frac{2}{5}}</tex> чисел упакованных на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <tex dpi="130">t_{1} = n^{1/5}</tex> наборов <tex dpi="130">S_{1}, S_{2}, \ldots, S_{t_{1}}</tex>, в каждом из которых <texdpi="150">n^{\frac{4}{5}}</gtex> чисел и <tex dpi="130">S_{i} < S_{j}, i < j</tex> контейнеров может быть сделана за . Затем, берутся <texdpi="150">O(n ^{\log gfrac{8}{25}}</g)tex> чисел из <tex dpi="130">S_{i}</tex> время и с использованием опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <texdpi="150">O(t_{2} = n^{\frac{1}{5}}n^{\frac{4}{25}} = n^{\frac{9}{25}}</tex> наборов <tex dpi="130">T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>, аналогичных наборам <tex dpi="130">S_{i}</g)tex>, в каждом из которых <tex dpi="150">n^{\frac{16}{25}}</tex> местачисел. Конкретно медиана может быть так найденаТеперь числа опускаются дальше в ЭП-дереве.
Нетрудно заметить, что перебалансирока занимает <tex dpi="130">O(n \log\log n)</tex> времени с <tex dpi="130">O(n)</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссона.
Доказательство:
Так как возможно делать попарное сравнение <tex>g</tex> чисел в одном контейнере Нам следует нумеровать уровни ЭП-дерева с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второгокорня, начиная с нуля. Рассмотрим спуск вниз на уровне <texdpi="130">\ldotss</tex>, . Имеется <texdpi="150">g</tex>t = n^{1 -ого чисел из (\frac{4}{5 контейнеров в один контейнер за константное время. Таким образом, набор <tex>})^S}</tex> из медиан теперь содержится в наборов по <texdpi="150">n/^{(5g\frac{4}{5})^S}</tex> контейнерахчисел в каждом. Рекурсивно находим медиану <tex>m</tex> в Так как каждый узел на данном уровне имеет <texdpi="150">p = n^{\frac{1}{5} \cdot (\frac{4}{5})^S}</tex>. Используя детей, то на <texdpi="130">ms + 1</tex>, уберем, хотя бы, уровень опускаются <texdpi="150">q = n/^{\frac{2}{5} \cdot (\frac{4}{5})^S}</tex> чисел среди для каждого набора, или всего <texdpi="150">qt \geqslant n^{\frac{2}{5}}</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсиючисел для всех наборов за один раз.
==Лемма №4==
Если <tex>g</tex> целых чисел, в сумме использующие <tex>(\log n)/2</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы за время <tex>O((n/g) \log g)</tex>, с использованием <tex>O(n/g)</tex> места.
Спуск вниз можно рассматривать как сортировку <tex dpi="130">q</tex> чисел в каждом наборе вместе с <tex dpi="130">p</tex> числами <tex dpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <tex dpi="130">q</tex> чисел разделены в <tex dpi="130">p + 1</tex> наборов <tex dpi="130">S_{0}, S_{1}, \ldots, S_{p}</tex> таких, что <tex dpi="130">S_{0} < a_{1} < \ldots < a_{p} < S_{p}</tex>.
Доказательство:
Так как используется только <tex>(\log n)/2</tex> бит в каждом контейнере для хранения <texdpi="130">gq</tex> чисел, используем bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <tex>O(n/g)</tex> времени не надо полностью сортировать и места. Так как используется <texdpi="130">(\log n)/q = p^2</tex> бит на контейнер, понадобится <tex>\sqrt{n}</tex> шаблонов то можно использовать [[#lemma6|лемму №6]] для всех контейнеровсортировки. Затем поместим <tex>g < (\log n)/2</tex> контейнеров Для этого необходимо неконсервативное преимущество, которое получается с одинаковым шаблоном в одну группупомощью [[Сортировка Хана#Signature sorting|signature sorting]]. Для каждого шаблона останется не более <tex>g - 1</tex> контейнеров, которые не смогут образовать группу. Поэтому не более <tex>\sqrt{n}этого используется линейная техника многократного деления (g - 1)</tex> контейнеров не смогут сформировать группуангл. Для каждой группы помещаем <tex>i</tex>''multi-е число во всех <tex>g</tex> контейнерах в один. Таким образом берутся <tex>g</tex> <tex>g</tex>-целых векторов и получаем <tex>g</tex> <tex>g</tex>-целых векторов где <tex>i</tex>-ый вектор содержит <tex>i</tex>-ое число из входящего вектора. Эта транспозиция может быть сделана за время <tex>O(g \log g)</tex>, с использованием <tex>O(gdividing technique'')</tex> места. Для всех групп это занимает время <tex>O((n/g) \log g)</tex>, с использованием <tex>O(n/g)</tex> места.
Для контейнеров вне групп (которых <tex>\sqrt{n}(g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex>O(n/g)</tex> места и времени. После всего этого используем bucket sorting вновь для сортировки <tex>n</tex> контейнеров. таким образом все числа отсортированы.
После <tex dpi="130">g</tex> сокращений бит в [[Сортировка Хана#Signature sorting|signature sorting]] получаем неконсервативное преимущество в <tex dpi="150">(\frac{h}{ \log\log n})^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на [[#lemma6|лемму №6]] для завершения разделения <tex dpi="130">q</tex> чисел с помощью <tex dpi="130">p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex dpi="130">w</tex> подзадач разделения на <tex dpi="130">w</tex> поднаборов для какого-то числа <tex dpi="130">w</tex>.
Заметим, что когда <tex>g = O( \log n)</tex> сортировка <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров произойдет за время <tex>O((n/g) \log\log n)</tex>, с использованием O(n/g) места. Выгода очевидна.
==Лемма №5==
Если принять, что каждый контейнер содержит <tex> \log m > \log n</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((n \log\log n)/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>-ом контейнере для маркеров.
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя [[#lemma6|лемму №6]], делается разделение. Так как получено неконсервативное преимущество в <tex dpi="150">(\frac{h}{\log\log n})^g</tex> и работа происходит на уровнях не ниже, чем <tex dpi="130">2 \log\log\log n</tex>, то алгоритм занимает <tex dpi="150">O(\frac{qt \log\log n}{g(\log h - \log\log\log n) - \log\log\log n}) = O(\log\log n)</tex> времени.
Доказательство:
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потомуВ итоге разделились <tex dpi="130">q</tex> чисел <tex dpi="130">p</tex> числами в каждый набор. То есть получилось, что каждый контейнер использует <texdpi="130">( S_{0} < e_{1} < S_{1} < \log n)ldots < e_{p} < S_{p}</2tex>, где <tex dpi="130">e_{i}</tex> {{---}} сегмент <tex dpi="130">a_{i}</tex> бит, полученный с помощью битового сокращения. Сортировка сгруппирует контейнеры для чисел как Такое разделение получилось комбинированием всех поднаборов в '''лемме №4'''подзадачах. Перемещаем каждую группу контейнеров для чиселПредполагаем, что числа хранятся в массиве <tex dpi="130">B</tex> так, что числа в <tex dpi="130">S_{i}</tex> предшествуют числам в <tex dpi="130">S_{j}</tex> если <tex dpi="130">i < j</tex> и <tex dpi="130">e_{i}</tex> хранится после <tex dpi="130">S_{i - 1}</tex>, но до <tex dpi="130">S_{i}</tex>.
==Лемма №6==
предположим, что каждый контейнер содержит <tex>\log m \log\log n > \log n</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)</tex>, с использованием <tex>O(n/g)</tex> памяти.
Пусть <tex dpi="130">B[i]</tex> находится в поднаборе <tex dpi="130">B[i].subset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <tex dpi="130">B[j]</tex> в <tex dpi="130">B[j].subset</tex>.
Доказательство:На это потребуется линейное время и место.
Заметим, что несмотря на то, что длина контейнера <tex>\log m \log\log n</tex> бит всего <tex>\log m</tex> бит используется для хранения упакованных чисел. Так же как в '''леммах №4, №5''' сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел помещаем <tex>g \log\log n</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex>g \log\log n</tex> контейнеров, упаковываем <tex>g \log\log n</tex> контейнеров в <tex>g</tex>, упаковывая <tex>\log\log n</tex> контейнеров в один. Далее делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(g \log\log n)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, распаковываем <tex>g</tex> контейнеров в <tex>g \log\log n</tex> контейнеров.
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex dpi="130">\log m \geqslant \log\log\log n</tex>, потому что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex dpi="150">\frac{h}{\log\log n}</tex> хешированных значений (сегментов) в себе на уровне <tex dpi="130">\log h</tex> в ЭП-дереве. Полное число хешированных бит в контейнере равно <tex dpi="130">(2 \log n)(c \log\log n)</tex> бит. Хешированные биты в контейнере выглядят как <tex dpi="130">0^{i}t_{1}0^{i}t_{2} \ldots t</tex><tex dpi="150">_{\frac{h}{\log\log n}}</tex>, где <tex dpi="130">t_{k}</tex>-ые — хешированные биты, а нули {{---}} это просто нули. Сначала упаковываем <tex dpi="130">\log\log n</tex> контейнеров в один и получаем <tex dpi="130">w_{1} = 0^{j}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>, где <tex dpi="130">t_{i, k}</tex>: элемент с номером <tex dpi="130">k = 1, 2, \ldots, </tex><tex dpi="150">\frac{h}{\log\log n}</tex> из <tex dpi="130">i</tex>-ого контейнера. Используем <tex dpi="130">O(\log\log n)</tex> шагов, чтобы упаковать <tex dpi="130">w_{1}</tex> в <tex dpi="130">w_{2} = 0</tex><tex dpi="150">^{\frac{jh}{\log\log n}}</tex><tex dpi="130">t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">t_{2,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">\ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>. Теперь упакованные хеш-биты занимают <tex dpi="130">2 \log</tex><tex dpi="150">\frac{n}{c}</tex> бит. Используем <tex dpi="130">O(\log\log n)</tex> времени чтобы распаковать <tex dpi="130">w_{2}</tex> в <tex dpi="130">\log\log n</tex> контейнеров <tex dpi="130">w_{3, k} = 0</tex><tex dpi="150">^{\frac{jh}{\log\log n}}</tex><tex dpi="130">0^{r}t_{k, 1}0^{r}t_{k, 2} \ldots t_{k,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex> <tex dpi="130">k = 1, 2, \ldots, \log\log n</tex>. Затем, используя <tex dpi="130">O(\log\log n)</tex> времени, упаковываем эти <tex dpi="130">\log\log n</tex> контейнеров в один <tex dpi="130">w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">0^{r}t_{2, 1} \ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>. Затем, используя <tex dpi="130">O(\log\log n)</tex> шагов, упаковываем <tex dpi="130">w_{4}</tex> в <tex dpi="130">w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">t_{2, 1}t_{2, 2} \ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>. В итоге используется <tex dpi="130">O(\log\log n)</tex> времени для упаковки <tex dpi="130">\log\log n</tex> контейнеров. Считаем, что время, потраченное на один контейнер — константа.
Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \le \log n</tex> чисел в один контейнер, тогда выбор в '''лемме №3''' может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве '''леммы №3''' теперь может быть сделана за время <tex>O(n/g)</tex>==См.также==* [[Сортировка подсчетом]]* [[Цифровая сортировка]]
==ЛитераураИсточники информации==# * [http://www.sciencedirect.com/science/article/pii/S019667740300155X Deterministic Sorting in O(n \log\log n) Time and Linear Space. Yijie Han.]# * А. Андерссон. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science. 135-141(1996)* [http://dl.acm.org/citation.cfm?id=1236460 A. Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.]* [[wikipedia:en:Integer_sorting|Wikipedia {{---}} Integer sorting]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкиСортировка]]
25
правок

Навигация