Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 22: Строка 22:
 
|definition=
 
|definition=
 
Для множества <tex>S</tex> определим
 
Для множества <tex>S</tex> определим
min(<tex>S</tex>) = min{<tex>a</tex>|<tex>a</tex> принадлежит <tex>a</tex>}
+
min(<tex>S</tex>) = min(<tex>a</tex>|<tex>a</tex> принадлежит <tex>a</tex>)
max(<tex>S</tex>) = max{<tex>a</tex>|<tex>a</tex> принадлежит <tex>a</tex>}
+
max(<tex>S</tex>) = max(<tex>a</tex>|<tex>a</tex> принадлежит <tex>a</tex>)
 
Набор <tex>S1</tex> < <tex>S2</tex> если max(<tex>S1</tex>) <= min(<tex>S2</tex>)
 
Набор <tex>S1</tex> < <tex>S2</tex> если max(<tex>S1</tex>) <= min(<tex>S2</tex>)
 
}}
 
}}

Версия 21:50, 10 июня 2012

Сортировка Хана (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]