Сортировка с помощью дерева.

Основан на методе прямого выбора. Эта повторяющийся поиск n-го ключа среди n-1 элемента. На первом этапе понадобится сравнение, затем n-2 и тд.

(n²-n)

Оптимизации можно добиться оставляя после каждого прохода больше информации чем просто идентификатор найденного макс и мин.

Проделав n-1 сравнений можно построить дерево выбора и идентифицировать(вычислить) его корень, как наименьший элемент.

06

12 06

    44 12 18 06

44   55         12  42        94    18        06     67

Второй этап сортировки: спуск вдоль пути отмеченного наименьшим элементом и исключение его из дерева путем замены на пустой (дырка) элемент или на элемент из соседний ветви в промежуточной вершинах

    12 18

12         18 42     18

44          12   18         67                44           12             18            67 44 35    12 44      94   18            67        44       55      42   94    18             67

Каждый очередной элемент попавший в корень будет очередным найденых ключем под сортированный массив. Далее исключаем его и т.д. после n таких шагов дерево станет пустым и процесс сортировки заканчивается. На каждом шаге logn сравнений. И для полного алгоритма понадобится еще n шагов.

Эффективная организация дерева из n элементов.

Требует только n единиц памяти.

Уильямс - HeapSort

Пирамида соответствующая дерева получается как последовательность ключей hL,hL+1,..,hR,

такая что для каждого i-го ключа должно выполняться правило h<=h2i hi<=h2i+1 i=L÷R/2

06 12 06 44 12 18 06 44 55 12 42 94 18 06 67

Любое двоичное дерево можно рассматривать как массив построенное по следующей схеме:

h1 h1=min(h1…hn)

h2 h3

h4 h5 h6 h7

Как добавить элемент х в пирамиду?

Сначала Х ставим на верх древовидной структуры, затем он постепенно спускается в низ каждый раз по направлению наименьшего из двух примыкающих к нему элементов. А сам элемент передвигается вверх. Этот сдвигающий алгоритм был использован Флюидом и называется алгоритм сдвигов Флюида.

Пр.

44 h1       x=44

  42 06

55   94 18 12

06

42 12

55 94 18 44

I и j пару индексов фиксирующей элементы меняющиеся на каждом шаге местами.

H1,…,hn hm,..,hn m=n div 2 +1

Правая часть Hm уже образует пирамиду, потому что индексы I,j удовлетворяют отношению J=2i j=2i+1 Эти элементы образуют нижнюю часть элементов, которые не требую упорядочивания. Далее пирамида расширяется влево… Каждый раз добавляется и сдвигами ставится в соответствующую позицию новый элемент.

44 55 12 |42| 94 19 06 67 m=8:2+1=5

55 |06 42 94 18 12 67 44 |42 06 55 94 18 12 67 06 42 44 55 94 18 12 67 3 6 7 06 42 12 55 94 18 44 67

В этом алгоритме каждый элемент добавляемый в пирамиду сохраняется в буфере х для дальнейшей возможно перемены местами с hj в цикле двигаясь по массиве с шагом соответствующем правилу: j=2*I или j=2*i+1

(J<=R) and (aj<x)

ai=x

Процедура shift сдвига:

ai=aj i=j j=2*j

(J<R) and (aj+1<aj)

Procedure shift (L,R:index); - -

i=L, j=2*L, x=aL

end

+

(J<R) and (a_j+1<aj)

-

j=j+1

j=j+1

+ +

-

L=(n div 2) +1

Процесс формирования пирамиды на том же месте.

L>1

Пирамида построена

-

L=L-1

+

shift(L,n)

Второй этап получить полную упорядоченность Необходимо проделать n сдвигающих шагов, причем после каждого шага в вершину выталкивается очередной минимум. Всплывающие элементы будет хранить в том же массиве следующим образом. Каждый раз берем последнюю? в буфер Х. Прячем верхний элемент в освободившиеся места, а ?.

Блок схема для этого

R=n

R>1

x=a1; an=ar; ar=x

Массив отсортирован

06 42 12 55 94 18 44 67 12 42 18 55 94 67 44 |06 18 42 44 55 94 67 |12 06 + 42 55 44 67 94 |18 12 06

R:=R-1

shift(1,R)

44 55 94 67 |42 18 12 06 55 67 94 |44 42 18 12 06 67 94 |55 44 42 18 12 06

Чем больше n тем алгоритм эффективнее.