17. Сортировка извлечением. Древесная сортировка. Временная сложность алгоритмов.

 

Сортировка извлечением, которую можно описать в нерекурсивной форме, состоит из (n-1)-го этапа; на k-м этапе разыскивается элемент с минимальным ключом среди тех, которые еще не отсортированы окончательно, и помещается в k-ю позицию.

                        ...

            for i:=1 to n-1 do

             begin

                        min:=a[i].key;

                        i_min:=i;

                        for j:=i+1 to n do

                                   begin if a[j].key<min then begin min:=a[j].key; i_min:=j end end;

                        buf:=a[i]; a[i]:=a[i_min]; a[i_min]:=buf

             end;

                        ...

           

            Таблица 3.2 иллюстрирует работу сортировки извлечением.

Таблица 3.2.

 

Начальные данные

 

i=2 (ситуация не изменилась: элемент с кл. 22 уже стоит на своем месте)

j

1

2

3

4

 

j

1

2

3

4

a[j].key

33

22

44

11

 

a[j].key

11

22

44

33

i=1 (элемент с кл. 11 встал на свое место)

 

i=3 (элемент с кл. 33 встал на свое место)

j

1

2

3

4

 

j

1

2

3

4

a[j].key

11

22

44

33

 

a[j].key

11

22

33

44

 

            Как средняя, так и максимальная сложность этого алгоритма O(n2). Практика показывает, что он не на много лучше пузырьковой сортировки. Основной недостаток сортировки извлечением в том, что выполняемые на каждом этапе сравнения дают намного более богатую информацию, чем та, которая эффективно используется.

            Пример. На первом шаге (см. табл.3.2) были проведены сравнения: 11<22, 22<33. В результате был сделан только тот вывод, что 11 стоит на первом месте, хотя следовало использовать и то, что 33 уже никак не может встать во вторую позицию и место для него следует искать, начиная с третьей позиции.

 

            Уильямс и Флойд усовершенствовали сортировку извлечением, получив алгоритм, называемый древесная сортировка (HeapSort). В этом алгоритме используется двоичное дерево, вершины которого помечаются элементами сортируемой последовательности. Затем процедура Heap меняет размещение этих элементов на дереве до тех пор, пока ключ элемента, соответствующего произвольной вершине, станет не меньше ключей элементов, соответствующих ее потомкам. Такое помеченное дерево называется сортирующим.

            Особенности сортирующего дерева состоят в том, что последовательность элементов, лежащих на пути из любой концевой вершины в корень, линейно упорядочена по ключу и элемент с наибольшим ключом всегда соответствует корню. (Пример сортирующего дерева приведен на рис. 3.6,б.)

            На следующем шаге алгоритма древесной сортировки из сортирующего дерева удаляется элемент с наибольшим ключом (из корня). Метка некоторой концевой вершины переносится в корень, а сама концевая вершина удаляется.  Затем полученное дерево переделывается в сортирующее и процесс повторяется.

            Средняя и максимальная сложность алгоритма древесной сортировки O(n logn) вне зависимости от того, как первоначально распределены ключи упорядочиваемой последовательности. Таким образом, этот метод является самым надежным из всех сортировок с помощью сравнений.

            Хранить сортирующее дерево лучше не цепным способом, а сплошным (см. §8 гл. I), в виде массива A[1..n], в котором а[1] - элемент, помещенный в корень, а[2i] и а[2i+1] - элементы в левом и правом потомках той вершины, в которой хранится элемент а[i].

            Формирует сортирующее дерево рекурсивная процедура Heap, которая из трех элементов а[i], а[2i] и а[2i+1] выбирает элемент а[k] с максимальным ключом и, если k<>i, переставляет этот элемент с элементом а[i]. Параметры процедуры Heap - first и  last - задают область ячеек массива А, обладающую свойством сортирующего дерева.

            Общее время, затрачиваемое процедурой Heap, O(n).

            На рис. 3.6 представлены два бинарных дерева - до обработки процедурой Heap (рис. 3.6,а) и после нее (рис. 3.6,б).

     Рис. 3.6.

            Древесная сортировка рекомендуется для упорядочения последовательностей с размерностью от 100 и более элементов.

            На рис.3.7 представлены процедуры, реализующие алгоритм древесной сортировки.

procedure Heap(first,last: integer);

 var k,k2,k21:integer; buf:node;

 begin

    if first<=(last div 2) then

      begin

        k:=first; k2:=2*first; k21:=k2+1;

        if a[first].key<a[k2].key then k:=k2;

        if ((k21)<=last) and (a[k].key<a[k21].key) then k:=k21;

        if k<>first then

           begin buf:=a[first]; a[first]:=a[k]; a[k]:=buf; Heap(k,last) end

      end

 end;

procedure BuildSortTree;

 var i,i0:integer;

 begin

   for i:=n downto 1 do Heap(i,n);

end;

procedure HeapSort;

 var i:integer; buf:node;

 begin

    BuildSortTree;

    for i:=n downto 2 do

      begin buf:=a[1]; a[1]:=a[i]; a[i]:=buf; Heap(1,i-1) end

 end;

         Рис.3.7.