Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 5 участников)
Строка 1: Строка 1:
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(n \log\log n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
+
'''Сортировка Хана''' (англ. ''Hansort'') {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex dpi="130">O(n \log\log n)</tex>, где <tex dpi="130">n</tex> {{---}} количество элементов для сортировки.
  
Данная статья писалась на основе брошюры Хана, посвященной этой сортировке.
+
Данная статья писалась на основе брошюры Хана (англ. ''Yijie Han''), посвященной этой сортировке.
  
 
== Описание ==
 
== Описание ==
Алгоритм построен на основе экспоненциального поискового дерева (далее {{---}} ЭП-дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в ЭП-дерево.
+
Алгоритм построен на основе '''экспоненциального поискового дерева Андерсона''' (англ. ''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> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.
 
  
==Определения==
+
{{Определение
# Контейнер {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.
+
|definition = '''ЭП-дерево''' {{---}} это дерево поиска, в котором все ключи хранятся в листьях этого дерева и количество детей у каждого узла уменьшается экспоненциально от глубины узла.
# Алгоритм, сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex>, называется консервативным, если длина контейнера (число бит в контейнере) равна <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.
+
}}
# Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с неконсервативным преимуществом <tex>k</tex>.
+
 
# Для множества <tex>S</tex> определим
+
[[Файл:Exp-tree.png|400px|thumb|right|Общая структура ЭП-дерева]]
 +
 
 +
Структура ЭП-дерева:
  
<tex>\min(S) = \min\limits_{a \in S} a</tex>  
+
1) Корень имеет <tex dpi="130">\Theta (n^e)</tex> сыновей <tex dpi="130">( 0 < e < 1 )</tex>. Все сыновья являются ЭП-деревьями.
  
<tex>\max(S) = \max\limits_{a \in S} a</tex>
+
2) Каждое поддерево корня имеет <tex dpi="130">\Theta(n^{1-e})</tex> сыновей.
  
Набор <tex>S1</tex> < <tex>S2</tex> если <tex>\max(S1) \le \min(S2)</tex>
+
В этом дереве <tex dpi="130">O(n \log\log n)</tex> уровней. При нарушении баланса дерева необходимо балансирование, которое требует <tex dpi="130">O(n \log\log n)</tex> времени при <tex dpi="130">n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.
# Предположим, есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>, и хочется использовать числа в <tex>T</tex> для разделения набора <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex>, таких что <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами.
 
  
==Сортировка с использованием O(n log log n) времени и памяти==
+
==Определения==
Для сортировки <tex>n</tex> целых чисел в диапазоне {<tex>0, 1, \ldots, m - 1</tex>} предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex>O(\log (m + n))</tex>. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.  
+
{{ Определение | definition =
 +
'''Контейнер''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.}}
 +
{{ Определение | definition =
 +
Алгоритм, сортирующий <tex dpi="130">n</tex> целых чисел из множества <tex dpi="130">\{0, 1, \ldots, m - 1\}</tex>, называется '''консервативным''', если длина контейнера (число бит в контейнере) равна <tex dpi="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 = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex>n^{1/5}</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} = n^{1/5}</tex> наборов <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^{(4/5)(2/5)}</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> чисел. Теперь числа опускаются дальше в ЭП-дереве.
+
Набор <tex dpi="130">S1 < S2</tex> если <tex dpi="130">\max(S1) \leqslant \min(S2)</tex>
 +
}}
  
Нетрудно заметить, что перебалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(n)</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссона.
+
{{ Определение | definition =
 +
Предположим, есть набор <tex dpi="130">T</tex> из <tex dpi="130">p</tex> чисел, которые уже отсортированы как <tex dpi="130">a_{1}, a_{2}, \ldots, a_{p}</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">q</tex> чисел <tex dpi="130">p</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} < S_{1} < \ldots < a_{p} < S_{p}</tex>.
 +
}}
  
 +
==Леммы==
  
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <tex>s</tex>. Имеется <tex>t = n^{1 - (4/5)^s}</tex> наборов по <tex>n^{(4/5)^s}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex>p = n^{(1/5)(4/5)^s}</tex> детей, то на <tex>s + 1</tex> уровень опускаются <tex>q = n^{(2/5)(4/5)^s}</tex> чисел для каждого набора, или всего <tex>qt \ge n^{2/5}</tex> чисел для всех наборов за один раз.
+
{{Лемма
 +
|id = lemma1
 +
|about = № 1
 +
|statement =
 +
Даны целые числа <tex dpi="130">b \geqslant s \geqslant 0</tex>, и <tex dpi="130">T</tex> является подмножеством множества <tex dpi="130">\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex dpi="130">n</tex> элементов, и <tex dpi="130">t \geqslant 2^{-s + 1}С^k_{n}</tex>. Функция <tex dpi="130">h_{a}</tex>, принадлежащая <tex dpi="130">H_{b,s}</tex>, может быть выбрана за время <tex dpi="130">O(bn^2)</tex> так, что количество коллизий <tex dpi="130">coll(h_{a}, 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> памяти. В том числе, так  может быть найдена медиана.
  
Спуск вниз можно рассматривать как сортировку <tex>q</tex> чисел в каждом наборе вместе с <tex>p</tex> числами <tex>a_{1}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <tex>q</tex> чисел разделены в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex> таких, что <tex>S_{0} < </tex> {<tex>a_{1}</tex>} <tex><</tex> <tex>\ldots</tex> <tex><</tex> {<tex>a_{p}</tex>} <tex>< S_{p}</tex>.
+
|proof =
 +
Так как возможно делать попарное сравнение <tex dpi="130">g</tex> чисел в одном контейнере с <tex dpi="130">g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex dpi="130">\ldots</tex>, <tex dpi="130">g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex dpi="130">S</tex> из медиан теперь содержится в <tex dpi="150">\frac{n}{5g}</tex> контейнерах. Рекурсивно находим медиану <tex dpi="130">m</tex> в <tex dpi="130">S</tex>. Используя <tex dpi="130">m</tex>, уберем хотя бы <tex dpi="150">\frac{n}{4}</tex> чисел среди <tex dpi="130">n</tex>. Затем упакуем оставшиеся из <tex dpi="150">\frac{n}{g}</tex> контейнеров в <tex dpi="150">\frac{3n}{4g}</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> памяти.
  
После <tex>g</tex> сокращений бит в '''signature sorting''' получаем неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на '''лемму №2''' для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадач разделения на <tex>w</tex> поднаборов для какого-то числа <tex>w</tex>.
+
Для контейнеров вне групп (которых <tex dpi="130">\sqrt{n}(g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex dpi="150">O(\frac{n}{g})</tex> времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex dpi="130">n</tex> контейнеров. Таким образом, все числа отсортированы.
  
  
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя '''лемму №2''', делается разделение. Так как получено неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> и работа происходит на уровнях не ниже, чем <tex>2 \log\log\log n</tex>, то алгоритм занимает <tex>O(qt \log\log n/(g(\log h - \log\log\log n) - \log\log\log n)) = O(\log\log n)</tex> времени.
+
Заметим, что когда <tex dpi="130">g = O( \log n)</tex>, сортировка <tex dpi="130">O(n)</tex> чисел в <tex dpi="150">\frac{n}{g}</tex> контейнеров произойдет за время <tex dpi="150">O((\frac{n}{g})</tex> <tex dpi="130">\log\log n)</tex> с использованием <tex dpi="150">O(\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>-ом контейнере для маркеров.
  
В итоге разделились <tex>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть получилось, что <tex>S_{0}</tex> < {<tex>e_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>e_{p}</tex>} < <tex>S_{p}</tex>, где <tex>e_{i}</tex> {{---}} сегмент <tex>a_{i}</tex>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве <tex>B</tex> так, что числа в <tex>S_{i}</tex> предшествуют числам в <tex>S_{j}</tex> если <tex>i < j</tex> и <tex>e_{i}</tex> хранится после <tex>S_{i - 1}</tex>, но до <tex>S_{i}</tex>.
 
  
 +
|proof =
 +
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex dpi="150">\frac{\log n}{2}</tex> бит. Сортировка сгруппирует контейнеры для чисел как в [[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров для чисел.
 +
}}
  
Пусть <tex>B[i]</tex> находится в поднаборе <tex>B[i].subset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <tex>B[j]</tex> в <tex>B[j].subset</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 =
 +
Заметим, что несмотря на то, что длина контейнера <tex dpi="130">\log m \log\log n</tex> бит, всего <tex dpi="130">\log m</tex> бит используется для хранения упакованных чисел. Так же как в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <tex dpi="130">g \log\log n</tex> вместо <tex dpi="130">g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex dpi="130">g \log\log n</tex> контейнеров, упаковываем <tex dpi="130">g \log\log n</tex> контейнеров в <tex dpi="130">g</tex>, упаковывая <tex dpi="130">\log\log n</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>\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> контейнеров. Считаем, что время, потраченное на один контейнер — константа.
+
Заметим, что если длина контейнера <tex dpi="130">\log m \log\log n</tex> и только <tex dpi="130">\log m</tex> бит используется для упаковки <tex dpi="130">g \leqslant \log n</tex> чисел в один контейнер, тогда выбор в [[#lemma2|лемме №2]] может быть сделан за время и память <tex dpi="150">O(\frac{n}{g})</tex>, потому что упаковка в доказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <tex dpi="150">O(\frac{n}{g})</tex>.
 +
}}
  
==Уменьшение числа бит в числах==
 
Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.
 
  
 +
{{Лемма
 +
|id = lemma6
 +
|about = № 6
 +
|statement =
 +
<tex dpi="130">n</tex> целых чисел можно отсортировать в <tex dpi="130">\sqrt{n}</tex> наборов <tex dpi="130">S_{1}</tex>, <tex dpi="130">S_{2}</tex>, <tex dpi="130">\ldots</tex>, <tex dpi="130">S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex dpi="130">\sqrt{n}</tex> чисел и <tex dpi="130">S_{i} < S_{j}</tex> при <tex dpi="130">i < j</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>.
  
Алгоритм: Пусть целое число <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</tex>: <tex>h_{a}(x) = (ax</tex> <tex>\bmod</tex> <tex>2^b)</tex> <tex>div</tex> <tex>2^{b - s}</tex>.
 
  
Данный алгоритм базируется на '''лемме №1'''.
+
|proof =
 +
Алгоритм сортировки <tex dpi="130">n</tex> целых чисел в <tex dpi="130">\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.  
  
 +
Постановка задачи и решение некоторых проблем:
  
Взяв <tex>s = 2 \log n</tex>, получаем хеш-функцию <tex>h_{a}</tex>, которая захеширует <tex>n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{a}(x)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <tex>h_{a}</tex> ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<tex>\bmod</tex> <tex>2^b</tex>) и (<tex>div</tex> <tex>2^{b - s}</tex>).
 
  
 +
Рассмотрим проблему сортировки <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>O(n^3)</tex>.
 
  
Следует отметить, что, несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</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|лемме №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> стадий.
  
==Signature sorting==
 
Предположим, что <tex>n</tex> чисел должны быть отсортированы, и в каждом <tex>\log m</tex> бит. Будем считаем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>\log m/h</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>\log m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>\log m/h</tex> бит в каждом.
 
  
 +
Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex dpi="130">n</tex> чисел уже поделены в <tex dpi="130">e</tex> наборов. Используем <tex dpi="130">\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma5|лемме №5]]. Полный размер маркера для каждого контейнера должен быть <tex dpi="150">\frac{\log n}{2}</tex>, и маркер использует <tex dpi="130">\log e</tex> бит, значит количество маркеров <tex dpi="130">g</tex> в каждом контейнере должно быть не более <tex dpi="150">\frac{\log n}{2\log e}</tex>. В дальнейшем, так как <tex dpi="150">g = \frac{\log n}{2 \log e}</tex>, м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex dpi="130">k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <tex dpi="150">O(\frac{k \log n}{g}) = O(k \log e)</tex> блоков. Заметим, что используется неконсервативное преимущество в <tex dpi="130">\log\log n</tex> для [[#lemma5|лемме №5]] Поэтому предполагается, что <tex dpi="150">\frac{\log n}{2 \log e}</tex> м.ч., в каждом из которых <tex dpi="130">k \log e</tex> блоков битов числа, упакованны в один контейнер. Для каждого м.ч. используется маркер из <tex dpi="130">\log e</tex> бит, который показывает, к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит <tex dpi="150">\frac{\log n}{2 \log e}</tex> маркеров, то для каждого контейнера требуется <tex dpi="150">\frac{\log n}{2}</tex> бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex dpi="150">O(\frac{n \log e}{ \log n})</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <tex dpi="150">O(\frac{n \log e}{ \log n})</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''' то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и взять некоторые из них. Так же делим биты для каждого числа из <tex>S</tex> и оставляем только один в каждом числе. По существу, для каждого <tex>a_{i}</tex> берутся все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегмент, который берется для числа в <tex>S</tex> это сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом, начальная задача о разделении <tex>n</tex> чисел по <tex>\log m</tex> бит преобразуется в несколько задач на разделение с числами по <tex>\log m/h</tex> бит.
+
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma5|леммы №5]].
  
  
Пример:
+
При таком помещении сразу возникает следующая проблема.
  
<tex>a_{1}</tex> = 3, <tex>a_{2}</tex> = 5, <tex>a_{3}</tex> = 7, <tex>a_{4}</tex> = 10, S = <tex>\{1, 4, 6, 8, 9, 13, 14\}</tex>.
+
Рассмотрим число <tex dpi="130">a</tex>, которое является <tex dpi="130">i</tex>-ым в наборе <tex dpi="130">S</tex>. Рассмотрим блок <tex dpi="130">a</tex> (назовем его <tex dpi="130">a'</tex>), который является <tex dpi="130">i</tex>-ым м.ч. в <tex dpi="130">S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex dpi="130">a</tex> (назовем это <tex dpi="130">a''</tex>) в <tex dpi="130">S</tex>, <tex dpi="130">a''</tex> просто перемещен на позицию в наборе <tex dpi="130">S</tex>, но не обязательно на позицию <tex dpi="130">i</tex> (где расположен <tex dpi="130">a'</tex>). Если значение блока <tex dpi="130">a'</tex> одинаково для всех чисел в <tex dpi="130">S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex dpi="130">S</tex> помещен <tex dpi="130">a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex dpi="130">k \log e</tex> блоков {{---}} это текущий блок. Таким образом, после того, как эти <tex dpi="130">k \log e</tex> блоков помещены в набор, изначальный текущий блок удаляется, потому что известно, что эти <tex dpi="130">k \log e</tex> блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex dpi="130">k \log e</tex> блоках.
  
Делим числа на 2 сегмента. Для <tex>a_{1}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> {{---}} верхний 1, нижний 1; <tex>a_{3}</tex> {{---}} верхний 1, нижний 3; <tex>a_{4}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим: для 1 нижний 1, так как он выделяется из нижнего сегмента <tex>a_{1}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты  8, 9, 10 формируют 4 новые задачи на разделение.
 
  
 +
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma3|3]], [[#lemma4|4]], [[#lemma5|5]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <tex dpi="130">n</tex> элементов в наборы размера <tex dpi="130">\sqrt{n}</tex>, то проблем быть не должно.
  
Использование '''signature sorting''' в данном алгоритме:
 
  
Есть набор <tex>T</tex> из <tex>p</tex> чисел, которые отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>. Используем числа в <tex>T</tex> для разделения набора <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex>. Пусть <tex>h = \log n/(c \log p)</tex> для константы <tex>c > 1</tex>. (<tex>h/ \log\log n \log p</tex>)-битные числа могут храниться в одном контейнере, содержащим <tex>(\log n)/(c \log\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/ \log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом) хешируются, и получается <tex>h/ \log\log n</tex> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть <tex>a'_{i}</tex> {{---}} хеш-контейнер для <tex>a_{i}</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> бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex> сегментов. Таким образом, получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).
+
===Алгоритм сортировки===
  
После того, как вышеописанный процесс повторится <tex>g</tex> раз, получится неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> раз, в то время как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление происходит за линейное время <tex>O(qt)</tex>.
+
Algorithm <tex>Sort(advantage</tex>, <tex>level</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{t}</tex>)
  
 +
<tex>advantage</tex> {{---}} это неконсервативное преимущество равное <tex>k\log\log n</tex>, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</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> хеш-функций.
+
# Если <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]].
  
 +
Algorithm IterateSort
 +
Call <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>(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 до 5
 +
# Помещаем <tex dpi="130">a_{i}</tex> в соответствующий набор с помощью блочной сортировки (англ. ''bucket sort''), потому что наборов около <tex dpi="130">\sqrt{n}</tex>.
 +
# Для каждого набора <tex dpi="130">S = </tex>{<tex dpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <tex dpi="130">t > \sqrt{n}</tex>, вызываем <tex>Sort(advantage</tex>, <tex dpi="130">\log_{k}(\frac{\log n}{4})</tex>, <tex dpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>).
  
 +
Время работы алгоритма <tex dpi="150">O(\frac{n \log\log n}{\log k})</tex>, что доказывает лемму.
 +
}}
  
Procedure '''Linear-Time-Sort'''
 
  
Входные данные: <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> наборов.
 
  
# Сортируем все <tex>d_{i}</tex> по <tex>d_{i}.value</tex>, используя bucket sort. Пусть все отртированные числа в <tex>A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex>n^{2/5}</tex> чисел.
+
==Уменьшение числа бит в числах==
# Помещаем все <tex>A[j]</tex> в <tex>A[j].set</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.
  
==Лемма №1==
 
Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0, и <tex>T</tex> является подмножеством множества <tex>\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\ge</tex> <tex>2^{-s + 1}</tex>С<tex>^k_{n}</tex>. Функция <tex>h_{a}</tex>, принадлежащая <tex>H_{b,s}</tex>, может быть выбрана за время <tex>O(bn^2)</tex> так, что количество коллизий <tex>coll(h_{a}, T)</tex> <tex>\le</tex> <tex>t</tex>.
 
  
==Лемма №2==
+
Алгоритм: Пусть целое число <tex dpi="130">b \geqslant 0</tex> и пусть <tex dpi="130">U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex dpi="130">H_{b,s}</tex> хеш-функций из <tex dpi="130">U</tex> в <tex dpi="130">\{0, \ldots, 2^s - 1\}</tex> определен как <tex dpi="130">H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex dpi="130">x</tex> из <tex dpi="130">U</tex>: <tex dpi="130">h_{a}(x) = (ax</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>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>n</tex> целых чисел в <tex>\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.  
+
Взяв <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>).  
  
==Сортировка n целых чисел в sqrt(n) наборов==
 
Постановка задачи и решение некоторых проблем:
 
  
 +
Такая хеш-функция может быть найдена за <tex dpi="130">O(n^3)</tex>.
  
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> в <tex>\sqrt{n}</tex> наборов, как в '''лемме №2'''. Предполагаем, что каждый контейнер содержит <tex>k \log\log n \log m</tex> бит и хранит число в <tex>\log m</tex> бит. Поэтому неконсервативное преимущество {{---}} <tex>k \log \log n</tex>. Также предполагаем, что <tex>\log m \ge \log n \log\log n</tex>. Иначе можно использовать radix sort для сортировки за время <tex>O(n \log\log n)</tex> и линейную память. Делим <tex>\log m</tex> бит, используемых для представления каждого числа, в <tex>\log n</tex> блоков. Таким образом, каждый блок содержит как минимум <tex>\log\log n</tex> бит. <tex>i</tex>-ый блок содержит с <tex>i \log m/ \log n</tex>-ого по <tex>((i + 1) \log m/ \log n - 1)</tex>-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex>2 \log n</tex>-уровневый алгоритм, который работает следующим образом:
+
Следует отметить, что, несмотря на размер таблицы <tex dpi="130">O(n^2)</tex>, потребность в памяти не превышает <tex dpi="130">O(n)</tex>, потому что хеширование используется только для уменьшения количества бит в числе.
  
 +
==Сортировка по ключу==
 +
Предположим, что <tex dpi="130">n</tex> чисел должны быть отсортированы, и в каждом <tex dpi="130">\log m</tex> бит. Будем считать, что в каждом числе есть <tex dpi="130">h</tex> сегментов, в каждом из которых <tex dpi="130">\log</tex> <tex dpi="150">\frac{m}{h}</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex dpi="130">2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex dpi="130">n</tex> чисел по <tex dpi="130">\log m</tex> бит в каждом стала задачей по сортировке <tex dpi="130">n</tex> чисел по <tex dpi="130">\log</tex> <tex dpi="150">\frac{m}{h}</tex> бит в каждом.
  
На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только <tex>\log m/ \log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex>\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/ \log n</tex> контейнеров с <tex>\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По '''лемме №3''' находим медиану этих <tex>n</tex> м.ч. за время и память <tex>O(n/ \log n)</tex>. Пусть <tex>a</tex> {{---}} это найденная медиана. Тогда <tex>n</tex> м.ч. могут быть разделены на не более чем три группы: <tex>S_{1}</tex>, <tex>S_{2}</tex> и <tex>S_{3}</tex>. <tex>S_{1}</tex> содержит м.ч., которые меньше <tex>a</tex>, <tex>S_{2}</tex> содержит м.ч., равные <tex>a</tex>, <tex>S_{3}</tex> содержит м.ч., большие <tex>a</tex>. Также мощность <tex>S_{1}</tex> и <tex>S_{3} </tex> не превосходит <tex>n/2</tex>. Мощность <tex>S_{2}</tex> может быть любой. Пусть <tex>S'_{2}</tex> {{---}} это набор чисел, у которых наибольший блок находится в <tex>S_{2}</tex>. Тогда убираем из дальнейшего рассмотрения <tex>\log m/ \log n</tex> бит (наибольший блок) из каждого числа, принадлежащего <tex>S'_{2}</tex>. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>\log n</tex> блоков, для каждого числа потребуется не более <tex>\log n</tex> стадий, чтобы поместить его в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex>n/ \log n</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex>O(n)</tex> времени из-за <tex>2 \log n</tex> стадий.
 
  
 +
Также рассмотрим проблему последующего разделения. Пусть <tex dpi="130">a_{1}</tex>, <tex dpi="130">a_{2}</tex>, <tex dpi="130">\ldots</tex>, <tex dpi="130">a_{p}</tex> {{---}} <tex dpi="130">p</tex> чисел и <tex dpi="130">S</tex> {{---}} множество чисeл. Необходимо разделить <tex dpi="130">S</tex> в <tex dpi="130">p + 1</tex> наборов, таких, что: <tex dpi="130">S_{0} < a_{1} < S_{1} < a_{2} < \ldots < a_{p} < S_{p}</tex>. Так как используется '''сортировка по ключу''' (англ. ''signature sorting'') то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <tex dpi="130">a_{i}</tex> на <tex dpi="130">h</tex> сегментов и взять некоторые из них. Так же делим биты для каждого числа из <tex dpi="130">S</tex> и оставляем только один в каждом числе. По существу, для каждого <tex dpi="130">a_{i}</tex> берутся все <tex dpi="130">h</tex> сегментов. Если соответствующие сегменты <tex dpi="130">a_{i}</tex> и <tex dpi="130">a_{j}</tex> совпадают, то нам понадобится только один. Сегмент, который берется для числа в <tex dpi="130">S</tex> это сегмент, который выделяется из <tex dpi="130">a_{i}</tex>. Таким образом, начальная задача о разделении <tex dpi="130">n</tex> чисел по <tex dpi="130">\log m</tex> бит преобразуется в несколько задач на разделение с числами по <tex dpi="150">\frac{\log m}{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>.
 
  
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из '''леммы №6'''.
+
'''Пример''':
 +
[[Файл:Han-example.png|500px|thumb]]
  
 +
<tex dpi="130">a_{1} = 3, a_{2} = 5, 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> блоках.
 
  
  
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. '''Леммы №4, №5, №6''' расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</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> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть <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> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в <tex dpi="130">a_{i}</tex> и <tex dpi="130">b_{i}</tex> разрезаны на <tex dpi="150">\frac{\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>.
  
  
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>)
+
Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, <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> хеш-функций.
  
<tex>k \log\log n</tex> {{---}} это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</tex> это уровень рекурсии.
 
  
# Если <tex>(level == 1)</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\le</tex> 3 набора, используя '''лемму №3''', чтобы найти медиану, а затем используем '''лемму №6''' для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.
+
Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит. Есть <tex dpi="130">t</tex> наборов, в каждом из которых <tex dpi="130">q + p</tex> хешированных контейнеров по <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.
# От <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>. При этом у <tex>a^{(u)}_{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}</tex>-ые к их наборам, используя '''лемму №6'''.
 
  
Конец.
 
  
 +
Операция '''сортировки за линейное время''' (англ. ''Linear-Time-Sort'')
  
Algorithm IterateSort
+
Входные данные: <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> наборов.
Call Sort(<tex>k \log\log n</tex>, <tex>\log_{k}((\log n)/4)</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{n - 1}</tex>);
 
  
от 1 до 5
+
# Сортируем все <tex dpi="130">d_{i}</tex> по <tex dpi="130">d_{i}.value</tex>, используя bucket sort. Пусть все отсортированные числа в <tex dpi="130">A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex dpi="150">n^{\frac{2}{5}}</tex> чисел.
# Помещаем <tex>a_{i}</tex> в соответствующий набор с помощью bucket sort, потому что наборов около <tex>\sqrt{n}</tex>.
+
# Помещаем все <tex dpi="130">A[j]</tex> в <tex dpi="130">A[j].set</tex>.
# Для каждого набора <tex>S = </tex>{<tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <tex>t > \sqrt{n}</tex>, вызываем Sort(<tex>k \log\log n</tex>, <tex>\log_{k}((\log 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'''.
+
==Сортировка с использованием O(n log log n) времени и памяти==
 +
Для сортировки <tex dpi="130">n</tex> целых чисел в диапазоне <tex dpi="130">\{0, 1, \ldots, m - 1\}</tex> предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex dpi="130">O(\log (m + n))</tex>. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.  
  
==Лемма №3==
 
Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел, упакованных в <tex>n/g</tex> контейнеров, может быть сделан за время <tex>O(n \log g/g)</tex> и с использованием <tex>O(n/g)</tex> памяти. В том числе, так  может быть найдена медиана.
 
  
 +
Берем <tex dpi="130">1/e = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex dpi="150">n^{\frac{1}{5}}</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь <tex dpi="150">n^{\frac{4}{5}}</tex> листьев. В отличие от оригинального дерева, за раз вставляется не один элемент, а <tex dpi="130">d^2</tex>, где <tex dpi="130">d</tex> — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex dpi="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>, в каждом из которых <tex dpi="150">n^{\frac{4}{5}}</tex> чисел и <tex dpi="130">S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex dpi="150">n^{\frac{8}{25}}</tex> чисел из <tex dpi="130">S_{i}</tex> и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex dpi="150">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}</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> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex>\ldots</tex>, <tex>g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex>, уберем хотя бы <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсию.
 
  
==Лемма №4==
+
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <tex dpi="130">s</tex>. Имеется <tex dpi="150">t = n^{1 - (\frac{4}{5})^S}</tex> наборов по <tex dpi="150">n^{(\frac{4}{5})^S}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex dpi="150">p = n^{\frac{1}{5} \cdot (\frac{4}{5})^S}</tex> детей, то на <tex dpi="130">s + 1</tex> уровень опускаются <tex dpi="150">q = n^{\frac{2}{5} \cdot (\frac{4}{5})^S}</tex> чисел для каждого набора, или всего <tex dpi="150">qt \geqslant n^{\frac{2}{5}}</tex> чисел для всех наборов за один раз.
Если <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> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <tex>O(n/g)</tex> времени и памяти. Так как используется <tex>(\log n)/2</tex> бит на контейнер, понадобится <tex>\sqrt{n}</tex> шаблонов для всех контейнеров. Затем поместим <tex>g < (\log n)/2</tex> контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более <tex>g - 1</tex> контейнеров, которые не смогут образовать группу. Поэтому не более <tex>\sqrt{n}(g - 1)</tex> контейнеров не смогут сформировать группу. Для каждой группы помещаем <tex>i</tex>-е число во всех <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(g)</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 sort вновь для сортировки <tex>n</tex> контейнеров. Таким образом, все числа отсортированы.
+
Так как <tex dpi="130">q</tex> чисел не надо полностью сортировать и <tex dpi="130">q = p^2</tex>, то можно использовать [[#lemma6|лемму №6]] для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью [[Сортировка Хана#Signature sorting|signature sorting]]. Для этого используется линейная техника многократного деления (англ. ''multi-dividing technique'').
  
  
Заметим, что когда <tex>g = O( \log n)</tex>, сортировка <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров произойдет за время <tex>O((n/g) \log\log n)</tex> с использованием <tex>O(n/g)</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>.
  
==Лемма №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>( \log n)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в '''лемме №4'''. Перемещаем каждую группу контейнеров для чисел.
+
В итоге разделились <tex dpi="130">q</tex> чисел <tex dpi="130">p</tex> числами в каждый набор. То есть получилось, что <tex dpi="130">S_{0} < e_{1} < S_{1} < \ldots < e_{p} < S_{p}</tex>, где <tex dpi="130">e_{i}</tex> {{---}} сегмент <tex dpi="130">a_{i}</tex>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве <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>.
+
==См. также==
 +
* [[Сортировка подсчетом]]
 +
* [[Цифровая сортировка]]
  
==Литература==
+
==Источники информации==
# Deterministic Sorting in O(n \log\log n) Time and Linear Space. Yijie Han.
+
* [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)
+
* А. Андерссон. 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]]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
[[Категория: Сортировки]]
+
[[Категория: Сортировка]]

Текущая версия на 19:13, 4 сентября 2022

Сортировка Хана (англ. Hansort) — сложный алгоритм сортировки целых чисел со сложностью [math]O(n \log\log n)[/math], где [math]n[/math] — количество элементов для сортировки.

Данная статья писалась на основе брошюры Хана (англ. Yijie Han), посвященной этой сортировке.

Описание

Алгоритм построен на основе экспоненциального поискового дерева Андерсона (англ. Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в экспоненциальное поисковое дерево (далее — ЭП-дерево).

Экспоненциальное поисковое дерево Андерсона

Определение:
ЭП-дерево — это дерево поиска, в котором все ключи хранятся в листьях этого дерева и количество детей у каждого узла уменьшается экспоненциально от глубины узла.


Общая структура ЭП-дерева

Структура ЭП-дерева:

1) Корень имеет [math]\Theta (n^e)[/math] сыновей [math]( 0 \lt e \lt 1 )[/math]. Все сыновья являются ЭП-деревьями.

2) Каждое поддерево корня имеет [math]\Theta(n^{1-e})[/math] сыновей.

В этом дереве [math]O(n \log\log n)[/math] уровней. При нарушении баланса дерева необходимо балансирование, которое требует [math]O(n \log\log n)[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.

Определения

Определение:
Контейнер — объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.


Определение:
Алгоритм, сортирующий [math]n[/math] целых чисел из множества [math]\{0, 1, \ldots, m - 1\}[/math], называется консервативным, если длина контейнера (число бит в контейнере) равна [math]O(\log(m + n))[/math]. Если длина больше, то алгоритм неконсервативный.


Определение:
Если сортируются целые числа из множества [math]\{0, 1, \ldots, m - 1\}[/math] с длиной контейнера [math]k \log (m + n)[/math] с [math]k \geqslant 1[/math], тогда сортировка происходит с неконсервативным преимуществом [math]k[/math].


Определение:
Для множества [math]S[/math] определим

[math]\min(S) = \min\limits_{a \in S} a[/math]

[math]\max(S) = \max\limits_{a \in S} a[/math]

Набор [math]S1 \lt S2[/math] если [math]\max(S1) \leqslant \min(S2)[/math]


Определение:
Предположим, есть набор [math]T[/math] из [math]p[/math] чисел, которые уже отсортированы как [math]a_{1}, a_{2}, \ldots, a_{p}[/math] и набор [math]S[/math] из [math]q[/math] чисел [math]b_{1}, b_{2}, \ldots, b_{q}[/math]. Тогда разделением [math]q[/math] чисел [math]p[/math] числами называется [math]p + 1[/math] набор [math]S_{0}, S_{1}, \ldots, S_{p}[/math], где [math]S_{0} \lt a_{1} \lt S_{1} \lt \ldots \lt a_{p} \lt S_{p}[/math].


Леммы

Лемма (№ 1):
Даны целые числа [math]b \geqslant s \geqslant 0[/math], и [math]T[/math] является подмножеством множества [math]\{0, \ldots, 2^b - 1\}[/math], содержащим [math]n[/math] элементов, и [math]t \geqslant 2^{-s + 1}С^k_{n}[/math]. Функция [math]h_{a}[/math], принадлежащая [math]H_{b,s}[/math], может быть выбрана за время [math]O(bn^2)[/math] так, что количество коллизий [math]coll(h_{a}, T) \leqslant t[/math].
Лемма (№ 2):
Выбор [math]s[/math]-ого наибольшего числа среди [math]n[/math] чисел, упакованных в [math]\frac{n}{g}[/math] контейнеров, может быть сделан за время [math]O(\frac{n \log g}{g})[/math] и с использованием [math]O(\frac{n}{g})[/math] памяти. В том числе, так может быть найдена медиана.
Доказательство:
[math]\triangleright[/math]
Так как возможно делать попарное сравнение [math]g[/math] чисел в одном контейнере с [math]g[/math] числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, [math]\ldots[/math], [math]g[/math]-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор [math]S[/math] из медиан теперь содержится в [math]\frac{n}{5g}[/math] контейнерах. Рекурсивно находим медиану [math]m[/math] в [math]S[/math]. Используя [math]m[/math], уберем хотя бы [math]\frac{n}{4}[/math] чисел среди [math]n[/math]. Затем упакуем оставшиеся из [math]\frac{n}{g}[/math] контейнеров в [math]\frac{3n}{4g}[/math] контейнеров и затем продолжим рекурсию.
[math]\triangleleft[/math]
Лемма (№ 3):
Если [math]g[/math] целых чисел, в сумме использующих [math]\frac{\log n}{2}[/math] бит, упакованы в один контейнер, тогда [math]n[/math] чисел в [math]\frac{n}{g}[/math] контейнерах могут быть отсортированы за время [math]O(\frac{n \log g}{g})[/math] с использованием [math]O(\frac{n}{g})[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Так как используется только [math]\frac{\log n}{2}[/math] бит в каждом контейнере для хранения [math]g[/math] чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает [math]O(\frac{n}{g})[/math] времени и памяти. Так как используется [math]\frac{\log n}{2}[/math] бит на контейнер, понадобится [math]\sqrt{n}[/math] шаблонов для всех контейнеров. Затем поместим [math]g \lt \frac{\log n}{2}[/math] контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более [math]g - 1[/math] контейнеров, которые не смогут образовать группу. Поэтому не более [math]\sqrt{n}(g - 1)[/math] контейнеров не смогут сформировать группу. Для каждой группы помещаем [math]i[/math]-е число во всех [math]g[/math] контейнерах в один. Таким образом берутся [math]g[/math] [math]g[/math]-целых векторов и получаются [math]g[/math] [math]g[/math]-целых векторов, где [math]i[/math]-ый вектор содержит [math]i[/math]-ое число из входящего вектора. Эта транспозиция может быть сделана за время [math]O(g \log g)[/math], с использованием [math]O(g)[/math] памяти. Для всех групп это занимает время [math]O(\frac{n \log g}{g})[/math], с использованием [math]O(\frac{n}{g})[/math] памяти.

Для контейнеров вне групп (которых [math]\sqrt{n}(g - 1)[/math] штук) разбираем и собираем заново контейнеры. На это потребуется не более [math]O(\frac{n}{g})[/math] времени и памяти. После всего этого используем карманную сортировку вновь для сортировки [math]n[/math] контейнеров. Таким образом, все числа отсортированы.


Заметим, что когда [math]g = O( \log n)[/math], сортировка [math]O(n)[/math] чисел в [math]\frac{n}{g}[/math] контейнеров произойдет за время [math]O((\frac{n}{g})[/math] [math]\log\log n)[/math] с использованием [math]O(\frac{n}{g})[/math] памяти. Выгода очевидна.
[math]\triangleleft[/math]
Лемма (№ 4):
Примем, что каждый контейнер содержит [math] \log m \gt \log n[/math] бит, и [math]g[/math] чисел, в каждом из которых [math]\frac{\log m}{g}[/math] бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий [math]\frac{\log n}{2g}[/math] бит, и [math]g[/math] маркеров упакованы в один контейнер таким же образом[math]^*[/math], что и числа, тогда [math]n[/math] чисел в [math]\frac{n}{g}[/math] контейнерах могут быть отсортированы по их маркерам за время [math]O(\frac{n \log\log n}{g})[/math] с использованием [math]O(\frac{n}{g})[/math] памяти. (*): если число [math]a[/math] упаковано как [math]s[/math]-ое число в [math]t[/math]-ом контейнере для чисел, тогда маркер для [math]a[/math] упакован как [math]s[/math]-ый маркер в [math]t[/math]-ом контейнере для маркеров.
Доказательство:
[math]\triangleright[/math]
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует [math]\frac{\log n}{2}[/math] бит. Сортировка сгруппирует контейнеры для чисел как в лемме №3. Перемещаем каждую группу контейнеров для чисел.
[math]\triangleleft[/math]
Лемма (№ 5):
Предположим, что каждый контейнер содержит [math]\log m \log\log n \gt \log n[/math] бит, что [math]g[/math] чисел, в каждом из которых [math]\frac{\log m}{g}[/math] бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий [math]\frac{\log n}{2g}[/math] бит, и что [math]g[/math] маркеров упакованы в один контейнер тем же образом что и числа. Тогда [math]n[/math] чисел в [math]\frac{n}{g}[/math] контейнерах могут быть отсортированы по своим маркерам за время [math]O(\frac{n}{g})[/math] с использованием [math]O(\frac{n}{g})[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Заметим, что несмотря на то, что длина контейнера [math]\log m \log\log n[/math] бит, всего [math]\log m[/math] бит используется для хранения упакованных чисел. Так же как в лемме №3 и лемме №4 сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем [math]g \log\log n[/math] вместо [math]g[/math] контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей [math]g \log\log n[/math] контейнеров, упаковываем [math]g \log\log n[/math] контейнеров в [math]g[/math], упаковывая [math]\log\log n[/math] контейнеров в один. Далее делаем транспозицию над [math]g[/math] контейнерами. Таким образом перемещение занимает всего [math]O(g \log\log n)[/math] времени для каждой группы и [math]O(\frac{n}{g})[/math] времени для всех чисел. После завершения транспозиции, распаковываем [math]g[/math] контейнеров в [math]g \log\log n[/math] контейнеров.


Заметим, что если длина контейнера [math]\log m \log\log n[/math] и только [math]\log m[/math] бит используется для упаковки [math]g \leqslant \log n[/math] чисел в один контейнер, тогда выбор в лемме №2 может быть сделан за время и память [math]O(\frac{n}{g})[/math], потому что упаковка в доказательстве лемме №2 теперь может быть сделана за время [math]O(\frac{n}{g})[/math].
[math]\triangleleft[/math]


Лемма (№ 6):
[math]n[/math] целых чисел можно отсортировать в [math]\sqrt{n}[/math] наборов [math]S_{1}[/math], [math]S_{2}[/math], [math]\ldots[/math], [math]S_{\sqrt{n}}[/math] таким образом, что в каждом наборе [math]\sqrt{n}[/math] чисел и [math]S_{i} \lt S_{j}[/math] при [math]i \lt j[/math], за время [math]O(\frac{n \log\log n} {\log k})[/math] и место [math]O(n)[/math] с неконсервативным преимуществом [math]k \log\log n[/math].
Доказательство:
[math]\triangleright[/math]

Алгоритм сортировки [math]n[/math] целых чисел в [math]\sqrt{n}[/math] наборов, представленный ниже, является доказательством данной леммы.

Постановка задачи и решение некоторых проблем:


Рассмотрим проблему сортировки [math]n[/math] целых чисел из множества [math]\{0, 1, \ldots, m - 1\}[/math] в [math]\sqrt{n}[/math] наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит [math]k \log\log n \log m[/math] бит и хранит число в [math]\log m[/math] бит. Поэтому неконсервативное преимущество — [math]k \log \log n[/math]. Также предполагаем, что [math]\log m \geqslant \log n \log\log n[/math]. Иначе можно использовать radix sort для сортировки за время [math]O(n \log\log n)[/math] и линейную память. Делим [math]\log m[/math] бит, используемых для представления каждого числа, в [math]\log n[/math] блоков. Таким образом, каждый блок содержит как минимум [math]\log\log n[/math] бит. [math]i[/math]-ый блок содержит с [math]\frac{i \log m} {\log n}[/math]-ого по [math](\frac{(i + 1) \log m} {\log n - 1})[/math]-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется [math]2 \log n[/math]-уровневый алгоритм, который работает следующим образом:


На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только [math]\frac{\log m}{\log n}[/math] бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер [math]\log n - 1[/math]). Предполагаем, что биты этих м.ч. упакованы в [math]\frac{n}{\log n}[/math] контейнеров с [math]\log n[/math] м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По лемме №2 находим медиану этих [math]n[/math] м.ч. за время и память [math]O(\frac{n}{\log n})[/math]. Пусть [math]a[/math] — это найденная медиана. Тогда [math]n[/math] м.ч. могут быть разделены на не более чем три группы: [math]S_{1}[/math], [math]S_{2}[/math] и [math]S_{3}[/math]. [math]S_{1}[/math] содержит м.ч., которые меньше [math]a[/math], [math]S_{2}[/math] содержит м.ч., равные [math]a[/math], [math]S_{3}[/math] содержит м.ч., большие [math]a[/math]. Также мощность [math]S_{1}[/math] и [math]S_{3} [/math] не превосходит [math]n/2[/math]. Мощность [math]S_{2}[/math] может быть любой. Пусть [math]S'_{2}[/math] — это набор чисел, у которых наибольший блок находится в [math]S_{2}[/math]. Тогда убираем из дальнейшего рассмотрения [math]\frac{\log m}{\log n}[/math] бит (наибольший блок) из каждого числа, принадлежащего [math]S'_{2}[/math]. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только [math]\log n[/math] блоков, для каждого числа потребуется не более [math]\log n[/math] стадий, чтобы поместить его в набор половинного размера. За [math]2 \log n[/math] стадий все числа будут отсортированы. Так как на каждой стадии работаем с [math]\frac{n}{\log n}[/math] контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается [math]O(n)[/math] времени из-за [math]2 \log n[/math] стадий.


Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что [math]n[/math] чисел уже поделены в [math]e[/math] наборов. Используем [math]\log e[/math] битов чтобы сделать марки для каждого набора. Теперь используем лемме №5. Полный размер маркера для каждого контейнера должен быть [math]\frac{\log n}{2}[/math], и маркер использует [math]\log e[/math] бит, значит количество маркеров [math]g[/math] в каждом контейнере должно быть не более [math]\frac{\log n}{2\log e}[/math]. В дальнейшем, так как [math]g = \frac{\log n}{2 \log e}[/math], м.ч. должны влезать в контейнер. Каждый контейнер содержит [math]k \log\log n \log n[/math] блоков, каждое м.ч. может содержать [math]O(\frac{k \log n}{g}) = O(k \log e)[/math] блоков. Заметим, что используется неконсервативное преимущество в [math]\log\log n[/math] для лемме №5 Поэтому предполагается, что [math]\frac{\log n}{2 \log e}[/math] м.ч., в каждом из которых [math]k \log e[/math] блоков битов числа, упакованны в один контейнер. Для каждого м.ч. используется маркер из [math]\log e[/math] бит, который показывает, к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит [math]\frac{\log n}{2 \log e}[/math] маркеров, то для каждого контейнера требуется [math]\frac{\log n}{2}[/math] бит. Таким образом, лемма №5 может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется [math]O(\frac{n \log e}{ \log n})[/math] контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно [math]O(\frac{n \log e}{ \log n})[/math].

Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из леммы №5.


При таком помещении сразу возникает следующая проблема.

Рассмотрим число [math]a[/math], которое является [math]i[/math]-ым в наборе [math]S[/math]. Рассмотрим блок [math]a[/math] (назовем его [math]a'[/math]), который является [math]i[/math]-ым м.ч. в [math]S[/math]. Когда используется вышеописанный метод перемещения нескольких следующих блоков [math]a[/math] (назовем это [math]a''[/math]) в [math]S[/math], [math]a''[/math] просто перемещен на позицию в наборе [math]S[/math], но не обязательно на позицию [math]i[/math] (где расположен [math]a'[/math]). Если значение блока [math]a'[/math] одинаково для всех чисел в [math]S[/math], то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в [math]S[/math] помещен [math]a''[/math]. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди [math]k \log e[/math] блоков — это текущий блок. Таким образом, после того, как эти [math]k \log e[/math] блоков помещены в набор, изначальный текущий блок удаляется, потому что известно, что эти [math]k \log e[/math] блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных [math]k \log e[/math] блоках.


Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы 3, 4, 5 расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из [math]n[/math] элементов в наборы размера [math]\sqrt{n}[/math], то проблем быть не должно.


Алгоритм сортировки

Algorithm [math]Sort(advantage[/math], [math]level[/math], [math]a_{0}[/math], [math]a_{1}[/math], [math]\ldots[/math], [math]a_{t}[/math])

[math]advantage[/math] — это неконсервативное преимущество равное [math]k\log\log n[/math], [math]a_{i}[/math]-ые это входящие целые числа в наборе, которые надо отсортировать, [math]level[/math] это уровень рекурсии.

  1. Если [math]level[/math] равен [math]1[/math] тогда изучаем размер набора. Если размер меньше или равен [math]\sqrt{n}[/math], то [math]return[/math]. Иначе делим этот набор в [math]\leqslant[/math] 3 набора, используя лемму №2, чтобы найти медиану, а затем используем лемму №5 для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.
  2. От [math]u = 1[/math] до [math]k[/math]
    1. Упаковываем [math]a^{(u)}_{i}[/math]-ый в часть из [math]1/k[/math]-ых номеров контейнеров. Где [math]a^{(u)}_{i}[/math] содержит несколько непрерывных блоков, которые состоят из [math]\frac{1}{k}[/math]-ых битов [math]a_{i}[/math]. При этом у [math]a^{(u)}_{i}[/math] текущий блок это самый крупный блок.
    2. Вызываем [math]Sort(advantage[/math], [math]level - 1[/math], [math]a^{(u)}_{0}[/math], [math]a^{(u)}_{1}[/math], [math]\ldots[/math], [math]a^{(u)}_{t}[/math]). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это число относится, уже направлен назад к месту, где число находится во входных данных. Число, имеющее наибольшее число бит в [math]a_{i}[/math], показывающее на текущий блок в нем, так же направлено назад к [math]a_{i}[/math].
    3. Отправляем [math]a_{i}[/math]-ые к их наборам, используя лемму №5.

Algorithm IterateSort Call [math]Sort(advantage[/math], [math]\log_{k}((\log n)/4)[/math], [math]a_{0}[/math], [math]a_{1}[/math], [math]\ldots[/math], [math]a_{n - 1}[/math]);

от 1 до 5

  1. Помещаем [math]a_{i}[/math] в соответствующий набор с помощью блочной сортировки (англ. bucket sort), потому что наборов около [math]\sqrt{n}[/math].
  2. Для каждого набора [math]S = [/math]{[math]a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}[/math]}, если [math]t \gt \sqrt{n}[/math], вызываем [math]Sort(advantage[/math], [math]\log_{k}(\frac{\log n}{4})[/math], [math]a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}[/math]).
Время работы алгоритма [math]O(\frac{n \log\log n}{\log k})[/math], что доказывает лемму.
[math]\triangleleft[/math]


Уменьшение числа бит в числах

Один из способов ускорить сортировку — уменьшить число бит в числе. Один из способов уменьшить число бит в числе — использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий [math]O(m)[/math] памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до [math]O(n)[/math]. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования [math]n[/math] чисел в таблицу размера [math]O(n^2)[/math] за константное время без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.


Алгоритм: Пусть целое число [math]b \geqslant 0[/math] и пусть [math]U = \{0, \ldots, 2^b - 1\}[/math]. Класс [math]H_{b,s}[/math] хеш-функций из [math]U[/math] в [math]\{0, \ldots, 2^s - 1\}[/math] определен как [math]H_{b,s} = \{h_{a} \mid 0 \lt a \lt 2^b, a \equiv 1 (\bmod 2)\}[/math] и для всех [math]x[/math] из [math]U[/math]: [math]h_{a}(x) = (ax[/math] [math]\bmod[/math] [math]2^b)[/math] [math]div[/math] [math]2^{b - s}[/math].

Данный алгоритм базируется на лемме №1.


Взяв [math]s = 2 \log n[/math], получаем хеш-функцию [math]h_{a}[/math], которая захеширует [math]n[/math] чисел из [math]U[/math] в таблицу размера [math]O(n^2)[/math] без коллизий. Очевидно, что [math]h_{a}(x)[/math] может быть посчитана для любого [math]x[/math] за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить [math]h_{a}[/math] ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только ([math]\bmod[/math] [math]2^b[/math]) и ([math]div[/math] [math]2^{b - s}[/math]).


Такая хеш-функция может быть найдена за [math]O(n^3)[/math].

Следует отметить, что, несмотря на размер таблицы [math]O(n^2)[/math], потребность в памяти не превышает [math]O(n)[/math], потому что хеширование используется только для уменьшения количества бит в числе.

Сортировка по ключу

Предположим, что [math]n[/math] чисел должны быть отсортированы, и в каждом [math]\log m[/math] бит. Будем считать, что в каждом числе есть [math]h[/math] сегментов, в каждом из которых [math]\log[/math] [math]\frac{m}{h}[/math] бит. Теперь применяем хеширование ко всем сегментам и получаем [math]2h \log n[/math] бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке [math]n[/math] чисел по [math]\log m[/math] бит в каждом стала задачей по сортировке [math]n[/math] чисел по [math]\log[/math] [math]\frac{m}{h}[/math] бит в каждом.


Также рассмотрим проблему последующего разделения. Пусть [math]a_{1}[/math], [math]a_{2}[/math], [math]\ldots[/math], [math]a_{p}[/math][math]p[/math] чисел и [math]S[/math] — множество чисeл. Необходимо разделить [math]S[/math] в [math]p + 1[/math] наборов, таких, что: [math]S_{0} \lt a_{1} \lt S_{1} \lt a_{2} \lt \ldots \lt a_{p} \lt S_{p}[/math]. Так как используется сортировка по ключу (англ. signature sorting) то перед тем, как делать вышеописанное разделение, необходимо поделить биты в [math]a_{i}[/math] на [math]h[/math] сегментов и взять некоторые из них. Так же делим биты для каждого числа из [math]S[/math] и оставляем только один в каждом числе. По существу, для каждого [math]a_{i}[/math] берутся все [math]h[/math] сегментов. Если соответствующие сегменты [math]a_{i}[/math] и [math]a_{j}[/math] совпадают, то нам понадобится только один. Сегмент, который берется для числа в [math]S[/math] это сегмент, который выделяется из [math]a_{i}[/math]. Таким образом, начальная задача о разделении [math]n[/math] чисел по [math]\log m[/math] бит преобразуется в несколько задач на разделение с числами по [math]\frac{\log m}{h}[/math] бит.


Пример:

Han-example.png

[math]a_{1} = 3, a_{2} = 5, a_{3} = 7, a_{4} = 10, S = \{1, 4, 6, 8, 9, 13, 14\}[/math].

Делим числа на два сегмента. Для [math]a_{1}[/math] получим верхний сегмент [math]0[/math], нижний [math]3[/math]; [math]a_{2}[/math] — верхний [math]1[/math], нижний [math]1[/math]; [math]a_{3}[/math] — верхний [math]1[/math], нижний [math]3[/math]; [math]a_{4}[/math] — верхний [math]2[/math], нижний [math]2[/math]. Для элементов из S получим: для [math]1[/math] нижний [math]1[/math], так как он выделяется из нижнего сегмента [math]a_{1}[/math]; для [math]4[/math] нижний [math]0[/math]; для [math]8[/math] нижний [math]0[/math]; для [math]9[/math] нижний [math]1[/math]; для [math]13[/math] верхний [math]3[/math]; для [math]14[/math] верхний [math]3[/math]. Теперь все верхние сегменты, нижние сегменты [math]1[/math] и [math]3[/math], нижние сегменты [math]4, 5, 6, 7,[/math] нижние сегменты [math]8, 9, 10[/math] формируют [math]4[/math] новые задачи на разделение.


Использование сортировки по ключу в данном алгоритме:

Есть набор [math]T[/math] из [math]p[/math] чисел, которые отсортированы как [math]a_{1}, a_{2}, \ldots, a_{p}[/math]. Используем числа в [math]T[/math] для разделения набора [math]S[/math] из [math]q[/math] чисел [math]b_{1}, b_{2}, \ldots, b_{q}[/math] в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, \ldots, S_{p}[/math]. Пусть [math]h = \frac{\log n}{c \log p}[/math] для константы [math]c \gt 1[/math]. ([math]\frac{h}{\log\log n \log p}[/math])-битные числа могут храниться в одном контейнере, содержащим [math]\frac{\log n}{c \log\log n}[/math] бит. Сначала рассматриваем биты в каждом [math]a_{i}[/math] и каждом [math]b_{i}[/math] как сегменты одинаковой длины [math]\frac{h} {\log\log n}[/math]. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах ([math]a_{i}[/math]-ом и [math]b_{i}[/math]-ом) хешируются, и получается [math]\frac{h}{\log\log n}[/math] хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть [math]a'_{i}[/math] — хеш-контейнер для [math]a_{i}[/math], аналогично [math]b'_{i}[/math]. В сумме хеш-значения имеют [math]\frac{2 \log n}{c \log\log n}[/math] бит, хотя эти значения разделены на сегменты по [math]\frac{h}{ \log\log n}[/math] бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в [math]\frac{2 \log n}{c \log\log n}[/math] бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в [math]a_{i}[/math] и [math]b_{i}[/math] разрезаны на [math]\frac{\log\log n}{h}[/math] сегментов. Таким образом, получилось дополнительное мультипликативное преимущество (англ. additional multiplicative advantage) в [math]\frac{h} {\log\log n}[/math].

После того, как вышеописанный процесс повторится [math]g[/math] раз, получится неконсервативное преимущество в [math](\frac{h} {\log\log n})^g[/math] раз, в то время как потрачено только [math]O(gqt)[/math] времени, так как каждое многократное деление происходит за линейное время [math]O(qt)[/math].


Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, [math]\frac{\log\log n}{h}[/math]-ые, [math](\frac{\log\log n}{h})^2[/math]-ые, [math]\ldots[/math] по счету в числе. Хеш-функцию для [math](\frac{\log\log n}{h})^t[/math]-ых по счету сегментов, получаем нарезанием всех [math]p[/math] чисел на [math](\frac{\log\log n}{h})^t[/math] сегментов. Рассматривая каждый сегмент как число, получаем [math]p(\frac{\log\log n}{h})^t[/math] чисел. Затем получаем одну хеш-функцию для этих чисел. Так как [math]t \lt \log n[/math], то получится не более [math]\log n[/math] хеш-функций.


Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в [math]\frac{2 \log n}{c \log\log n}[/math] бит. Есть [math]t[/math] наборов, в каждом из которых [math]q + p[/math] хешированных контейнеров по [math]\frac{2 \log n}{c \log\log n}[/math] бит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.


Операция сортировки за линейное время (англ. Linear-Time-Sort)

Входные данные: [math]r \geqslant n^{\frac{2}{5}}[/math] чисел [math]d_{i}[/math], [math]d_{i}.value[/math] — значение числа [math]d_{i}[/math], в котором [math]\frac{2 \log n}{c \log\log n}[/math] бит, [math]d_{i}.set[/math] — набор, в котором находится [math]d_{i}[/math]. Следует отметить, что всего есть [math]t[/math] наборов.

  1. Сортируем все [math]d_{i}[/math] по [math]d_{i}.value[/math], используя bucket sort. Пусть все отсортированные числа в [math]A[1..r][/math]. Этот шаг занимает линейное время, так как сортируется не менее [math]n^{\frac{2}{5}}[/math] чисел.
  2. Помещаем все [math]A[j][/math] в [math]A[j].set[/math].

Сортировка с использованием O(n log log n) времени и памяти

Для сортировки [math]n[/math] целых чисел в диапазоне [math]\{0, 1, \ldots, m - 1\}[/math] предполагается, что в нашем консервативном алгоритме используется контейнер длины [math]O(\log (m + n))[/math]. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.


Берем [math]1/e = 5[/math] для ЭП-дерева Андерссона. Следовательно, у корня будет [math]n^{\frac{1}{5}}[/math] детей, и каждое ЭП-дерево в каждом ребенке будет иметь [math]n^{\frac{4}{5}}[/math] листьев. В отличие от оригинального дерева, за раз вставляется не один элемент, а [math]d^2[/math], где [math]d[/math] — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все [math]d^2[/math] чисел на один уровень. В корне опускаются [math]n^{\frac{2}{5}}[/math] чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на [math]t_{1} = n^{1/5}[/math] наборов [math]S_{1}, S_{2}, \ldots, S_{t_{1}}[/math], в каждом из которых [math]n^{\frac{4}{5}}[/math] чисел и [math]S_{i} \lt S_{j}, i \lt j[/math]. Затем, берутся [math]n^{\frac{8}{25}}[/math] чисел из [math]S_{i}[/math] и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на [math]t_{2} = n^{\frac{1}{5}}n^{\frac{4}{25}} = n^{\frac{9}{25}}[/math] наборов [math]T_{1}, T_{2}, \ldots, T_{t_{2}}[/math], аналогичных наборам [math]S_{i}[/math], в каждом из которых [math]n^{\frac{16}{25}}[/math] чисел. Теперь числа опускаются дальше в ЭП-дереве.

Нетрудно заметить, что перебалансирока занимает [math]O(n \log\log n)[/math] времени с [math]O(n)[/math] времени на уровень, аналогично стандартному ЭП-дереву Андерссона.


Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне [math]s[/math]. Имеется [math]t = n^{1 - (\frac{4}{5})^S}[/math] наборов по [math]n^{(\frac{4}{5})^S}[/math] чисел в каждом. Так как каждый узел на данном уровне имеет [math]p = n^{\frac{1}{5} \cdot (\frac{4}{5})^S}[/math] детей, то на [math]s + 1[/math] уровень опускаются [math]q = n^{\frac{2}{5} \cdot (\frac{4}{5})^S}[/math] чисел для каждого набора, или всего [math]qt \geqslant n^{\frac{2}{5}}[/math] чисел для всех наборов за один раз.


Спуск вниз можно рассматривать как сортировку [math]q[/math] чисел в каждом наборе вместе с [math]p[/math] числами [math]a_{1}, a_{2}, \ldots, a_{p}[/math] из ЭП-дерева, так, что эти [math]q[/math] чисел разделены в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, \ldots, S_{p}[/math] таких, что [math]S_{0} \lt a_{1} \lt \ldots \lt a_{p} \lt S_{p}[/math].


Так как [math]q[/math] чисел не надо полностью сортировать и [math]q = p^2[/math], то можно использовать лемму №6 для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью signature sorting. Для этого используется линейная техника многократного деления (англ. multi-dividing technique).


После [math]g[/math] сокращений бит в signature sorting получаем неконсервативное преимущество в [math](\frac{h}{ \log\log n})^g[/math]. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на лемму №6 для завершения разделения [math]q[/math] чисел с помощью [math]p[/math] чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в [math]w[/math] подзадач разделения на [math]w[/math] поднаборов для какого-то числа [math]w[/math].


Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя лемму №6, делается разделение. Так как получено неконсервативное преимущество в [math](\frac{h}{\log\log n})^g[/math] и работа происходит на уровнях не ниже, чем [math]2 \log\log\log n[/math], то алгоритм занимает [math]O(\frac{qt \log\log n}{g(\log h - \log\log\log n) - \log\log\log n}) = O(\log\log n)[/math] времени.


В итоге разделились [math]q[/math] чисел [math]p[/math] числами в каждый набор. То есть получилось, что [math]S_{0} \lt e_{1} \lt S_{1} \lt \ldots \lt e_{p} \lt S_{p}[/math], где [math]e_{i}[/math] — сегмент [math]a_{i}[/math], полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве [math]B[/math] так, что числа в [math]S_{i}[/math] предшествуют числам в [math]S_{j}[/math] если [math]i \lt j[/math] и [math]e_{i}[/math] хранится после [math]S_{i - 1}[/math], но до [math]S_{i}[/math].


Пусть [math]B[i][/math] находится в поднаборе [math]B[i].subset[/math]. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все [math]B[j][/math] в [math]B[j].subset[/math].

На это потребуется линейное время и место.


Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере [math]\log m \geqslant \log\log\log n[/math], потому что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть [math]\frac{h}{\log\log n}[/math] хешированных значений (сегментов) в себе на уровне [math]\log h[/math] в ЭП-дереве. Полное число хешированных бит в контейнере равно [math](2 \log n)(c \log\log n)[/math] бит. Хешированные биты в контейнере выглядят как [math]0^{i}t_{1}0^{i}t_{2} \ldots t[/math][math]_{\frac{h}{\log\log n}}[/math], где [math]t_{k}[/math]-ые — хешированные биты, а нули — это просто нули. Сначала упаковываем [math]\log\log n[/math] контейнеров в один и получаем [math]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,}[/math][math]_{ \frac{h}{\log\log n}}[/math], где [math]t_{i, k}[/math]: элемент с номером [math]k = 1, 2, \ldots, [/math][math]\frac{h}{\log\log n}[/math] из [math]i[/math]-ого контейнера. Используем [math]O(\log\log n)[/math] шагов, чтобы упаковать [math]w_{1}[/math] в [math]w_{2} = 0[/math][math]^{\frac{jh}{\log\log n}}[/math][math]t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1,}[/math][math]_{ \frac{h}{\log\log n}}[/math][math]t_{2,}[/math][math]_{ \frac{h}{\log\log n}}[/math][math]\ldots t_{\log\log n,}[/math][math]_{ \frac{h}{\log\log n}}[/math]. Теперь упакованные хеш-биты занимают [math]2 \log[/math][math]\frac{n}{c}[/math] бит. Используем [math]O(\log\log n)[/math] времени чтобы распаковать [math]w_{2}[/math] в [math]\log\log n[/math] контейнеров [math]w_{3, k} = 0[/math][math]^{\frac{jh}{\log\log n}}[/math][math]0^{r}t_{k, 1}0^{r}t_{k, 2} \ldots t_{k,}[/math][math]_{ \frac{h}{\log\log n}}[/math] [math]k = 1, 2, \ldots, \log\log n[/math]. Затем, используя [math]O(\log\log n)[/math] времени, упаковываем эти [math]\log\log n[/math] контейнеров в один [math]w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1,}[/math][math]_{ \frac{h}{\log\log n}}[/math][math]0^{r}t_{2, 1} \ldots t_{\log\log n,}[/math][math]_{ \frac{h}{\log\log n}}[/math]. Затем, используя [math]O(\log\log n)[/math] шагов, упаковываем [math]w_{4}[/math] в [math]w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1,}[/math][math]_{ \frac{h}{\log\log n}}[/math][math]t_{2, 1}t_{2, 2} \ldots t_{\log\log n,}[/math][math]_{ \frac{h}{\log\log n}}[/math]. В итоге используется [math]O(\log\log n)[/math] времени для упаковки [math]\log\log n[/math] контейнеров. Считаем, что время, потраченное на один контейнер — константа.

См. также

Источники информации