Изменения

'''Сортировка Хана ''' (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> определим

Набор 1) Корень имеет <texdpi="130">S1\Theta (n^e)</tex> < сыновей <texdpi="130">S2( 0 </tex> если e <tex>\max(S1) \le \min(S21 )</tex>. Все сыновья являются ЭП-деревьями.

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

Алгоритм: Пусть целое число <texdpi="130">b \ge 0</tex> и пусть <tex>U max(S) = \{0, max\ldots, 2^b - 1\}</tex>. Класс <tex>H_limits_{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 (\mod 2)\in S}</tex> и для всех <tex>x</tex> из <tex>U: h_{a}(x) = (ax \mod 2^{b}) div 2^{b - s}</tex>.

Данный алгоритм базируется на следующей лемме: ==Леммы==

|id=lemma1. |about = № 1|statement=Даны целые числа <texdpi="130">b</tex> <tex>\ge</tex> <tex>geqslant s</tex> <tex>\gegeqslant 0</tex> 0 , и <texdpi="130">T</tex> является подмножеством множества <texdpi="130">\{0, \ldots, 2^b - 1\}</tex>, содержащим <texdpi="130">n</tex> элементов, и <texdpi="130">t</tex> <tex>\ge</tex> <tex>geqslant 2^{-s + 1}</tex>С<tex>^k_{n}</tex>. Функция <texdpi="130">h_{a}</tex> , принадлежащая <texdpi="130">H_{b,s}</tex> , может быть выбрана за время <texdpi="130">O(bn^2)</tex> так, что количество коллизий <texdpi="130">coll(h_{a}, T) <tex>\le</tex> leqslant t</tex>.

Взяв <tex>s {{Лемма|id = lemma2|about = № 2 \log n|statement = Выбор </texdpi="130"> получаем хэш функцию <tex>h_{a}s</tex> которая захэширует -ого наибольшего числа среди <texdpi="130">n</tex> чисел из <tex>U</tex> , упакованных в таблицу размера <texdpi="150">O(\frac{n^2)</tex> без коллизий. Очевидно, что <tex>h_}{ag}(x)</tex> контейнеров, может быть посчитана для любого <tex>x</tex> сделан за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, спокойно применяется <texdpi="150">h_O(\frac{an \log g}{g})</tex> ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod и с использованием <texdpi="150">2^b</tex>) и O(div <tex>2^\frac{n}{b - sg})</tex>)памяти. В том числе, так может быть найдена медиана.

 Следует отметить, что несмотря на размер таблицы Для контейнеров вне групп (которых <texdpi="130">O\sqrt{n}(n^2g - 1)</tex>, потребность в памяти штук) разбираем и собираем заново контейнеры. На это потребуется не превышает более <texdpi="150">O(\frac{n}{g})</tex> потомувремени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex dpi="130">n</tex> контейнеров. Таким образом, что хэширование используется только для уменьшения количества бит в числевсе числа отсортированы. ==Signature sorting==В данной сортировке используется следующий алгоритм:

|id=lemma2. lemma4|about = № 4|statement=Примем, что каждый контейнер содержит <texdpi="130">\log m > \log n</tex> целых бит, и <tex dpi="130">g</tex> чисел можно отсортировать , в каждом из которых <texdpi="150">\sqrtfrac{n\log m}{g}</tex> наборов бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <texdpi="150">S_\frac{1\log n}{2g}</tex>бит, и <tex dpi="130">g</tex>S_{2}маркеров упакованы в один контейнер таким же образом<tex dpi="130">^*</tex>, что и числа, тогда <texdpi="130">\ldotsn</tex>, чисел в <texdpi="150">S_{\sqrtfrac{n}{g}</tex> таким образом, что в каждом наборе контейнерах могут быть отсортированы по их маркерам за время <texdpi="150">O(\sqrtfrac{n \log\log n}{g})</tex> чисел и с использованием <texdpi="150">S_O(\frac{in}{g})</tex> < памяти.(*): если число <texdpi="130">S_{j}a</tex> при упаковано как <texdpi="130">is</tex> < -ое число в <texdpi="130">jt</tex>-ом контейнере для чисел, за время тогда маркер для <texdpi="130">O(n \log\log n/ \log k)a</tex> и место упакован как <texdpi="130">O(n)s</tex> с не консервативным преимуществом -ый маркер в <texdpi="130">k \log\log nt</tex>|proof=Доказательство данной леммы будет приведено далее в тексте статьи-ом контейнере для маркеров.}} 

Номер три.{{Лемма|id=lemma3. |statementproof =Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел упакованных в <tex>n/g</tex> контейнеров может Контейнеры для маркеров могут быть сделана за отсортированы с помощью bucket sort потому, что каждый контейнер использует <texdpi="150">O(n \frac{\log g/g)</tex> время и с использованием <tex>O(n/g)}{2}</tex> местабит. Конкретно медиана может быть так найдена.|proof=Так Сортировка сгруппирует контейнеры для чисел как возможно делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex>\ldots</tex>, <tex>g</tex>-ого чисел из 5 [[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров в один контейнер за константное время. Таким образом набор <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> контейнеров и затем продолжим рекурсию.

|id=lemma4.lemma5|about = № 5|statement=Если <tex>g</tex> целых чиселПредположим, в сумме использующие что каждый контейнер содержит <texdpi="130">(\log n)/2</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы за время <tex>O((n/g) m \log\log g)</tex>, с использованием <tex>O(n/g)</tex> места.|proof=Так как используется только <tex>(\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <texdpi="130">O(n/g)</tex> времени и места. Потомучисел, что используется в каждом из которых <texdpi="150">(\frac{\log n)/2m}{g}</tex> бит на , упакованы в один контейнер понадобится , что каждое число имеет маркер, содержащий <texdpi="150">\sqrtfrac{\log n}{2g}</tex> шаблонов для всех контейнеров. Затем поместим бит, и что <texdpi="130">g < (\log n)/2</tex> контейнеров с одинаковым шаблоном маркеров упакованы в одну группуодин контейнер тем же образом что и числа. Для каждого шаблона останется не более Тогда <texdpi="130">g - 1n</tex> контейнеров которые не смогут образовать группу. Поэтому не более чисел в <texdpi="150">\sqrtfrac{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>-ое число из входящего вектора. Эта транспозиция может могут быть сделана отсортированы по своим маркерам за время <texdpi="150">O(g \log g)</tex>, с использованием <tex>O(g)</tex> места. Для всех групп это занимает время <tex>O((frac{n/g) \log }{g})</tex>, с использованием <texdpi="150">O(n/g)</tex> места. Для контейнеров вне групп (которых <tex>\sqrtfrac{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) места. Выгода очевиднапамяти.

Лемма пять.{{Лемма|id=lemma5.|statement=Если принятьЗаметим, что каждый контейнер содержит если длина контейнера <texdpi="130"> \log m > \log\log n</tex> бит, и только <texdpi="130">g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий используется для упаковки <texdpi="130">(g \leqslant \log n)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы чисел в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел выбор в <tex>n/g</tex> контейнерах могут [[#lemma2|лемме №2]] может быть отсортированы по их маркерам сделан за время и память <texdpi="150">O((n \log\log frac{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>-ом контейнере для маркеров.доказательстве [[#lemma2|proof=Контейнеры для маркеров могут лемме №2]] теперь может быть отсортированы с помощью bucket sort потому, что каждый контейнер использует сделана за время <texdpi="150">O( \log frac{n}{g})/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Перемещаем каждую группу контейнеров для чисел.

|id=lemma6.|about = № 6|statement=предположим, что каждый контейнер содержит <texdpi="130">\log m \log\log n > \log n</tex> бит, что <tex>g</tex> целых чисел, можно отсортировать в каждом из которых <texdpi="130">(\log m)/gsqrt{n}</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий наборов <texdpi="130">(\log n)/(2g)S_{1}</tex> бит, и что <texdpi="130">gS_{2}</tex> маркеров упакованы в один контейнер тем же образом что и числа, тогда <texdpi="130">n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)\ldots</tex>, с использованием <texdpi="130">O(S_{\sqrt{n/g)}}</tex> памяти.|proof=Заметимтаким образом, что несмотря на то, что длина контейнера в каждом наборе <texdpi="130">\log m \log\log sqrt{n}</tex> бит всего <tex>\log m</tex> бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел помещаем <texdpi="130">g \log\log nS_{i} < S_{j}</tex> вместо при <texdpi="130">g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей i <tex>g \log\log nj</tex> контейнеров, упаковываем за время <texdpi="150">g \logO(\log frac{n</tex> контейнеров в <tex>g</tex>, упаковывая <tex>\log\log n</tex> контейнеров в один. Далее делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(g } {\log\log nk})</tex> времени для каждой группы и место <texdpi="130">O(n/g)</tex> времени для всех чисел. После завершения транспозиции, распаковываем с неконсервативным преимуществом <texdpi="130">g</tex> контейнеров в <tex>g k \log\log n</tex> контейнеров.}} 

Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки |proof = Алгоритм сортировки <texdpi="130">g \le \log n</tex> целых чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <texdpi="130">O(\sqrt{n/g)}</tex>наборов, потомупредставленный ниже, что упаковка в доказатльстве является доказательством данной леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.

На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее Сложная часть алгоритма заключается в том, как поместить м.ч.) потомув набор, что каждое м.ч. теперь содержит только <tex>\log m/ \log n</tex> бит. Каждое которому принадлежит соответствующее число представлено и соотносится с м.ч., над которым работаем после предыдущих операций деления набора в данный моментнашем алгоритме. ПоложимПредположим, что нулевая стадия работает с самыми большим блоком (блок номер <texdpi="130">\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы чисел уже поделены в <texdpi="130">n/ \log ne</tex> контейнеров с наборов. Используем <texdpi="130">\log ne</tex> мбитов чтобы сделать марки для каждого набора.чТеперь используем [[#lemma5|лемме №5]]. упакованных в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считается, что она бесплатна. По третьей лемме находим медиану этих Полный размер маркера для каждого контейнера должен быть <texdpi="150">\frac{\log n}{2}</tex> м.ч. за время , и память маркер использует <texdpi="130">O(n/ \log n)e</tex>. Пусть бит, значит количество маркеров <texdpi="130">ag</tex> это найденная медиана. Тогда <tex>n</tex> м.ч. могут в каждом контейнере должно быть разделены на не более чем три группы: <texdpi="150">S_\frac{1\log n}</tex>, <tex>S_{2}</tex> и <tex>S_{3\log e}</tex>. В дальнейшем, так как <texdpi="150">S_g = \frac{1\log n}</tex> содержит м.ч. которые меньше <tex>a</tex>, <tex>S_{2\log e}</tex> содержит , м.ч. равные должны влезать в контейнер. Каждый контейнер содержит <texdpi="130">ak \log\log n \log n</tex>блоков, <tex>S_{3}</tex> содержит каждое м.ч. большие может содержать <texdpi="150">a</tex>. Так же мощность <tex>S_O(\frac{1k \log n}</tex> и <tex>S_{3g} ) = O(k \log e)</tex>\le блоков. Заметим, что используется неконсервативное преимущество в <texdpi="130">\log\log n/2</tex>. Мощность для [[#lemma5|лемме №5]] Поэтому предполагается, что <texdpi="150">S_\frac{2\log n}</tex> может быть любой. Пусть <tex>S'_{2\log e}</tex> это набор чиселм.ч., у в каждом из которых наибольший блок находится в <texdpi="130">S_{2}k \log e</tex>блоков битов числа, упакованны в один контейнер. Для каждого м. Тогда убираем ч. используется маркер из <texdpi="130">\log m/ \log ne</tex> бит (наибольший блок) из каждого числа из <tex>S'_{2}</tex> из дальнейшего рассмотрения, который показывает, к какому набору он принадлежит. Таким образом после первой стадии каждое число находится Предполагаем, что маркеры так же упакованы в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотренияконтейнеры, как и м.ч. Так как в каждом числе только каждый контейнер для маркеров содержит <texdpi="150">\frac{\log n}{2 \log e}</tex> блоковмаркеров, то для каждого числа потребуется не более контейнера требуется <texdpi="150">\frac{\log n}{2}</tex> стадий чтобы поместить его бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированынаборы, которым они принадлежат. Так как на каждой стадии работаем с используется <texdpi="150">O(\frac{n/ \log e}{ \log n})</tex> контейнерамиконтейнеров, то игнорируя время, необходимое на упаковку для помещения м.ч. в контейнеры и помещение м.ч. в нужный наборих наборы, затрачивается равно <texdpi="150">O(\frac{n)</tex> времени из-за <tex>2 \log e}{ \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> времениПри таком помещении сразу возникает следующая проблема.

Стоит отметить, что процесс помещения нестабиленпосле нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma3|3]], т.к[[#lemma4|4]], [[#lemma5|5]] расчитаны на не очень маленькие наборы. основан на алгоритме Но поскольку сортируется набор из леммы шесть<tex dpi="130">n</tex> элементов в наборы размера <tex dpi="130">\sqrt{n}</tex>, то проблем быть не должно.

Рассмотрим число Algorithm IterateSortCall <tex>aSort(advantage</tex>, которое является <texdpi="130">i</tex>-ым в наборе <tex>S</tex>. Рассмотрим блок <tex>a</tex> \log_{k}((назовем его <tex>a'</tex>\log n), который является <tex>i</tex>-ым м.ч. в <tex>S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex>a</tex> (назовем это <tex>a''</tex>4) в <tex>S</tex>, <texdpi="130">a''</tex> просто перемещен на позицию в наборе <tex>Sa_{0}</tex>, но не обязательно на позицию <tex>i</tex> (где расположен <tex>a'</tex>). Если значение блока <texdpi="130">a'a_{1}</tex> одинаково для всех чисел в <tex>S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex>S</tex> помещен <tex>a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем dpi="текущий блок набора130". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, помещаются последующие блоки вместе с текущим блоком в набор. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex>k \log eldots</tex> блоков это текущий блок. Таким образом после того, как помещены эти <texdpi="130">k \log ea_{n - 1}</tex> блоков в набор, удаляется изначальный текущий блок, потому, что известно, что эти <tex>k \log e</tex> блоков перемещены в правильный набор и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex>k \log e</tex> блоках.);

Время работы алгоритма Алгоритм: Пусть целое число <texdpi="130">Ob \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 (n \logbmod 2)\log n}</tex> и для всех <tex dpi="130">x</tex> из <tex dpi="130">U</tex>: <tex dpi="130">h_{a}(x) = (ax</ tex> <tex dpi="130">\log kbmod</tex> <tex dpi="130">2^b)</tex>, что доказывает лемму <tex dpi="130">div</tex> <tex dpi="130">2^{b - s}</tex>.

==Собственно сортировка с использованием O(nloglogn) времени и памяти==Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, \ldots, m - 1</tex>} предполагается, что используем контейнер длины <tex>O(\log (m + n))</tex> в нашем консервативном алгоритме. Далее всегда считается, что все числа упакованы в контейнеры одинаковой длиныДанный алгоритм базируется на [[#lemma1|лемме №1]].

Нетрудно заметить==Сортировка по ключу==Предположим, что ребалансирока занимает <texdpi="130">O(n </tex> чисел должны быть отсортированы, и в каждом <tex dpi="130">\logm</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> времени с бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <texdpi="130">O(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 dpi="130">a_{1}</tex> получим верхний сегмент <texdpi="130">q0</tex> чисел в каждом наборе вместе с , нижний <texdpi="130">p3</tex> числами ; <texdpi="130">a_{2}</tex> {{---}} верхний <tex dpi="130">1}</tex>, нижний <tex dpi="130">1</tex>; <tex dpi="130">a_{23}</tex> {{---}}верхний <tex dpi="130">1</tex>, \ldots, нижний <tex dpi="130">3</tex>; <tex dpi="130">a_{p4}</tex> из ЭП{{---дерева, так}} верхний <tex dpi="130">2</tex>, что эти нижний <texdpi="130">q2</tex> чисел разделены в . Для элементов из S получим: для <texdpi="130">p + 1</tex> наборов нижний <tex dpi="130">1</tex>S_{0}, S_так как он выделяется из нижнего сегмента <tex dpi="130">a_{1}, \ldots, S_{p}</tex> таких, что ; для <tex dpi="130">4</tex> нижний <tex dpi="130">0</tex>; для <tex dpi="130">8</tex> нижний <texdpi="130">S_{0} < /tex>; для <tex dpi="130">9</tex>{нижний <texdpi="130">a_{1}</tex>} ; для <tex dpi="130">13</tex> верхний <tex dpi="130">3</tex>; для <tex dpi="130">14</tex> верхний < tex dpi="130">3</tex>\ldots. Теперь все верхние сегменты, нижние сегменты <tex dpi="130">1</tex> и < {tex dpi="130">3</tex>, нижние сегменты <texdpi="130">a_{p}4, 5, 6, 7,</tex>}нижние сегменты <tex dpi="130">8, 9, 10</tex> формируют < S_{p}tex dpi="130">4</tex>новые задачи на разделение.

Так как не надо полностью сортировать <tex>q</tex> чисел и <tex>q = p^2</tex>, то есть возможность использовать лемму 2 для Использование '''сортировки. Для этого необходимо неконсервативное преимущество, которое получается ниже. Для этого используется линейная техника многократного деления (multi-dividing technique), чтобы добиться этого.по ключу''' в данном алгоритме:

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

Хэш функция, которая используется, находится следующим образом. Будут хэшироватся сегменты, которые Входные данные: <texdpi="150">r \loggeqslant n^{\log n/hfrac{2}{5}}</tex>-ые, чисел <texdpi="130">(\log\log n/h)^2d_{i}</tex>-ые, <texdpi="130">\ldotsd_{i}.value</tex> от всего — значение числа. Для сегментов вида <texdpi="130">(\log\log n/h)^td_{i}</tex>, получаем нарезанием всех в котором <texdpi="150">p</tex> чисел на <tex>(\frac{2 \log n}{c \log\log n/h)^t}</tex> сегментов. Рассматривая каждый сегмент как числобит, получится <texdpi="130">p(\log\log n/h)^td_{i}.set</tex> чисел. Затем получаем одну хэш функцию для этих чисел. Так как — набор, в котором находится <texdpi="130">t < \log nd_{i}</tex> то. Следует отметить, получится не более что всего есть <texdpi="130">\log nt</tex> хэш функцийнаборов.

Входные данные: Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <texdpi="130">r s</tex> . Имеется <tex dpi="150">t = n^{2/1 - (\frac{4}{5})^S}</tex> чисел наборов по <texdpi="150">d_n^{(\frac{i4}</tex>, <tex>d_{i5})^S}</tex>чисел в каждом.value значение числа Так как каждый узел на данном уровне имеет <texdpi="150">d_p = n^{\frac{i1}{5}</tex> в котором <tex>(2 \log n)/cdot (c \log\log nfrac{4}{5})^S}</tex> битдетей, то на <texdpi="130">d_{i}.sets + 1</tex> набор, в котором находится уровень опускаются <texdpi="150">d_q = n^{\frac{2}{5} \cdot (\frac{i4}{5})^S}</tex>чисел для каждого набора, следует отметить что или всего <texdpi="150">tqt \geqslant n^{\frac{2}{5}}</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>.

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

Помещаем Пусть <tex dpi="130">B[i]</tex> находится в поднаборе <tex dpi="130">B[i].subset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <texdpi="130">B[j]</tex> в <texdpi="130">B[j].subset</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}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} = 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> контейнеров. Считаем что время потраченное на одно слово {{---}} константа.* [[Сортировка подсчетом]]* [[Цифровая сортировка]]

==ЛитераураИсточники информации==# * [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]]

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