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

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

Алгоритм

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

Andersson's exponential search tree

Э.П.дерево с [math]n[/math] листьями состоит из корня [math]r[/math] и [math]n^e[/math] (0<[math]e[/math]<1) Э.П.поддеревьев, в каждом из которых [math]n^{1 - e}[/math] листьев; каждое Э.П.поддерево является сыном корня [math]r[/math]. В этом дереве [math]O(log(logn))[/math] уровней. При нарушении баланса дерева, необходимо балансирование, которое требует [math]O(nlog(logn))[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Необходимая информация

Определение:

Контейнер — объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д.

Определение:

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

Определение:

Для множества [math]S[/math] определим min([math]S[/math]) = min([math]a[/math]:[math]a[/math] принадлежит [math]S[/math]) max([math]S[/math]) = max([math]a[/math]:[math]a[/math] принадлежит [math]S[/math]) Набор [math]S1[/math] < [math]S2[/math] если max([math]S1[/math]) <= min([math]S2[/math])

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

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

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

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

Лемма:

Даны целые числа [math]b[/math] >= [math]s[/math] >= 0 и [math]T[/math] является подмножеством {0, ..., [math]2^b[/math] - 1}, содержащим [math]n[/math] элементов, и [math]t[/math] >= [math]2^{-s + 1}[/math]С[math]^n_{k}[/math]. Функция [math]h_{a}[/math] принадлежащая [math]H_{b,s}[/math] может быть выбрана за время [math]O(bn^2)[/math] так, что количество коллизий [math]coll(h_{a}, T) \lt = t[/math]

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

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

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

Signature sorting

В данной сортировке используется следующий алгоритм:

Предположим, что [math]n[/math] чисел должны быть сортированы, и в каждом [math]logm[/math] бит. Мы рассматриваем, что в каждом числе есть [math]h[/math] сегментов, в каждом из которых [math]log(m/h)[/math] бит. Теперь мы применяем хэширование ко всем сегментам и получаем [math]2hlogn[/math] бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке [math]n[/math] чисел по [math]m[/math] бит в каждом стала задачей по сортировке [math]n[/math] чисел по [math]log(m/h)[/math] бит в каждом.

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