Сортировка Хана
Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью
, где — количество элементов для сортировки.Данная статья писалась на основе брошюры Хана, посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.
Содержание
Алгоритм
Алгоритм построен на основе экспоненциального поискового дерева (далее — Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
Andersson's exponential search tree
Э.П.дерево с
листьями состоит из корня и (0< <1) Э.П.поддеревьев, в каждом из которых листьев; каждое Э.П.поддерево является сыном корня . В этом дереве уровней. При нарушении баланса дерева, необходимо балансирование, которое требует времени при вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.Необходимая информация
Определение: |
Контейнер — объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д. |
Определение: |
Алгоритм сортирующий | целых чисел из множества называется консервативным, если длина контейнера (число бит в контейнере), является . Если длина больше, то алгоритм не консервативный.
Определение: |
Если мы сортируем целые числа из множества {0, 1, ..., | - 1} с длиной контейнера с >= 1, тогда мы сортируем с не консервативным преимуществом .
Определение: |
Для множества min( Набор ) = min( : принадлежит ) max( ) = max( : принадлежит ) < если max( ) <= min( ) | определим
Уменьшение числа бит в числах
Один из способов ускорить сортировку — уменьшить число бит в числе. Один из способов уменьшить число бит в числе — использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий
памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до . Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования чисел в таблицу размера за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.Алгоритм: Пусть целое число
и пусть . Класс хэш функций из в определен как и для всех из .Данный алгоритм базируется на следующей лемме:
Лемма: |
Даны целые числа >= >= 0 и является подмножеством {0, ..., - 1}, содержащим элементов, и >= С . Функция принадлежащая может быть выбрана за время так, что количество коллизий |
Взяв
мы получим хэш функцию которая захэширует чисел из в таблицу размера без коллизий. Очевидно, что может быть посчитана для любого за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod ) и (div ).Такая хэш функция может быть найдена за
.Следует отметить, что несмотря на размер таблицы
, потребность в памяти не превышает потому, что хэширование используется только для уменьшения количества бит в числе.Signature sorting
В данной сортировке используется следующий алгоритм:
Предположим, что
чисел должны быть сортированы, и в каждом бит. Мы рассматриваем, что в каждом числе есть сегментов, в каждом из которых бит. Теперь мы применяем хэширование ко всем сегментам и получаем бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке чисел по бит в каждом стала задачей по сортировке чисел по бит в каждом.Так же, рассмотрим проблему последующего разделения. Пусть
, , ..., — чисел и — множество чисeл. Мы хотим разделить в наборов таких, что: < { } < < { } < ... < { } < . Т.к. мы используем signature sorting, до того как делать вышеописанное разделение, мы поделим биты в на сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из и оставим только один в каждом числе. По существу для каждого мы возьмем все сегментов. Если соответствующие сегменты и совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в , — сегмент, который выделяется из . Таким образом мы преобразуем начальную задачу о разделении чисел в бит в несколько задач на разделение с числами в бит.Пример:
= 3, = 5, = 7, = 10, S = {1, 4, 6, 8, 9, 13, 14}.
Мы разделим числа на 2 сегмента. Для
получим верхний сегмент 0, нижний 3; верхний 1, нижний 1; верхний 1, нижний 3; верхний 2, нижний 2. Для элементов из S получим: для 1: нижний 1 т.к. он выделяется из нижнего сегмента ; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.Сортировка на маленьких целых
Для лучшего понимания действия алгоритма и материала, изложенного в данной статье, в целом, ниже представлены несколько полезных лемм.
Лемма: |
целых чисел можно отсортировать в наборов , , ..., таким образом, что в каждом наборе чисел и < при < , за время и место с не консервативным преимуществом |
Лемма: |
Выбор -о наибольшего числа среди чисел упакованных в контейнеров может быть сделана за время и с использованием места. Конкретно медиана может быть так найдена. |
Доказательство: |
Так как мы можем делать попарное сравнение | чисел в одном контейнере с числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., -о чисел из 5 контейнеров в один контейнер за константное время. Таким образом набор из медиан теперь содержится в контейнерах. Рекурсивно находим медиану в . Используя уберем хотя бы чисел среди . Затем упакуем оставшиеся из контейнеров в контейнеров и затем продолжим рекурсию.
Лемма: |
Если целых чисел, в сумме использующие бит, упакованы в один контейнер, тогда чисел в контейнерах могут быть отсортированы за время , с использованием места. |
Доказательство: |
Так как используется только | бит в каждом контейнере для хранения чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает времени и места. Потому, что мы используем бит на контейнер нам понадобится