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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

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

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

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

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

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

На початку обираються m-елементів: , причому, .

Потім виконується m впорядкувань методом включення, спочатку для елементів, що стоять через , потім для елементів через і т. д. до .

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

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

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

1. for  to 
2. do for  to 
3.    do 
4.       
5.       while  і 
6.       do 
7.          
8.       

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

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

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

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

• При виборі час роботи алгоритму, в найгіршому випадку, є .
• Якщо d — впорядкованний за спаданням набір чисел виду , то час роботи є .
• Якщо d — впорядкованний за спаданням набір чисел виду , то час роботи є .

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

Проілюструймо роботу алгоритму на вхідному масиві 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 обмінів.

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

[ред.] Реалізація (Паскаль/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
 a[i1]:=10-random(20);
end;
procedure Arroutput(a2:massive; n2:integer);
var i2:integer;
begin
 for i2:=1 to n2 do
 write(a[i2],' ');
end;
Procedure change (var k,l:integer);
 var tmp:integer;
 begin
  tmp:=k; k:=l; l:=tmp;
 end;
procedure ShellSort(var A3:massive; n3:integer);
var i,h,cur:integer;
begin
  h:=n div 2;
  while h>0 do
  begin
    cur:=0;
   while cur+h+1<=n do
    begin
     if a3[cur+1]>a3[cur+h+1] then
     change(a3[cur+1],a3[cur+h+1]);
     inc(cur);
    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. (1959). «A high-speed sorting procedure». Communications of the ACM 2 (7): 30–32. DOI:10.1145/368370.368387.
2. ↑ Shell sort. National Institute of Standards and Technology. Процитовано 2007-07-17.