Сортировка Шелла (Shell Sort)

Подробности: Категория: Сортировка и поиск

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

Худшее время	O(n²)
Лучшее время	O(n log² n)
Среднее время	зависит от выбранных шагов
Затраты памяти	О(n) всего, O(1) дополнительно

Пример

Пусть дан список $A = (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68)$ и выполняется его сортировка методом Шелла, а в качестве значений $d$ выбраны $5, 3, 1$ .

На первом шаге сортируются подсписки $A$ , составленные из всех элементов $A$ , различающихся на 5 позиций, то есть подсписки $A_{5,1} = (32, 66, 40)$ , $A_{5, 2} = (95, 35, 43)$ , $A_{5, 3} = (16, 19, 93)$ , $A_{5, 4} = (82, 75, 68)$ , $A_{5, 5} = (24, 54)$ .

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

Реализация алгоритма на различных языках программирования:

Псевдокод

ЗАДАЧА Шелл(a=: РЯД ИЗ ЦЕЛ);
ПЕР
  b,i,j,k,h: ЦЕЛ;
УКАЗ
  b:=РАЗМЕР(a);
  k:=b ДЕЛИТЬ 2;
  ПОКА k>0 ВЫП
    ОТ i:=1 ДО b-k ВЫП
      j:=i;
      ПОКА (j>=1) И (a[j]>a[j+k]) ВЫП
        h:=a[j];
        a[j]:=a[j+k];
        a[j+k]:=h;
        УМЕНЬШИТЬ(j);
      КОН;
    КОН;
    k:=k ДЕЛИТЬ 2
  КОН
КОН Шелл;

Cи

/* Пример из книги Герберта Шилдта */
void shell(char *items, int count)
{
  register int i, j, gap, k;
  char x, a[5];
 
  a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
 
  for(k=0; k < 5; k++) {
    gap = a[k];
    for(i=gap; i < count; ++i) {
      x = items[i];
      for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)
        items[j+gap] = items[j];
      items[j+gap] = x;
    }
  }
}

C++

int increment(long inc[], long size) {
// inc[] массив, в который заносятся инкременты
// size размерность этого массива
 int p1, p2, p3, s;
 
  p1 = p2 = p3 = 1;
  s = -1;
  do {// заполняем массив элементов по формуле Роберта Седжвика
    if (++s % 2) {
      inc[s] = 8*p1 - 6*p2 + 1;
    } else {
      inc[s] = 9*p1 - 9*p3 + 1;
      p2 *= 2;
      p3 *= 2;
    }
	p1 *= 2;
// заполняем массив, пока текущая инкремента хотя бы в 3 раза меньше количества элементов в массиве
  } while(3*inc[s] < size);
 
  return s > 0 ? --s : 0;// возвращаем количество элементов в массиве
}
 
template<class T>
void shellSort(T a[], long size) {
// inc инкремент, расстояние между элементами сравнения
// i и j стандартные переменные цикла
// seq[40] массив, в котором хранятся инкременты
  long inc, i, j, seq[40];
  int s;//количество элементов в массиве seq[40]
 
  // вычисление последовательности приращений
  s = increment(seq, size);
  while (s >= 0) {
	//извлекаем из массива очередную инкременту
	inc = seq[s--];
// сортировка вставками с инкрементами inc
    for (i = inc; i < size; i++) {
      T temp = a[i];
// сдвигаем элементы до тех пор, пока не дойдем до конца или не упорядочим в нужном порядке
      for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)
        a[j+inc] = a[j];
// после всех сдвигов ставим на место j+inc элемент, который находился на i месте
      a[j+inc] = temp;
    }
  }
}

VBA

Sub Sort(Mus() As Long)
  Dim i As Long, k As Long, Pos As Long
  Dim l As Long, r As Long, n As Long, tmp As Long
 
  l = LBound(Mus)
  r = UBound(Mus)
  n = r - l + 1
  k = 1
  Do
    k = k * 3 + 1
  Loop Until k > n
 
  Do
    k = k \ 3
    For i = (k + l) To r
       Pos = i
       tmp = Mus(i)
       Do While Mus(Pos - k) > tmp
         Mus(Pos) = Mus(Pos - k)
         Pos = Pos - k
         If (Pos - k) < l Then Exit Do
       Loop
       Mus(Pos) = tmp
    Next
  Loop Until k = 1
End Sub

C#

void shellSort(int[] arr)
        {
            int j;
            int step = arr.Length / 2;
            while (step > 0)
            {
                for (int i = 0; i < (arr.Length - step); i++)
                {
                    j = i;
                    while ((j >= 0) && (arr[j] > arr[j + step]))
                    {
                        int tmp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = tmp;
                        j-=step;
                    }
                }
                step = step / 2;
            }
        }

Этот более быстрый

private void shellSort(int[] vector)
        {
            int step = vector.Length / 2;
            while (step > 0)
            {
                int i, j;
                for (i = step; i < vector.Length; i++)
                {
                    int value = vector[i];
                    for (j = i - step; (j >= 0) && (vector[j] > value); j -= step)
                        vector[j + step] = vector[j];
                    vector[j + step] = value;
                }
                step /= 2;
            }
        }

Java

void sort_shell(int[] a){
   int i, j, k, h, m=0, b=a.length;
   int[] d = { 1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11969, 27901,
               84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
               58548857, 157840433, 410151271, 1131376761, 2147483647 };
   while (d[m] < b) ++m;
   while (--m >= 0){
      k = d[m];
      for (i = k; i < b; i++){     // k-сортировка
         j=i;
         h=a[i];
         while ((j >= k) && (a[j-k] > h)){
              a[j]=a[j-k];
              j -= k;
         }
         a[j] = h;
      }
   }
}

Object Pascal (Delphi)

var
  incr: array [0..23] of integer = (1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711,
  11969, 27901, 84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
  58548857, 157840433, 410151271, 1131376761, 2147483647);
 
type arInt = array of integer;
procedure ShellSort(var Arr: arInt);
  var
     C: Boolean;
     G: Integer;
     I: Integer;
     J: Integer;
     Tmp: Integer;
     len: Integer;
     cur_inc: integer;
begin
  len := Length(Arr) - 1;
  cur_inc := 0;
  while 3 * incr[cur_inc + 1] <= Length(Arr) do
    inc(cur_inc);
  repeat
    g := incr[cur_inc];
    i := g;
    repeat
      j := i - g;
      c := True;
      repeat
        if arr[j] >= arr[j + g] then
          c := False
        else
        begin
          Tmp := Arr[j];
          Arr[j] := Arr[j+g];
          Arr[j+g] := Tmp;
        end;
        dec(j, g);
      until  not ((j >= 0) and C);
      inc(i);
    until  not (i <= len);
    dec(cur_inc);
  until  not (cur_inc <> -1);
end;

PHP

function ShellSort($elements,$length) {
     $k=0;
     $gap[0] = (int) ($length / 2);
 
     while($gap[$k] > 1) {
         $k++;
         $gap[$k]= (int)($gap[$k-1] / 2);
     }//end while
 
     for($i = 0; $i <= $k; $i++){
         $step=$gap[$i];
 
         for($j = $step; $j < $length; $j++) {
             $temp = $elements[$j];
             $p = $j - $step;
             while($p >= 0 && $temp < $elements[$p]) {
                 $elements[$p + $step] = $elements[$p];
                 $p= $p - $step;
             }//end while
             $elements[$p + $step] = $temp;
         }//endfor j
     }//endfor i
 
     return $elements;
 }// end function
 
 // Exmaple
 // $SortedElements=shellsort($UnsortedElements,length of list(an integer));
 // e.g: $elements=shellsort($elements,10);

Python

def shell(seq):
    inc = len(seq) // 2
    while inc:
        for i, el in enumerate(seq):
            while i >= inc and seq[i - inc] > el:
                seq[i] = seq[i - inc]
                i -= inc
            seq[i] = el
        inc = 1 if inc == 2 else int(inc * 5.0 / 11)
 
data = [22, 7, 2, -5, 8, 4]
shell(data)
print data # [-5, 2, 4, 7, 8, 22]

Ruby

n = mass.size - 1
d = n/2
while d >= 1
n.downto(0) do |i|
 0.upto(i-d) do |j|
   mass[j], mass[j+d] = mass[j+d], mass[j] if mass[j] > mass[j+d]
 end
end
d /= 2
end
puts mass

Perl

@out=(5,3,7,9,2,1,6,5,3,7,9,3,4);
for(my$k=int($N/2);$k>0;$k=int($k/2)){
    for(0..$#out-$k){
	$j=$_;
	while($j>=0&&$out[$j]>$out[$j+$k]){
	    ($out[$j],$out[$j+$k])=($out[$j+$k],$out[$j]);
	    $j--;
	}
    }
}

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

отсутствие потребности в памяти под стек;
отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n?), что хуже, чем худшее гарантированное время для сортировки Шелла.

При написании статьи были использованы открытые источники сети интернет :

Wikipedia

Kvodo

Youtube