Rambler's Top100

Анализ сортировки Шелла

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

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

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

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

Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т.д. Обнаружение наименьшего среди n элементов требует - это очевидно - n-1 сравнения, среди n-1 нужно n-2 сравнений и т.д. Сумма первых n-1 целых равна 1/2(n2-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, изобретенном Д.Уилльямсом.  

Вверх

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

hi<=h2i и hi<=h2i+1 для i=L...R/2. 

                                                               h1  

                      h                                                                    h3  

         h4                        h5                                         h6                           h7  

 h8             h9         h10            h11                     h12                h13        h14             h15  

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

                                                               h1   

                     42                                                                    06   

         55                      94                                       18                          12  

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

                                                               06  

                         42                                                                        12  

           55                      94                                               18                           44  

Р.Флойдом был предложен способ построения пирамиды "на том же месте". Его процедура сдвига представлена в программе процедурой sift.  

Процесс формирования пирамиды из n элементов h1,...,hn на том же месте описывается так:  

Вверх

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.  

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz