Сортировка выбором

Турнирная сортировка

Идея выбора может привести к эффективному алгоритму сортировки. Весь вопрос в том, чтобы найти более эффективный метод определения i-го наибольшего имени, чего можно добиться, используя механизм турнира с выбыванием. Суть его такова: сравниваются x₁:x₂,x₃:x₄,…,x_n-1:x_n,затем сравниваются "победители” (т.е., большие имена) этих сравнений и т.д. Эта процедура для n=8 показана на рисунке:

44     55   12     42   94     18   06     67

Заметим, что для определения наибольшего имени этот процесс требует n-1 сравнений ; но определив наибольшее имя, мы обладаем большим объемом информации о втором по величине (в порядке убывания) имени: оно должно быть одним из тех, которые "потерпели поражение” от наибольшего имени. Таким образом второе по величине имя теперь можно определить, заменяя наибольшее имя на -¥ и вновь осуществляя сравнение вдоль пути от наибольшего имени к корню.

Реализация

procedure turnir_sort;

   Const MAX_VALUE=-32767;

   Type

    index1 = 1 .. 2*n-1;

    item1 = record

            key: integer;    { ключ сортировки }

            adres: index;    { описание других компонент }

    end;

   var i,j,j1:index1;

      B:array [index1] of item1;

  begin

   for i:=n to 2*n-1 do

     begin

     B[i].key:=A[i-n+1].key;

     B[i].adres:=i;

     end;

     i:=2*n-1;j:=1;

   repeat {первый круг}

     if B[i].key>B[i-1].key then j:=i else j:=i-1;

     B[j div 2].key:=B[j].key;

     B[j div 2].adres:=B[j].adres;

     i:=i-2;

   until(i<3);

     A[1].key:=B[1].key;

     j1:=2;

   repeat  {последующие круги}

        if ((B[1].adres mod 2)=0) then i:=B[1].adres+1

           else i:=B[1].adres;

        B[B[1].adres].key:=MAX_VALUE;

        repeat

          if B[i].key>B[i-1].key then j:=i else j:=i-1;

          B[j div 2].key:=B[j].key;

          B[j div 2].adres:=B[j].adres;

          i:=i div 2;

          if ((i mod 2)=0) then i:=i+1;

        until(i<3);

       A[j1].key:=B[1].key;

       j1:=j1+1;

     until(j1>n);

    end;

Пирамидальная сортировка

Идея турнира с выбыванием прослеживается при сортировке весьма отчетливо, если имена образуют пирамиду. Пирамида-это полностью сбалансированное бинарное дерево высоты h, в котором все листья находятся на расстоянии h или h-1 от корня и все потомки узла меньше его самого; кроме того, в нем все листья уровня h максимально смещены влево.(см. рис.)

42

Чтобы получить удобное линейное представление дерева, пирамиду можно хранить по уровням в одномерном массиве: сыновья имени из i-й позиции есть имена в позициях 2i и 2i+1. Таким образом, пирамида, представленная на рисунке, принимает вид:

i:   1    2    3    4    5    6    7    8

Заметим, что в пирамиде наибольшее имя должно находиться в корне и, таким образом, всегда в первой позиции массива, представляющего пирамиду. Обмен местами первого имени с n-м помещает наибольшее имя в его правильную позицию, но нарушает свойство пирамидальности в первых n-1 именах. Если мы можем сначала построить пирамиду, а затем восстанавливать ее эффективно, то всё в порядке, так как тогда можно производить сортировку следующим образом:

Построить пирамиду из x_1,…,x_n,

For i:=n downto 2 do        Восстановить пирамиду

                            в x₁,…,x_i-1

Это общее описание пирамидальной сортировки.

Как преобразовать в пирамиду данное бинарное дерево, все листья которого максимально сдвинуты влево и оба поддерева которого являются пирамидами? Сравниваем корень с большим из сыновей. Если корень больше, дерево уже является пирамидой; в противном случае мы меняем его местами с большим сыном и применяем рекурсивно алгоритм восстановления к поддереву, корень которого заменялся. Таким образом, процедура RESTORE(j,k)восстановления пирамиды из последовательности xj,xj+1,…,xk в предположении, что все поддеревья суть пирамиды, такова:

procedure RESTORE(j,k)

if x_j ¹ лист then

                   if x_m>x_j then 

                                  RESTORE(m,k)

Переписывая это итеративным способом и дополняя деталями, мы получаем следующий алгоритм.

Реализация

procedure RESTORE(var f,l:index);

 var j,m:index; x:item;

begin

   j:=f;

   while(j<=(l div 2)) do

    begin

     if (2*j<l) and (A[2*j].key<A[2*j+1].key) then m:=2*j+1 else m:=2*j;

     if (A[m].key>A[j].key) then

       begin

         x:=A[m]; A[m]:=A[j]; A[j]:=x;

         j:=m;

       end

      else j:=l;

    end;

end;

Для построения пирамиды вначале заметим, что свойство пирамидальности уже выполняется (тривиально) для каждого листа (x_i, i=ë0.5nû+1,…,n) и что обращение к RESTORE(i,n)для i=ë0.5nû, ë0.5nû-1,…,1 преобразует таблицу в пирамиду на всех высших уровнях. Таким образом, пирамидальная сортировка производится так, как показано в алгоритме. Первый цикл for строит пирамиду и известен как фаза построения; второй цикл for носит название фазы выбора.

Реализация

procedure piramid_sort;

 var i,nn,o,o1:index; x:item;

 begin

    nn:=n; o:=1;

    for i:=(nn div 2) downto 1 do  RESTORE(i,nn);

    for i:=nn downto 2 do

     begin

       x:=A[1];

       A[1]:=A[i];

       A[i]:=x;

       o1:=i-1;

       RESTORE(o,o1);

     end;

 end;

Сортировка обменом

Сортировка разделением

Рассмотрим еще один метод сортировки обменом. Он обладает столь блестящими характеристиками, что его изобретатель К.Хоор окрестил его быстрой сортировкой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Предположим, что нам даны n элементов с ключами, расположенными в обратном порядке. Их можно рассортировать, выполнив всего n/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так постепенно продвигаться от двух концов к середине. Разумеется, это возможно, но только если мы твердо знаем, что элементы расположены строго в обратном порядке.

Попробуем рассмотреть следующий алгоритм: выберем случайным образом какой-то элемент (назовем его х), просмотрим массив, двигаясь справа налево, пока не найдем элемента A[i] > х,  а затем просмотрим его справа налево, пока не обнаружим A[i]<х. Теперь поменяем местами эти два элемента и продолжим процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую – с ключами меньшими, чем х и правую - с ключами большими. Теперь запишем этот алгоритм разделения в виде процедуры в программе (см. ниже). Заметим что отношения > и < заменены на «больше или равно» и «меньше или равно», отрицания которых в операторе цикла с предусловием - это < и >. При такой замене х действует как барьер для обоих просмотров.

Реализация

     procedure partition;

     var w,x: item;

     begin i:=1; j:=n;

        "выбор случайного элемента х;"

        repeat

          while (A[i].key < x.key) do i:=i+1;

          while (x.key < A[j].key) do j:=j-1;

          if (i<=j) then

             begin w:=A[i]; A[i]:=A[j]; A[j]:=w;

                i:=i+1; j:=j-1;

            end;

         until (i>j);

     end;

Если, например, в качестве х выбрать средний ключ, равный 42, из массива ключей 44 55 12 |42| 94 06 18 67 то, для того, чтобы разделить массив, потребуется два обмена

   18 06 12 |42| 94 55 44 67

конечные значения индексов i=5 и j=3. Ключи A[1],...,A[i-1] меньше или равны ключу х=42, ключи A[j+1],...,A[n] больше или равны х. Следовательно, мы получили два подмассива:

A[k].key <= x.key  для k=1, ..., i-1,

A[k].key >= x.key  для k=j+1, ..., n

и, следовательно

A[k].key = x.key  для k=j+1, ..., i-1

Этот алгоритм очень прост и эффективен. Но он так же может быть весьма неуклюжим, как видно из примера с n одинаковыми ключами, в котором выполняется n/2 обменов. Эти ненужные обмены можно легко устранить, заменив, операторы просмотра на

while (A[i].key < x.key) do i:=i+1;

while (x.key < A[j].key) do j:=j-1;

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

Теперь нам пора вспомнить, что наша цель не только разделить исходный массив элементов на большие и меньшие, но так же рассортировать его. Однако от разделения до сортировки один небольшой шаг: разделив массив, нужно сделать то же самое с обеими полученными частями, затем с частями этих частей и т.д., пока каждая часть будет содержать только один элемент. Этот метод представлен программой ниже.