Сортування Шелла

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування Шелла
Step-by-step visualisation of Shellsort
Демонстрація сортування Шелла з інтервалами 23, 10, 4, 1.
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія \Omega ( n log^2 n)
Оптимальний Переважно ні

Сортува́ння Ше́лла — це алгоритм сортування, що є узагальненням сортування включенням.

Алгоритм базується на двох тезах:

  • Сортування включенням ефективне для майже впорядкованих масивів.
  • Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз.

Тому сортування Шелла виконує декілька впорядкувань включенням, кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного.

Сортування Шелла не є стабільним.

Історія[ред.ред. код]

Сортування Шелла названо начесть автора — Дональда Шелла, який опублікував цей алгоритм у 1959[1] році. В деяких пізніших друкованих виданнях алгоритм називають сортуванням Шелла-Мацнера, за ім'ям Нортона Мацнера. Але сам Мацнер стверджував: «Мені не довелось нічого робити з цим алгоритмом, і моє ім'я не має пов'язуватись з ним».[2]

Ідея алгоритму[ред.ред. код]

На початку обираються m-елементів: d_1,d_2,\dots,d_m, причому, d_1 > d_2 > \dots > d_m = 1.

Потім виконується m впорядкувань методом включення, спочатку для елементів, що стоять через \;d_1, потім для елементів через \;d_2 і т. д. до \;d_m=1.

Ефективність досягається тим, що кожне наступне впорядкування вимагає меншої кількості перестановок, оскільки деякі елементи вже стали на свої місця.

Псевдокод[ред.ред. код]

Сам алгоритм не залежить від вибору m і d, тому будемо вважати, що вони задані.

Shell\_Sort(A,N)\;
1. for k\leftarrow 1 to \;m
2. do for i\leftarrow d[k]+1 to \;N
3.    do a\leftarrow A[i]
4.       j\leftarrow i
5.       while \;j-d[k] \ge 1 і \;A[j-d[k]]>a
6.       do A[j]\leftarrow A[j-d[k]]
7.          j\leftarrow j-d[k]
8.       A[j]\leftarrow a

Коректність алгоритма[ред.ред. код]

Оскільки \;d_m=1 то на останньому кроці виконується звичайне впорядкування включенням всього масиву, а отже кінцевий масив буде впорядкованим.

Час роботи[ред.ред. код]

Час роботи залежить від вибору значень елементів масиву d. Існує декілька підходів вибору цих значень:

  • При виборі d_1=\left\lfloor\frac{N}{2}\right\rfloor, d_2=\left\lfloor\frac{d_1}{2}\right\rfloor, d_3=\left\lfloor\frac{d_2}{2}\right\rfloor, \dots, d_m=1 час роботи алгоритму, в найгіршому випадку, є \;O(N^2).
  • Якщо d — впорядкованний за спаданням набір чисел виду \frac{3^j-1}{2}, j \in \mathbb N, d_i<N, то час роботи є \;O\left(N^\frac{3}{2}\right).
  • Якщо d — впорядкованний за спаданням набір чисел виду 2^i3^j, i,j \in \mathbb N, d_k<N, то час роботи є \;O(N\log^2N).

Приклад роботи[ред.ред. код]

Проілюструймо роботу алгоритму на вхідному масиві A = (5,16,1,32,44,3,16,7), d = (5,3,1).

  1. Масив після впорядкування з кроком в 5: (3,16,1,32,44,5,16,7) — зроблено 1 обмін.
  2. Масив після впорядкування з кроком 3: (3,7,1,16,16,5,32,44) — зроблено 3 обміна.
  3. Масив після впорядкування з кроком 1: (1,3,5,7,16,16,32,44) — зроблено 5 обмінів.

Отже, весь масив впорядковано за 9 операцій обміну.

Реалізація (Паскаль/DELPHI)[ред.ред. код]

PROGRAM MyVerShellSort;
{$APPTYPE CONSOLE}
USES SysUtils;
TYPE massive=array[1..100] of integer;
VAR A:massive; n:integer;
procedure RndArrInput(var a1:massive; n1:integer);
  var i1:integer;
  begin
    randomize;
    for i1:=1 to n1 do
      a1[i1]:=10-random(20);
  end;
procedure Arroutput(a2:massive; n2:integer);
  var i2:integer;
  begin
    for i2:=1 to n2 do
      write(a2[i2],' ');
  end;
procedure change (var k,l:integer);
  var tmp:integer;
  begin
    tmp:=k; k:=l; l:=tmp;
  end;
procedure  ShellSort(var  A:massive;  N:integer);
  var  i,j,h:integer;
  begin
    h:=N  div  2;
    while  h>0  do
      begin
        for  i:=1  to  N-h  do
          begin
            j:=i;
            while  (j>=1)and(A[j]>A[j+h])  do
              begin
                change(a[j],a[j+h]);
                dec(j);
              end;
          end;
        h:=h  div  2;
      end;
  end;
BEGIN
writeln('enter data:');
readln(n);
RndArrInput(a,n);
ArrOutPut(a,n); readln;
ShellSort(a,n);
ArrOutPut(a,n);
readln;
END.

Примітки[ред.ред. код]

  1. Shell D.L. A high-speed sorting procedure // Communications of the ACM, 2 (1959) (7) С. 30–32. — DOI:10.1145/368370.368387.
  2. «Shell sort». National Institute of Standards and Technology. Архів оригіналу за 2013-06-26. Процитовано 2007-07-17. 

Посилання[ред.ред. код]