Структуры и алгоритмы обработки данных



         

Сортировка Шелла (сортировка с уменьшающимся шагом)


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

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

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

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает; также очевидно, что расстояния в группах можно уменьшать по разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.

Приводимый алгоритм основан на методе прямой вставки без барьера и не ориентирована на некую определенную последовательность расстояний, хотя в нем для конкретности заданы шаги 5, 3 и 1.

При использовании метода барьера  каждая из сортировок нуждается в постановке своего собственного барьера, и программу для определения его местонахождения необходимо делать насколько возможно простой. Поэтому приходится расширять массив до [-h1..N].

h[1..t] - массив размеров  шагов

a[1..n] - сортируемый массив

k - шаг сортировки

x - значение вставляемого элемента

Subroutine  ShellSort

 

Псевдокод:

const t = 3

          h(1) = 5

          h(2) = 3

          h(3) = 1

  for m = 1 to t

    k = h(m)

    for i = k + 1 to n

      x = a(i)

      for j = i - k to 1 step -k

        if  x < a(j) then

          a( j+k) = a(j)

        else

           goto L

         endif

       next j

  L:  a(j+k) = x

      next i

     next m

    return

Паскаль:

const   t = 3;

            h(1) = 5;

            h(2) = 3;

            h(3) = 1;

var

  h: array [1..t] of integer;

  a: array [1..n] of integer;

   k, x, m, t, i, j: integer;

 begin

   for  m = 1 to t do

     begin

       k:= h(m);

       for i = k + 1 to n do

         begin

          x:= a(i);           

          for j = i-k  downto k   do

             begin

              if  x < a(j ) then

                a(j+k):= a(j);

               else

                 goto 1;

              end ;

             end;

            end;

1:          a(j+1) = x ;

         end;   

    end .

<


Содержание  Назад  Вперед