Изменения

'''Сортировка Хана ''' (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 Экспоненциальное поисковое дерево Андерсона == {{Определение|definition = '''ЭП-дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> ''' {{---}} это дерево поиска, в котором все ключи хранятся в листьях этого дерева и количество детей у каждого узла уменьшается экспоненциально от глубины узла.}} [[Файл:Exp-tree.png|400px|thumb|right|Общая структура ЭП-дерева]] Структура ЭП-дерева: 1) Корень имеет <texdpi="130">\Theta (n^e)</tex> (сыновей <texdpi="130">( 0< e < 1)</tex>) . Все сыновья являются ЭП-поддеревьев, в каждом из которых деревьями. 2) Каждое поддерево корня имеет <texdpi="130">\Theta(n^{1 - e})</tex> листьев; каждое ЭП-поддерево является сыном корня <tex>r</tex>сыновей.  В этом дереве <texdpi="130">O(n \log\log n)</tex> уровней. При нарушении баланса дерева необходимо балансирование, которое требует <texdpi="130">O(n \log\log n)</tex> времени при <texdpi="130">n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.

Алгоритм, сортирующий <texdpi="130">n</tex> целых чисел из множества <texdpi="130">\{0, 1, \ldots, m - 1\}</tex>, называется '''консервативным''', если длина контейнера (число бит в контейнере) равна <texdpi="130">O(\log(m + n))</tex>. Если длина больше, то алгоритм '''неконсервативный'''.

Если сортируются целые числа из множества <texdpi="130">\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <texdpi="130">k \log (m + n)</tex> с <texdpi="130">k</tex> <tex>\gegeqslant 1</tex> 1, тогда сортировка происходит с '''неконсервативным преимуществом''' <texdpi="130">k</tex>.

Для множества <texdpi="130">S</tex> определим

<texdpi="130">\min(S) = \min\limits_{a \in S} a</tex>

<texdpi="130">\max(S) = \max\limits_{a \in S} a</tex>

Набор <texdpi="130">S1</tex> < <tex>S2</tex> если <texdpi="130">\max(S1) \le leqslant \min(S2)</tex>

Предположим, есть набор <texdpi="130">T</tex> из <texdpi="130">p</tex> чисел, которые уже отсортированы как <texdpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex> и набор <texdpi="130">S</tex> из <texdpi="130">q</tex> чисел <texdpi="130">b_{1}, b_{2}, \ldots, b_{q}</tex>. Тогда '''разделением''' <texdpi="130">q</tex> чисел <texdpi="130">p</tex> числами называется <texdpi="130">p + 1</tex> набор <texdpi="130">S_{0}, S_{1}, \ldots, S_{p}</tex>, где <texdpi="130">S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>.

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

Берем <tex>1/e = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex>n^{1/5}</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь <tex>n^{4/5}</tex> листьев. В отличие от оригинального дерева, зараз вставляется не один элемент, а <tex>d^Лемма|id = lemma2|about = № 2|statement = Выбор </texdpi="130">, где <tex>ds</tex> — количество детей узла дерева, в котором -ого наибольшего числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются среди <texdpi="130">n^{2/5}</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на упакованных в <tex>t_{1} dpi= n^{1/5}</tex> наборов <tex"150">S_{1}, S_{2}, \ldots, S_{t_frac{1}}</tex>, в каждом из которых <tex>n^{4/5}</tex> чисел и <tex>S_{i} < S_{jg}, i < j</tex>. Затемконтейнеров, берутся может быть сделан за время <texdpi="150">O(\frac{n^{(4/5)(2/5)\log g}</tex> чисел из <tex>S_{ig})</tex> и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на с использованием <tex>t_{2} dpi= n^{1/5}n^{4/25} = n^{9/25}</tex"150"> наборов <tex>T_{1}, T_{2}, O(\ldots, T_frac{t_{2}}</tex>, аналогичных наборам <tex>S_{in}</tex>, в каждом из которых <tex>n^{16/25g})</tex> чиселпамяти. Теперь числа опускаются дальше в ЭП-деревеВ том числе, так может быть найдена медиана.

Нетрудно заметить|proof = Так как возможно делать попарное сравнение <tex dpi="130">g</tex> чисел в одном контейнере с <tex dpi="130">g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, что перебалансирока занимает <tex dpi="130">\ldots</tex>O(, <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">\logfrac{n}{4}</tex> чисел среди <tex dpi="130">n</tex>. Затем упакуем оставшиеся из <tex dpi="150">\log frac{n)}{g}</tex> времени с контейнеров в <texdpi="150">O(n)\frac{3n}{4g}</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссонаконтейнеров и затем продолжим рекурсию.}}

Спуск вниз можно рассматривать как сортировку <tex>q</tex> чисел в каждом наборе вместе с Для контейнеров вне групп (которых <texdpi="130">p</tex> числами <tex>a_{1}, a_{2}, \ldots, a_sqrt{pn}</tex> из ЭП(g -дерева, так, что эти <tex>q</tex> чисел разделены в <tex>p + 1)</tex> наборов штук) разбираем и собираем заново контейнеры. На это потребуется не более <texdpi="150">S_{0}, S_{1}, O(\ldots, S_{p}</tex> таких, что <tex>S_frac{0n} < </tex> {<tex>a_{1g})</tex>} времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <texdpi="130"><</tex> <tex>\ldots</tex> <tex><</tex> {<tex>a_{p}</tex>} <tex>< S_{p}n</tex>контейнеров. Таким образом, все числа отсортированы.

Так как Заметим, что когда <texdpi="130">qg = O( \log n)</tex>, сортировка <tex dpi="130">O(n)</tex> чисел не надо полностью сортировать и в <tex dpi="150">\frac{n}{g}</tex>q контейнеров произойдет за время <tex dpi= p^2"150">O((\frac{n}{g})</tex> <tex dpi="130">\log\log n)</tex>, то можно использовать '''лемму №2''' для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью signature sorting. Для этого используется линейная техника многократного деления использованием <tex dpi="150">O(multi-dividing technique\frac{n}{g})</tex> памяти. Выгода очевидна.}}

Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем{{Лемма|id = lemma5|about = № 5|statement =Предположим, используя '''лемму №2''', делается разделение. Так как получено неконсервативное преимущество в что каждый контейнер содержит <texdpi="130">(h/ \logm \log\log n > \log n)^</tex> бит, что <tex dpi="130">g</tex> и работа происходит на уровнях не нижечисел, чем в каждом из которых <texdpi="150">2 \log\logfrac{\log nm}{g}</tex>бит, то алгоритм занимает упакованы в один контейнер, что каждое число имеет маркер, содержащий <texdpi="150">O(qt \logfrac{\log n}{2g}</(tex> бит, и что <tex dpi="130">g(\log h - \log\log</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <tex dpi="130">n</tex> чисел в <tex dpi="150">\log frac{n) - \log\log}{g}</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex dpi="150">O(\log frac{n}{g})) </tex> с использованием <tex dpi= "150">O(\log\log frac{n}{g})</tex> временипамяти.

На это потребуется линейное {{Лемма|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>\log m \ge \log\log\log n</tex>, потому что в противном случае можно использовать radix sort для |proof = Алгоритм сортировки чисел. У контейнера есть <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} dpi= 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"130">, где <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} dpi= 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"130">O(\log\log n)</tex> времени, упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_sqrt{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1, h/ \log\log n}0^{r}t_{2, 1} \ldots t_{\log\log n, h/ \log\log n}</tex>. Затем, используя <tex>O(\log\log n)</tex> шагов, упаковываем <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>. В итоге используется <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаемнаборов, что времяпредставленный ниже, потраченное на один контейнер — константаявляется доказательством данной леммы.

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

Алгоритм: Пусть целое число Рассмотрим проблему сортировки <texdpi="130">b \ge 0n</tex> и пусть целых чисел из множества <texdpi="130">U = \{0, 1, \ldots, 2^b m - 1\}</tex>. Класс в <texdpi="130">H_\sqrt{b,sn}</tex> хеш-функций из наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <texdpi="130">Uk \log\log n \log m</tex> бит и хранит число в <texdpi="130">\log m</tex> бит. Поэтому неконсервативное преимущество {0, \ldots, 2^s {--- 1\}}</texdpi="130"> определен как k \log \log n</tex>H_{b. Также предполагаем,s} что <tex dpi= "130">\{h_{a} log m \mid 0 < a < 2^b, a geqslant \equiv 1 (log n \bmod 2)log\}log n</tex> и . Иначе можно использовать radix sort для всех сортировки за время <texdpi="130">xO(n \log\log n)</tex> из и линейную память. Делим <texdpi="130">U\log m</tex>: бит, используемых для представления каждого числа, в <texdpi="130">h_{a}(x) = (ax\log n</tex> блоков. Таким образом, каждый блок содержит как минимум <texdpi="130">\bmodlog\log n</tex> бит. <texdpi="130">2^b)i</tex> -ый блок содержит с <texdpi="150">div\frac{i \log m} {\log n}</tex> -ого по <texdpi="150">2^(\frac{(i + 1) \log m} {b \log n - s1})</tex>-ый биты.Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex dpi="130">2 \log n</tex>-уровневый алгоритм, который работает следующим образом:

Такая хеш-функция может быть найдена за <tex>O(n^3)</tex>Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma5|леммы №5]].

==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>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>.

Делим числа на 2 сегмента. Для Algorithm <tex>a_{1}Sort(advantage</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}level</tex> {{---}} верхний 1, нижний 1; <tex>a_{30}</tex> {{---}} верхний 1, нижний 3; <tex>a_{41}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим: для 1 нижний 1<tex>\ldots</tex>, так как он выделяется из нижнего сегмента <tex>a_{1t}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.)

Использование '''signature sorting''' # Если <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 IterateSortCall <tex>TSort(advantage</tex> из <tex>p</tex> чисел, которые отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>. Используем числа в <tex>T</tex> для разделения набора <tex>S</tex> из <texdpi="130">q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_log_{0k}, 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 n4)</tex> бит. Сначала рассматриваем биты в каждом , <texdpi="130">a_{i}</tex> и каждом <tex>b_{i0}</tex> как сегменты одинаковой длины <tex>h/ \log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (<texdpi="130">a_{i1}</tex>-ом и <tex>b_{i}</tex>-ом) хешируются, и получается <texdpi="130">h/ \log\log nldots</tex> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть <tex>a'_{i}</tex> {{---}} хеш-контейнер для <texdpi="130">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_{i1}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex> сегментов. Таким образом, получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).;

После тогоот 1 до 5# Помещаем <tex dpi="130">a_{i}</tex> в соответствующий набор с помощью блочной сортировки (англ. ''bucket sort''), как вышеописанный процесс повторится потому что наборов около <texdpi="130">g\sqrt{n}</tex> раз, получится неконсервативное преимущество в .# Для каждого набора <texdpi="130">(hS = </ tex>{<tex dpi="130">a_{i_{0}}, a_{i_{1}}, \logldots, a_{i_{t}}</tex>}, если <tex dpi="130">t > \log sqrt{n)^g}</tex> раз, в то время как потрачено только вызываем <tex>OSort(gqt)advantage</tex> времени, так как каждое многократное деление происходит за линейное время <texdpi="130">O\log_{k}(qt\frac{\log n}{4})</tex>, <tex dpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>).

Рассмотрим ==Уменьшение числа бит в числах==Один из способов ускорить сортировку за линейное время, о которой было упомянуто ранее{{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). ПредполагаетсяДеление пополам заключается в том, что хешированные значения для каждого контейнера упакованы количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <texdpi="130">O(2 \log n)/(c \log\log nm)</tex> битпамяти. Есть Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <texdpi="130">tO(n)</tex> наборов. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в каждом из которых контейнере. Для этого используется хеш-функция для хеширования <texdpi="130">q + pn</tex> хешированных контейнеров по чисел в таблицу размера <texdpi="130">O(n^2 \log n)/(c \log\log n)</tex> бит в каждом. Эти контейнеры должны быть отсортированы в каждом набореза константное время без коллизий. Комбинируя все Для этого используется модифицированная хеш-контейнеры в один pool, сортируем следующим образомфункция авторства: Dierzfelbinger и Raman.  Procedure '''Linear-Time-Sort'''

# Сортируем все Алгоритм: Пусть целое число <tex dpi="130">b \geqslant 0</tex> и пусть <texdpi="130">d_U = \{i0, \ldots, 2^b - 1\}</tex> по . Класс <texdpi="130">d_H_{ib,s}.value</tex>, используя bucket sort. Пусть все отртированные числа хеш-функций из <tex dpi="130">U</tex> в <texdpi="130">A[\{0, \ldots, 2^s - 1..r]\}</tex>. Этот шаг занимает линейное время, так определен как сортируется не менее <texdpi="130">nH_{b,s} = \{h_{a} \mid 0 < a < 2^{b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex dpi="130">x</5tex> из <tex dpi="130">U</tex>: <tex dpi="130">h_{a}(x) = (ax</tex> <tex dpi="130">\bmod</tex> чисел.# Помещаем все <texdpi="130">2^b)</tex> <tex dpi="130">A[j]div</tex> в <texdpi="130">A[j].set2^{b - s}</tex>.

==Лемма Данный алгоритм базируется на [[#lemma1|лемме №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>]].

Алгоритм сортировки Такая хеш-функция может быть найдена за <texdpi="130">O(n^3)</tex> целых чисел в <tex>\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.

Следует отметить, что, несмотря на размер таблицы <tex dpi==Сортировка "130">O(n целых чисел ^2)</tex>, потребность в sqrtпамяти не превышает <tex dpi="130">O(n) наборов==Постановка задачи и решение некоторых проблем:</tex>, потому что хеширование используется только для уменьшения количества бит в числе.

Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <texdpi="130">n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем '''лемму №6'''. Полный размер маркера для каждого контейнера должен быть <tex>\log n/2</tex>, и маркер использует <tex>\log e</tex> битa_{1} = 3, значит количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>\log n/(a_{2\log e)</tex>. В дальнейшем} = 5, так как <tex>g a_{3} = \log n/(2 \log e)</tex>7, м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>k \log\log n \log n</tex> блоковa_{4} = 10, каждое м.ч. может содержать <tex>O(k \log n/g) S = O(k \log e)</tex> блоков. Заметим{1, что используется неконсервативное преимущество в <tex>\log\log n</tex> для '''леммы №6'''. Поэтому предполагается4, что <tex>\log n/(2 \log e)</tex> м.ч., в каждом из которых <tex>k \log e</tex> блоков битов числа6, упакованны в один контейнер. Для каждого м.ч. используется маркер из <tex>\log e</tex> бит8, который показывает9, к какому набору он принадлежит. Предполагаем13, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит <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)/ 14\log n)}</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> новые задачи на алгоритме из '''леммы №6'''разделение.

Рассмотрим число <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''' расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из как вышеописанный процесс повторится <texdpi="130">ng</tex> элементов раз, получится неконсервативное преимущество в наборы размера <texdpi="150">(\sqrtfrac{h} {\log\log n})^g</tex>раз, в то проблем быть не должновремя как потрачено только <tex dpi="130">O(gqt)</tex> времени, так как каждое многократное деление происходит за линейное время <tex dpi="130">O(qt)</tex>.

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

# Если <tex>(level == 1)</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\le</tex> 3 набора, используя Операция '''лемму №3сортировки за линейное время''', чтобы найти медиану, а затем используем '''лемму №6(англ. ''' для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.# От <tex>u = 1</tex> до <tex>k</tex>## Упаковываем <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>Linear-ых номеров контейнеров. Где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>Time-ых битов <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'''.)

КонецВходные данные: <tex dpi="150">r \geqslant n^{\frac{2}{5}}</tex> чисел <tex dpi="130">d_{i}</tex>, <tex dpi="130">d_{i}.value</tex> — значение числа <tex dpi="130">d_{i}</tex>, в котором <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, <tex dpi="130">d_{i}.set</tex> — набор, в котором находится <tex dpi="130">d_{i}</tex>. Следует отметить, что всего есть <tex dpi="130">t</tex> наборов.

Algorithm IterateSortCall Sort==Сортировка с использованием O(<tex>k \n log\log n) времени и памяти==Для сортировки </texdpi="130">, <tex>\log_{k}((\log n)/4)</tex>, целых чисел в диапазоне <texdpi="130">a_\{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots, m - 1\}</tex>предполагается, что в нашем консервативном алгоритме используется контейнер длины <texdpi="130">a_{O(\log (m + n - 1}))</tex>);. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.

Время работы алгоритма Берем <texdpi="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">O(n ^{\logfrac{4}{5}}</tex> чисел и <tex dpi="130">S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex dpi="150">n^{\log 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}, \log k)ldots, T_{t_{2}}</tex>, аналогичных наборам <tex dpi="130">S_{i}</tex>, что доказывает '''лемму №2'''в каждом из которых <tex dpi="150">n^{\frac{16}{25}}</tex> чисел. Теперь числа опускаются дальше в ЭП-дереве.

==Лемма №3==Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чиселНетрудно заметить, упакованных в <tex>n/g</tex> контейнеров, может быть сделан за время что перебалансирока занимает <texdpi="130">O(n \log g/g\log n)</tex> и времени с использованием <texdpi="130">O(n/g)</tex> памяти. В том числевремени на уровень, так может быть найдена медианааналогично стандартному ЭП-дереву Андерссона.

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

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

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

Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует Пусть <texdpi="130">( \log n)B[i]</2tex> находится в поднаборе <tex dpi="130">B[i].subset</tex> бит. Сортировка сгруппирует контейнеры Чтобы позволить разделению выполниться, для чисел как каждого поднабора помещаем все <tex dpi="130">B[j]</tex> в '''лемме №4'''<tex dpi="130">B[j]. Перемещаем каждую группу контейнеров для чиселsubset</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> чисел в один контейнер, тогда выбор в '''лемме №3''' может быть сделан за время и память <tex>O(n/g)</tex>, потому что упаковка в доказательстве '''леммы №3''' теперь может быть сделана за время <tex>O(n/g)</tex>==См.также==* [[Сортировка подсчетом]]* [[Цифровая сортировка]]

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

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