Изменения

'''Сортировка Хана ''' (Yijie Han)англ. ''Hansort'' ) {{---}} сложный алгоритм сортировки целых чисел со сложностью <texdpi="130">O(n \log\log n)</tex>, где <texdpi="130">n</tex> {{---}} количество элементов для сортировки.

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

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

== Andersson's exponential search tree Экспоненциальное поисковое дерево Андерсона ==ЭП-дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (<tex>0< e < 1</tex>) ЭП-поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое ЭП-поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(n \log\log n)</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(n \log\log n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

{{Определение|definition ==Определения== # Контейнер '''ЭП-дерево''' {{---}} объектэто дерево поиска, в которым котором все ключи хранятся наши данные. Например: 32-битные в листьях этого дерева и 64-битные числа, массивы, вектораколичество детей у каждого узла уменьшается экспоненциально от глубины узла.# Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.# Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с неконсервативным преимуществом <tex>k</tex>.# Для множества <tex>S</tex> определим <tex>\min(S) = \min\limits_{a \in S} a</tex>

==Уменьшение числа бит в числах==Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas1). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий Корень имеет <texdpi="130">O\Theta (mn^e)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до сыновей <texdpi="130">O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел хранимых в контейнере. Для этого используется хеш функция для хеширования <tex>n0 </tex> чисел в таблицу размера e <tex>O(n^21 )</tex> за константное время, без коллизий. Для этого используется хеш модифицированная функция авторства: Dierzfelbinger и RamanВсе сыновья являются ЭП-деревьями.

Алгоритм: Пусть целое число В этом дереве <texdpi="130">b \ge 0</tex> и пусть <tex>U = O(n \{0, log\ldots, 2^b - 1\}log n)</tex>уровней. Класс <tex>H_{bПри нарушении баланса дерева необходимо балансирование,s}</tex> хеш функций из <tex>U</tex> в которое требует <texdpi="130">O(n \{0, log\ldots, 2^s - 1\}log n)</tex> определен как времени при <tex>H_{b,s} dpi= \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex"130">x</tex> из <tex>U: h_{a}(x) = (ax \bmod 2^b) \div 2^{b - s}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>. Если длина больше, то алгоритм базируется на лемме №1:'''неконсервативный'''. }}{{ Определение | 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>s dpi= 2 \log n</tex"130"> получаем хеш функцию S1 <tex>h_{a}S2</tex> которая захеширует если <texdpi="130">n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O\max(n^2S1)</tex> без коллизий. Очевидно, что <tex>h_{a}\leqslant \min(xS2)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, спокойно применяется <tex>h_{a}</tex> ко всему контейнеру, а в результате все хеш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хеш знчения вовлечены только (mod <tex>2^b</tex>) и (div <tex>2^{b - s}</tex>).

Следует отметить{{Лемма|id = lemma2|about = № 2|statement = Выбор <tex dpi="130">s</tex>-ого наибольшего числа среди <tex dpi="130">n</tex> чисел, упакованных в <tex dpi="150">\frac{n}{g}</tex> контейнеров, что несмотря на размер таблицы может быть сделан за время <texdpi="150">O(\frac{n^2\log g}{g})</tex>, потребность в памяти не превышает и с использованием <texdpi="150">O(\frac{n}{g})</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=Signature sorting"130">n</tex>. Затем упакуем оставшиеся из <tex dpi="150">\frac{n}{g}</tex> контейнеров в <tex dpi="150">\frac{3n}{4g}</tex> контейнеров и затем продолжим рекурсию.В данной сортировке используется следующий алгоритм:}}

Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, Для контейнеров вне групп (которых <texdpi="130">\ldots</tex>, <tex>a_sqrt{pn}</tex> {{(g ---}} <tex>p1)</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>} < На это потребуется не более <texdpi="150">O(\ldots</tex> < frac{<tex>a_{pn}</tex>} < <tex>S_{pg})</tex>. Т.к. используется signature sorting, до того как делать вышеописанное разделение, необходимо поделить биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов времени и возьмем некоторые из нихпамяти. Так же делим биты После всего этого используем карманную сортировку вновь для каждого числа из сортировки <texdpi="130">Sn</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> битотсортированы.

{{Лемма|id = lemma4|about = № 4|statement = Примем, что каждый контейнер содержит <tex dpi="130"> \log m > \log n</tex>a_бит, и <tex dpi="130">g</tex> чисел, в каждом из которых <tex dpi="150">\frac{\log m}{1g}</tex> = 3бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <texdpi="150">a_\frac{2\log n}{2g}</tex> бит, и <tex dpi="130">g</tex> маркеров упакованы в один контейнер таким же образом<tex dpi= 5"130">^*</tex>, что и числа, тогда <texdpi="130">a_n</tex> чисел в <tex dpi="150">\frac{n}{3g}</tex> контейнерах могут быть отсортированы по их маркерам за время <tex dpi= 7, "150">O(\frac{n \log\log n}{g})</tex>a_с использованием <tex dpi="150">O(\frac{n}{4g})</tex> памяти.(*): если число <tex dpi= 10"130">a</tex> упаковано как <tex dpi="130">s</tex>-ое число в <tex dpi="130">t</tex>-ом контейнере для чисел, S тогда маркер для <tex dpi="130">a</tex> упакован как <tex dpi= "130">s</tex>\{1, 4, 6, 8, 9, 13, 14\}-ый маркер в <tex dpi="130">t</tex>-ом контейнере для маркеров.

|proof =Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex dpi="150">\frac{\log n}{2}</tex> бит. Сортировка n целых сгруппирует контейнеры для чисел как в sqrt(n) наборов==[[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров для чисел.Постановка задачи и решение некоторых проблем:}}

На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.) потому, что каждое м.ч. теперь содержит только {{Лемма|id = lemma6|about = № 6|statement = <texdpi="130">\log m/ \log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем целых чисел можно отсортировать в данный момент. Положим, что нулевая стадия работает с самыми большим блоком (блок номер <texdpi="130">\log sqrt{n - 1}</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/ \log n</tex> контейнеров с <tex>\log n</tex> м.ч. упакованных в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считается, что она бесплатна. По третьей лемме находим медиану этих <tex>n</tex> м.ч. за время и память <tex>O(n/ \log n)</tex>. Пусть <tex>a</tex> это найденная медиана. Тогда <tex>n</tex> м.ч. могут быть разделены на не более чем три группы: наборов <texdpi="130">S_{1}</tex>, <texdpi="130">S_{2}</tex> и , <texdpi="130">S_{3}\ldots</tex>. , <texdpi="130">S_{1\sqrt{n}</tex> содержит м.ч. которые меньше <tex>a</tex>, <tex>S_{2}</tex> содержит м.ч. равные <tex>a</tex>таким образом, что в каждом наборе <texdpi="130">S_\sqrt{3n}</tex> содержит м.ч. большие <tex>a</tex>. Так же мощность чисел и <texdpi="130">S_{1i}</tex> и <tex>S_{3j} </tex>\le при <texdpi="130">n/2i </tex>. Мощность <tex>S_{2}j</tex> может быть любой. Пусть <tex>S'_{2}</tex> это набор чисел, у которых наибольший блок находится в за время <texdpi="150">S_{2}</tex>. Тогда убираем <tex>\log m/ O(\log n</tex> бит (наибольший блок) из каждого числа из <tex>S'_frac{2}</tex> из дальнейшего рассмотрения. Таким образом после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>\log n</tex> блоков, для каждого числа потребуется не более <tex>\log n</tex> стадий чтобы поместить его в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex>n/ } {\log nk})</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается место <texdpi="130">O(n)</tex> времени из-за с неконсервативным преимуществом <texdpi="130">2 k \log\log n</tex> стадий.

Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <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> для использования леммы шесть. Поэтому предполагается, что <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> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров то время необходимое для помещения м.ч. в их наборы потребуется <tex>O((n \log e)/ \log n)</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]] может быть применена для помещения м.ч. в наборы размера , которым они принадлежат. Так как используется <texdpi="150">O(\sqrtfrac{n\log e}{ \log n})</tex>контейнеров, то проблем не должно бытьвремя, необходимое для помещения м.ч. в их наборы, равно <tex dpi="150">O(\frac{n \log e}{ \log n})</tex>.

Algorithm Sort(<tex>k \log\log n</tex>Стоит отметить, <tex>level</tex>что после нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma3|3]], <tex>a_{0}</tex>[[#lemma4|4]], [[#lemma5|5]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <texdpi="130">a_{1}n</tex>, элементов в наборы размера <texdpi="130">\ldots</tex>, <tex>a_sqrt{tn}</tex>), то проблем быть не должно.

# <tex>if level == 1</tex> тогда изучить размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе разделить этот набор в <tex>\le</tex> 3 набора используя лемму три, чтобы найти медиану а затем использовать лемму 6 для =Алгоритм сортировки. Для набора где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</tex>.# От <tex>u = 1</tex> до <tex>k</tex>## Упаковать <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров, где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>-ых битов <tex>a_{i}</tex> и у которого текущий блок это самый крупный блок.## Вызвать Sort(<tex>k \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данных. Число имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на ткущий блок в нем, так же отправлено назад к <tex>a_{i}</tex>.## Отправить <tex>a_{i}-ые к их наборам, используя лемму шесть.</tex>==

Call Sort(<tex>k \log\log nSort(advantage</tex>, <texdpi="130">\log_{k}((\log n)/4)</tex>, <texdpi="130">a_{0}</tex>, <texdpi="130">a_{1}</tex>, <texdpi="130">\ldots</tex>, <texdpi="130">a_{n - 1}</tex>);

# Поместить Помещаем <texdpi="130">a_{i}</tex> в соответствующий набор с помощью блочной сортировки (англ. ''bucket sort ''), потому, что наборов около <texdpi="130">\sqrt{n}</tex>.# Для каждого набора <texdpi="130">S = </tex>{<texdpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <texdpi="130">t > \sqrt{n}</tex>, вызвать Sort(вызываем <tex>k \log\log nSort(advantage</tex>, <texdpi="130">\log_{k}((\frac{\log n)/}{4})</tex>, <texdpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>).

Время работы алгоритма <texdpi="150">O(\frac{n \log\log n/ }{\log k})</tex>, что доказывает лемму 2.}}

==Уменьшение числа бит в числах==Берем <tex>1/e = 5</tex> для экспоненциального поискового дереве Андерссона. Поэтому у корня будет <tex>n^Один из способов ускорить сортировку {{1/5---}}</tex> детей и каждое ЭП-дерево уменьшить число бит в каждом ребенке будет иметь <tex>n^{4/5}</tex> листьевчисле. В отличии от оригинального дерева, вставляется не один элемент за раз, а <tex>d^2</tex>, где <tex>d</tex> Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество детей узла дереваоставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, где числа должны спуститься вниз. Алгоритм полностью опускает все требующий <texdpi="130">d^2O(m)</tex> чисел на один уровеньпамяти. В корне опускаются Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <texdpi="130">O(n^{2/5})</tex> чисел на следующий уровень. После Для тогочтобы еще ускорить алгоритм, как опустились все числа на следующий уровень и они успешно разделились на <tex>t_{1} = n^{1/5}</tex> наборов <tex>S_{1}необходимо упаковать несколько чисел в один контейнер, S_{2}, \ldots, S_{t_{1}}</tex>чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в каждом из которых контейнере. Для этого используется хеш-функция для хеширования <texdpi="130">n^{4/5}</tex> чисел и <tex>S_{i} < S_{j}, i < j</tex>. Затем, берутся в таблицу размера <texdpi="130">O(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>n^{16/25}</tex> чисел, аналогичным наборам <tex>S_{i}</tex>константное время без коллизий. Теперь числа опускаются дальше в ЭПДля этого используется модифицированная хеш-деревефункция авторства: Dierzfelbinger и Raman.

Нетрудно заметить, что ребалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(n)</tex> временем Данный алгоритм базируется на уровень. Аналогично стандартному ЭП-дереву Андерссона[[#lemma1|лемме №1]].

Спуск вниз можно рассматривать как сортировку ==Сортировка по ключу==Предположим, что <texdpi="130">qn</tex> чисел должны быть отсортированы, и в каждом наборе вместе с <texdpi="130">p</tex> числами <tex>a_{1}, a_{2}, \ldots, a_{p}log m</tex> из ЭП-дерева, такбит. Будем считать, что эти в каждом числе есть <texdpi="130">qh</tex> чисел разделены сегментов, в каждом из которых <texdpi="130">p + 1\log</tex> наборов <texdpi="150">S_{0}, S_\frac{1m}, \ldots, S_{ph}</tex> таких, что бит. Теперь применяем хеширование ко всем сегментам и получаем <texdpi="130">S_{0} < 2h \log n</tex>{бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <texdpi="130">a_{1}n</tex>} < чисел по <texdpi="130">\ldotslog m</tex> бит в каждом стала задачей по сортировке <tex dpi="130">n< {/tex> чисел по <texdpi="130">a_{p}\log</tex>}<texdpi="150"> < S_\frac{m}{ph}</tex>бит в каждом.

Делим числа на два сегмента. Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <texdpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex>, и хотется использовать числа в получим верхний сегмент <texdpi="130">T0</tex> для разделения , нижний <texdpi="130">S3</tex> из ; <texdpi="130">qa_{2}</tex> чисел <tex>b_{1}, b_{2---}, \ldots, b_{q}верхний </texdpi="130"> в <tex>p + 1</tex> наборов , нижний <texdpi="130">S_{0}, S_{1}, \ldots, S_{p}</tex> что ; <texdpi="130">S_a_{03}</tex> < {<tex>a_{1---}</tex>} < верхний <texdpi="130">S_{1}</tex> < , нижний <texdpi="130">\ldots3</tex> < {; <texdpi="130">a_{p4}</tex>{{---} < <tex>S_{p}верхний </texdpi="130">. Назовем это разделением <tex>q2</tex> чисел , нижний <texdpi="130">p2</tex> числами. Пусть Для элементов из S получим: для <tex>h dpi= \log n/(c \log p)</tex> для константы <tex>c "130"> 1</tex>. нижний <texdpi="130">h/ \log\log n \log p1</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <tex>(\log n)/(c \log\log n)</tex> бит. Сначала рассматриваем биты в каждом как он выделяется из нижнего сегмента <texdpi="130">a_{i1}</tex> и каждом ; для <texdpi="130">b_{i}4</tex> как сегменты одинаковой длины нижний <texdpi="130">h/ \log\log n0</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество ; для сортировки, хешируются числа в этих контейнерах (<texdpi="130">a_{i}8</tex>-ом и нижний <texdpi="130">b_{i}0</tex>-ом), чтобы получить ; для <texdpi="130">h/ \log\log n9</tex> хешированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хеш значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш значения считаются за константное время. Затем, посчитав значения, два контейнера объединяются в один. Пусть нижний <texdpi="130">a'_{i}1</tex> хеш контейнер ; для <texdpi="130">a_{i}13</tex>, аналогично верхний <texdpi="130">b'_{i}3</tex>. В сумме хеш значения имеют ; для <texdpi="130">(2 \log n)/(c \log\log n)14</tex> бит. Хотя эти значения разделены на сегменты по верхний <texdpi="130">h/ \log\log n3</tex> бит в каждом контейнере. Между сегментами получаются пустотыТеперь все верхние сегменты, которые забиваются нулями. Сначала упаковываются все нижние сегменты в <texdpi="130">(2 \log n)/(c \log\log n)1</tex> бит. Потом рассматриваются каждый хеш контейнер как число и сортируются эти хеш контейнеры за линейное время (сортировка рассмотрена чуть позже). После этой сортировки биты в <texdpi="130">a_{i}3</tex> и , нижние сегменты <texdpi="130">b_{i}4, 5, 6, 7,</tex> разрезаны на нижние сегменты <texdpi="130">\log\log n/h8, 9, 10</tex>. Таким образом получилось дополнительное мультипликативное преимущество в формируют <texdpi="130">h/ \log\log n4</tex> (additional multiplicative advantage)новые задачи на разделение.

После того, как повторится вышеописанный процесс <tex>g</tex> раз, получится неконсервативное преимущество Использование '''сортировки по ключу''' в <tex>(h/ \log\log n)^g</tex> раз, в то время, как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся за линейное время <tex>O(qt)</tex>.данном алгоритме:

Рассмотрим сортировку за линейное время , о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упаковались упакованы в <texdpi="150">(\frac{2 \log n)/(}{c \log\log n)}</tex> бит. Есть <texdpi="130">t</tex> наборов , в каждом из которых <texdpi="130">q + p</tex> хешированных контейнеров по <texdpi="150">(\frac{2 \log n)/(}{c \log\log n)}</tex> бит в каждом. Эти числа контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш -контейнеры в один pool, сортируем следующим образом.

Входные данные: # Сортируем все <tex>r > dpi= n^{2/5}</tex> чисел <tex"130">d_{i}</tex>, по <texdpi="130">d_{i}.value</tex>, используя bucket sort.value значение Пусть все отсортированные числа в <texdpi="130">d_{i}A[1..r]</tex> в котором . Этот шаг занимает линейное время, так как сортируется не менее <texdpi="150">(2 \log n)/(c ^{\log\log n)</tex> бит, <tex>d_frac{2}{i5}}.set</tex> набор, в котором находится чисел.# Помещаем все <texdpi="130">d_{i}A[j]</tex>, следует отметить что всего в <texdpi="130">tA[j].set</tex> наборов.

# Сортировать все ==Сортировка с использованием O(n log log n) времени и памяти==Для сортировки <texdpi="130">d_{i}n</tex> по целых чисел в диапазоне <texdpi="130">d_\{i0, 1, \ldots, m - 1\}</tex>.value используя bucket sort. Пусть все сортированные числа предполагается, что в A[1..r]. Этот шаг занимает линейное время так как сортируется не менее нашем консервативном алгоритме используется контейнер длины <texdpi="130">O(\log (m + n^{2/5}))</tex> чисел.# Поместить Далее везде считается, что все A[j] числа упакованы в A[j]контейнеры одинаковой длины.set

Теперь для каждого набора собираются все его поднаборы в подзадачах в один набор. Затем используя лемму два, делается разделение. Так Спуск вниз можно рассматривать как получено неконсервативное преимущество сортировку <tex dpi="130">q</tex> чисел в каждом наборе вместе с <texdpi="130">(h/ \log\log n)^gp</tex> и работа происходит на уровнях не ниже чем числами <texdpi="130">a_{1}, a_{2 }, \log\log\log nldots, a_{p}</tex>из ЭП-дерева, так, то алгоритм занимает что эти <tex dpi="130">q</tex> чисел разделены в <tex dpi="130">p + 1</tex>O(qt наборов <tex dpi="130">S_{0}, S_{1}, \log\log nldots, S_{p}</(g(\log h - \log\log\log n) - \log\log\log n)) tex> таких, что <tex dpi= O("130">S_{0} < a_{1} < \log\log n)ldots < a_{p} < S_{p}</tex> времени.

Помещаем все После <texdpi="130">Bg</tex> сокращений бит в [[jСортировка Хана#Signature sorting|signature sorting]]получаем неконсервативное преимущество в </texdpi="150"> в (\frac{h}{ \log\log n})^g</tex>B. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на [[j#lemma6|лемму №6]] для завершения разделения <tex dpi="130">q</tex> чисел с помощью <tex dpi="130">p</tex> чисел на наборы.subsetЗаметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex dpi="130">w</tex>подзадач разделения на <tex dpi="130">w</tex> поднаборов для какого-то числа <tex dpi="130">w</tex>.

Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере В итоге разделились <texdpi="130">\log m \ge \log\log\log nq</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log n</tex> хешированных значений (сегментов) в себе на уровне <texdpi="130">\log hp</tex> числами в ЭП-деревекаждый набор. Полное число хешированных бит в контейнере <tex>(2 \log n)(c \log\log n)</tex> бит. Хотя хешированны биты в контейнере выглядят как То есть получилось, что <texdpi="130">S_{0^{i}t_< e_{1}0^< S_{i1}t_< \ldots < e_{2p} \ldots t_< S_{h/ \log\log np}</tex>, где <texdpi="130">t_e_{ki}</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}сегмент </texdpi="130"> где <tex>t_a_{i, k}</tex>: <tex>k = 1, 2полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, \ldots, h/ \log\log nчто числа хранятся в массиве </texdpi="130"> из <tex>iB</tex>-ого контейнера. Ипользуем <tex>O(\log\log n)</tex> шаговтак, чтобы упаковать что числа в <texdpi="130">w_S_{1i}</tex> предшествуют числам в <texdpi="130">w_S_{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 nj}</tex>. Теперь упакованные хеш биты занимают если <texdpi="130">2 \log n/ci </tex> бит. Используем <tex>O(\log\log n)j</tex> времени чтобы распаковать и <texdpi="130">w_e_{2i}</tex> в <tex>\log\log n</tex> контейнеров хранится после <texdpi="130">w_S_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, i - 1}O^{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} dpi= 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"130">w_S_{4i}</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> контейнеров. Считаем что время потраченное на одно слово {{---}} константа.

==Лемма №2==Пусть <texdpi="130">nB[i]</tex> целых чисел можно отсортировать находится в поднаборе <texdpi="130">\sqrt{n}</tex> наборов <tex>S_{1}B[i].subset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <texdpi="130">S_{2}</tex>, <tex>\ldots</tex>, <tex>S_{\sqrt{n}}B[j]</tex> таким образом, что в каждом наборе <texdpi="130">\sqrt{n}</tex> чисел и <tex>S_{i}</tex> < <tex>S_{B[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].subset</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>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>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>(\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <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 sorting вновь для сортировки <tex>n</tex> контейнеров. таким образом все числа отсортированы.  Заметим, что когда <tex>g = O( \log n)</tex> сортировка <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров произойдет за линейное время <tex>O((n/g) \log\log n)</tex>, с использованием O(n/g) места. Выгода очевидна.==Лемма №5==Если принять, что каждый контейнер содержит <tex> \log m > \log n</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((n \log\log n)/g)</tex> с использованием <tex>O(n/g)</tex> места.(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.  Доказательство: Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>( \log n)/2</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>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \le \log n</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>==См.также==* [[Сортировка подсчетом]]* [[Цифровая сортировка]]

==ЛитераураИсточники информации==# * [http://www.sciencedirect.com/science/article/pii/S019667740300155X Deterministic Sorting in O(n \log\log n) Time and Linear Space. Yijie Han.]# * А. Андерссон. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science. 135-141(1996)* [http://dl.acm.org/citation.cfm?id=1236460 A. Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.]* [[wikipedia:en:Integer_sorting|Wikipedia {{---}} Integer sorting]]

[[Категория: СортировкиСортировка]]