В этой теме продолжаем изучать методы сортировок массивов, которые получены усовершенствованием простых методов.   Улучшенные методы сортировки Сортировка с помощью включений с уменьшающимися расстояниями.

В 1959 г. Д.Шеллом было предложено усовершенствование сортировки с помощью прямого включения.  

Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. После первого прохода элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на две позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.  

Например: Дан массив, состоящий из элементов:  

44  55  12  42  94  18  06  67

После четверной сортировки получаем:  

44  18  06  42  94  55 12  67

Т.е. элементы, отстоящие на 4 позиции друг от друга сравниваются и меняются местами в случае необходимости (44<94, 55>18 значит меняем местами, 12>06 тоже меняем местами, 42<67).  
После двойной сортировки получаем:  

06  18  12  42  44  55  94  67

  Теперь сравниваем элементы, отстоящие на 2 позиции (44>06 - меняем, 94>12 - меняем, 44>12 - меняем и т.д.)  
После одинарной сортировки получаем:  

06  12  18  42  44  55  67  94

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

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояния обозначаются соответственно h₁,h₂,...,h_t, для них выполняются условия  

h_t=1, h_i+1<h_i

Каждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров. Ясно, что каждая из сортировок нуждается в постановке своего собственного барьера и программу для определения его местоположения необходимо делать насколько возможно простой. Поэтому приходится расширять массив не только на одну-единственную компоненту a₀, а на h₁ компонент.   Анализ сортировки Шелла

Анализ этого алгоритма поставил несколько проблем. Не известно, какие расстояния дают наилучшие результаты. Д.Кнут в работе "Искусство программирования для ЭВМ" показывает, что имеет смысл использовать такую последовательность ( записана в обратном порядке):  

1, 4, 13, 40, 121, ...  или  1, 3, 7, 15, 31, ...

Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n^1.2.   Сортировка с помощью дерева.

Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т.д. Обнаружение наименьшего среди n элементов требует - это очевидно - n-1 сравнения, среди n-1 нужно n-2 сравнений и т.д. Сумма первых n-1 целых равна 1/2(n²-n). Как же в таком случае можно усовершенствовать упомянутый метод сортировки? Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С помощью n/4 сравнений - меньший из пары уже выбранных меньших и т.д. Проделав n-1 сравнений, мы можем построить дерево выбора и идентифицировать его корень как нужный нам наименьший ключ.  
Рассмотрим тот же массив:  44  55  12  42  94  18  06  67. Из двух соседних будем выбирать наименьший.  

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

Повторяющиеся выборы среди двух ключей.  

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

                      12                                                                     ?  
  

         44                      12                                    18                              ?  

44            55        12           42                    94             18            ?                 67

Выбор наименьшего ключа.  
 
 
  

                                                           12  
 
  

                      12                                                                   18  
  

         44                      12                                    18                              67  

44            55        12           42                    94             18               ?             67  

Заполнение дырок.  

Элемент, передвинувшийся в корень дерева, вновь будет наименьшим (теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (т.е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внимание - на каждом из n шагов выбора требуется только n·logn элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение. Естественно, сохранение дополнительной информации делает задачу более изощренной, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Наша следующая задача - найти приемы эффективной организации этой информации. Это удалось добиться в методе Heapsort, изобретенном Д.Уилльямсом.  

Пирамида определяется как последовательность ключей h_L, h_L+1,...,h_R, такая, что  
hi<=h_2i и hi<=h_2i+1 для i=L...R/2.  
                                                               h₁  

                      h₂                                                                     h₃  

         h₄                        h₅                                         h₆                           h₇  

 h₈             h₉         h₁₀            h₁₁                     h₁₂                h₁₃        h₁₄             h₁₅  

Предположим, есть некоторая пирамида с заданными элементами h_L+1,...,h_R для некоторых значений L и R и нужно добавить новый элемент x, образуя расширенную пирамиду h_L,...,h_R. Возьмем, например, в качестве исходной пирамиду h₁,...,h₇  
                                                               h₁  
  

                     42                                                                    06  
  

         55                      94                                       18                          12  

и добавим к ней слева элемент h₁=44. Новая пирамида получается так: сначала x ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значение 44 сначала меняется местами с 06, затем с 12 и в результате образуется дерево  

                                                               06  
 
                       42                                                                        12  

   
       55                      94                                               18                           44  

Р.Флойдом был предложен способ построения пирамиды "на том же месте". Его процедура сдвига представлена в программе процедурой sift.  
Процесс формирования пирамиды из n элементов h₁,...,h_n на том же месте описывается так:  

L:=(n div 2) +1;  
while L>1 DO begin L:=L-1; sift(L,n); end;  

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

type mass=array[1..100] of integer;  
var   k,i,j,x: integer;  
        a: mass;  
  procedure sift ( var a: mass; l,r: integer);  
    begin  
      i:=l;j:=2*l;x:=a[l];  
          if (j<r) and (a[j]<a[j+1]) then j:=j+1;  
          while (j<=r) and (x<a[j]) do  
              begin  
                  x:=a[i]; a[i]:=a[j]; a[j]:=x;  
                  i:=j; j:=2*j;  
                  if (j<r) and (a[j]<a[j+1]) then j:=j+1;  
              end;  
     end;  
  procedure Heapsort (var a: mass; n: integer);  
      var  l,r: integer;  
          begin  
               l:=(n div 2)+1; r:=n;  
               while l>1 do  
                    begin  
                        l:=l-1;  
                        sift(a,l,r);  
                    end;  
               while r>1 do  
                    begin  
                         x:=a[1]; a[1]:=a[r]; a[r]:=x; r:=r-1;  
                         sift(a,l,r);  
                    end;  
          end;  
  Begin  randomize;  
     readln(k);  
     for i:=1 to k do  
          begin  
               a[i]:=random(100);write(a[i],'  ');  
          end; writeln;  
      heapsort(a,k);  
      writeln;  
      for i:=1 to k do  
      write(a[i],'  ');  
      writeln;  
  End.  

Анализ Heapsort.  

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

В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log₂(n/2), log₂(n/2-1),...,log₂(n-1) позиций (логарифм "обрубается" до следующего меньшего целого). Следовательно, фаза сортировки требует   n-1 сдвигов с самое большое log₂(n-1), log₂(n-2),...,1 перемещениями. Кроме того, нужно еще n-1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев Heapsort потребует n*log₂n шагов.  
 

Сортировка с помошью разделения.  

Теперь коснемся третьего улучшенного метода, основанного на обмене. Улучшение метода, основанного на обмене, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Изобретатель Ч.Хоар назвал этот метод быстрой сортировкой (Quicksort).  

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

Давайте, попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент a_i>x, затем будем просматривать массив справа, пока не встретим a_j<x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую с ключами больше (или равными) x. Если взять в качестве x для сравнения средний ключ 42, то в массиве ключей  

44  55  12  42  94  06  18  67  

для разделения понадобятся два обмена: 18≈44 и 6≈55. Получаем  

     18  06  12  42  94  55  44  67  

последние значения индексов таковы: i=5, а j=3. Ключи a₁...a_i-1 меньше или равны ключу x=42, а ключи a_j+1...a_n больше или равны x. Следовательно, существует две части, а именно  
Ak:1<= k < i:a_k <= x  
Ak: j< k <= n:x <= a_k  

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

Суть итеративного решения заключается во введении списка требуемых разделений, т.е. разделений, которые необходимо провести. На каждом этапе возникают две задачи по разделению. И только к одной из них мы можем непосредственно сразу приступить в очередной итерации, другая же заносится в упомянутый список. При этом, конечно, существенно, что требования из списка выполняются несколько специфическим образом, а именно в обратном порядке. Следовательно, первое из перечисленных требований выполняется последним, и наоборот. В приводимой не рекурсивной версии Quicksort каждое требование задается просто левым и правым индексами - это границы части, требующей дальнейшего разделения. Вводим индекс s, указывающий на самую последнюю строку в стеке. О том, как выбрать подходящий размер стека m, речь пойдет при анализе Quicksort.  

const m=4; n=20;  
type stack=record  
     t,r:integer;  
     end;  
type mass=array[1..n] of integer;  
var i,j,t,r,x,w:integer;  
    s: 0..m;  
    a: mass;  
    st: array[1..m] of stack;  

Begin  
   for i:=1 to n do  
     begin  
       a[i]:=random(100); write(a[i],'  ');  
     end;  
   s:=1; st[s].t:=1; st[s].r:=n;  
   repeat  {выбор из стека последнего запроса}  
     t:=st[s].t;r:=st[s].r;s:=s-1;  
       repeat  {разделение a[t]...a[r]}  
         i:=t;j:=r;x:=a[(l+r) div 2];  
         repeat  
           while a[i]<x do i:=i+1;  
           while x<a[j] 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;  
         if i<r then   {запись в стек запроса из правой части}  
                begin s:=s+1; st[s].t:=i;st[s].r:=r; end;  
         r:=j;  {теперь t и r ограничивают левую часть}  
       until t>=r;  
   until s=0;  

   writeln;  
   for i:=1 to n do  
     write(a[i],'  ');  
End.  

  Анализ Quicksort.      
Для исследования производительности Quicksort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. Следовательно, при этом выполняется точно n сравнений. Число же обменов можно определить из следующих вероятностных соображений. При заданной границе значений x ожидаемое число операций обмена равно числу элементов в левой части разделяемой последовательности, т.е. n-1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, если этот элемент перед этим находился в правой части. Вероятность этого равна (n-(x-1))/n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.  

m = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n  
    = [Su: 1<= x <= n-1:u*(n-u)]/n²  
    = [n*(n-1)/2n-(2n²-3n+1)/6n = (n-1/n)/6  

Представим себе, что нам всегда удается выбрать в качестве границы медиану, в этом случае каждый процесс разделения расщепляет массив на две половины и для сортировки требуется всего log₂n  проходов. В результате общее число сравнений равно n*log₂n, а общее число обменов - n*log₂(n)/6. Средняя производительность Quicksort при случайном выборе границы отличается от упомянутого оптимального варианта лишь коэффициентом 2*ln(2). Как бы то ни было, но Quicksort присущи и некоторые недостатки. Главный из них - недостаточно высокая производительность при небольших n.  

Литература  

1.  Н.Вирт. Алгоритмы и структуры данных.  
2.  Д.Кнут. Искусство программирования для ЭВМ.  

Упражнения  

1.  Дан массив целых чисел a[1..n]. Отсортировать его методом Шелла.  
2.  Найти количество различных чисел среди элементов данного массива. Число действий порядка nlogn. (В решение использовать изученные сортировки).  
3.  Найти перестановку элементов 1, 2,  3, ..., n, при которой быстрая сортировка ведет себя наихудшим (наилучшим) образом (n=5, 6, 7).