Энциклопедия Turbo Pascal. Главы 1-4 - Сортировка Шелла

Сортировка Шелла

Сортировка Шелла получила свое название по имени ее создателя Д.Л.Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга.  ("Ракушка" - одно из значений слова
shell - Примеч. пер.)

Общий метод,  который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами.  На рис.2 показана схема выполнения сортировки Шелла для массива "оасве".  Сначала сортируются все элементы,  которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.

проход 1   f   d   a   c   b   e

проход 2   c   b   a   f   d   e

проход 3   a   b   c   e   d   f

полученный результат   a   b   c   d   e   .

Сортировка Шелла:

       { сортировка Шелла }
       procedure Shell(var item: DataArray; count:integer);
       const
         t = 5;
       var
         i, j, k, s, m: integer;
         h: array[1..t] of integer;
         x: DataItem;
       begin
         h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
         for m := 1 to t do
           begin

         k:=h[m];
         s:=-k;
         for i := k+1 to count do
         begin
           x := item[i];
           j := i-k;
           if s=0 then
           begin
             s := -k;
             s := s+1;
             item[s] := x;
           end;
           while (x<item[j]) and (j<count) do
             begin
               item[j+k] := item[j];
               j := j-k;
             end;
             item[j+k] := x;
           end;
         end;
     end; { конец сортировки Шелла }

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

Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9,  5, 3, 2, 1, которая использована в показанном выше примере.  Следует избегать последовательностей степени двойки,  которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки.  /Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно/.

Внутренний цикл имеет   два   условия   проверки.   Условие "х<item[j]" необходимо для упорядочения элементов.  Условия "j>0" и "j<=count" необходимы для того,  чтобы предотвратить выход за пределы массива "item".  Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла.  Слегка измененные версии сортировки Шелла используют специальные управляющие элементы,  которые не являются в действительности частью той информации, которая должна сортироваться.  Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения.  Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки.

Анализ сортировки Шелла требует решения некоторых сложных математических задач,  которые выходят за рамки этой книги. Время выполнения сортировки Шелла пропорционально n**1.2.  Эта зависимость значительно лучше квадратичной зависимости,  которой подчиняются рассмотренные ранее алгоритмы сортировки.  Однако,  прежде чем вы решите использовать сортировку Шелла,  следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.