81
правка
Изменения
Нет описания правки
== Алгоритм ==
Алгоритм построен на основе экспоненциального поискового дерева (далее {{- --}} Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
== Andersson's exponential search tree ==
|id=def1.
|definition=
Контейнер {{- --}} объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д.
}}
{{Определение
==Уменьшение числа бит в числах==
Один из способов ускорить сортировку {{- --}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{--- }} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.
Алгоритм: Пусть целое число <tex>b</tex> >= 0 и пусть <tex>U</tex> = {0, ..., <tex>2^b</tex> - 1}. Класс <tex>H_{b,s}</tex> хэш функций из <tex>U</tex> в {0, ..., <tex>2^s</tex> - 1} определен как <tex>H_{b,s}</tex> = {<tex>h_{a}</tex>| 0 < <tex>a</tex> < <tex>2^b</tex>, и <tex>a</tex> нечетно} и для всех <tex>x</tex> из <tex>U</tex>: <tex>h_{a}(x) = (ax</tex> mod <tex>2^b</tex><tex>)</tex> div <tex>2^{b - s}</tex>
Такая хэш функция может быть найдена за <tex>О(n^3)</tex>.
Следует отметить, что несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex> потому, что хэштрование хэширование используется только для уменьшения количества бит в числе. ==Signature sorting==В данной сортировке используется следующий алгоритм: Предположим, что <tex>n</tex> чисел должны быть сортированы, и в каждом <tex>logm</tex> бит. Мы рассматриваем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>log(m/h)</tex> бит. Теперь мы применяем хэширование ко всем сегментам и получаем <tex>2hlogn</tex> бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>log(m/h)</tex> бит в каждом. Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, ..., <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество числе.
