14. Сортировка включением. Метод Шелла. Временная сложность алгоритмов.

 

Сортировка включением состоит в следующем: выбирается некоторый элемент, сортируются другие элементы, после чего выбранный элемент “включается”, т.е. устанавливается на свое место среди других элементов. Рассмотрим подробнее соответствующий алгоритм.

                        ...

                        for i:=2 to n do

                         begin

                                   buf:=a[i]; y:=a[i].key; j:=i-1;

                                   while (j>0) and (a[j].key>y) do begin a[j+]:=a[j]; j:=j-1 end

                                   a[j+1]:=buf;

                         end

                        ...

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

Таблица 3.1.

 

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

 

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

j

1

2

3

4

 

j

1

2

3

4

a[j].key

33

22

44

11

 

a[j].key

22

33

44

11

i=2 (элемент с кл. 22 встал на свое место относительно элемента с кл. 33)

 

i=4 (элемент с кл. 11 встал на свое место относительно элементов с кл. 22, 33, 44)

j

1

2

3

4

 

j

1

2

3

4

a[j].key

22

33

44

11

 

a[j].key

11

22

33

44

 

            У этого алгоритма есть одно важное достоинство: в противоположность другим методам он имеет наилучшую эффективность, если в начальном массиве уже установлен некоторый порядок.

            Пример. Если элемент с ключом 44 уже стоял на своем месте относительно элементов с ключами 22 и 33 (см. табл. 3.1), то на третьем шаге его не понадобилось передвигать.

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

            Пример. Чтобы поставить элемент с ключом 11 на свое место (см. табл. 3.1), на четвертом шаге пришлось передвинуть элементы с ключами 22, 33, 44.

 

            Усовершенствованная сортировка включением известна как сортировка Шелла. В 1959 году Д.Л.Шелл предложил вместо систематического включения элемента с индексом i в подмассив предшествующих ему элементов (этот способ противоречит принципу “балансировки”, почему и не позволяет получить эффективный алгоритм) включать этот элемент в подсписок, содержащий элементы с индексами i-h, i-2h, i-3h и т.д., где h - некоторая натуральная постоянная. Таким образом формируется массив, в котором h-серии элементов, отстоящих друг от друга на расстояние h, сортируются отдельно:

            После того, как отсортированы непересекающиеся h-серии, процесс возобновляется с новым значением h’<h. Предварительная сортировка серий с расстоянием h значительно ускоряет сортировку серий с расстоянием h’.

            Для достаточно больших массивов результаты тестов показывают, что рекомендуемой можно считать последовательность таких hi, что hi+1=3 hi +1: ..., 364, 121, 40, 13, 4, 1. Начать процесс следует с такого элемента этой последовательности, который является ближайшим к целой части числа (n/9),  превосходящим это число.

            Пример. Если сортируется последовательность из n=1000 элементов, то целая часть числа (n/9) составит 111, значит h следует выбрать равным 121.

            Доказано,что максимальная сложность алгоритма Шелла составляет O(n5/4). Так как

то этот вид сортировки пригоден для последовательностей, имеющих примерно до 70 тыс. элементов.

            На рис. 3.3 представлена процедура, реализующая метод Шелла.

 

Procedure ShellSort;

 var h,j,k,y,kh:integer; buf:node;

 begin

   h:=1; while h<(n div 9) do h:=3*h+1;

   while h>0 do

    begin

      for k:=1 to h do

       begin

         kh:=k+h;

         while (kh<=n) do

          begin

            buf:=a[kh]; y:=buf.key; j:=kh-h;

            while (j>=1) and (y<a[j].key) do begin a[j+h]:=a[j]; j:=j-h end;

            a[j+h]:=buf; kh:=kh+h;

          end

       end;

      h:=h div 3;

    end

  end;   {* Shell*}                                         

 

                        Рис. 3.3