Сортування Шелла
![]() Демонстрація сортування Шелла з інтервалами 23, 10, 4, 1. | |
Клас | Алгоритм сортування |
---|---|
Структура даних | масив |
Найгірша швидкодія | |
Оптимальний | Переважно ні |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Shell_sorting_algorithm_color_bars.svg/220px-Shell_sorting_algorithm_color_bars.svg.png)
Сортува́ння Ше́лла — це алгоритм сортування, що є узагальненням сортування включенням.
Алгоритм базується на двох тезах:
- Сортування включенням ефективне для майже впорядкованих масивів.
- Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз.
Тому сортування Шелла виконує декілька впорядкувань включенням, кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного.
Сортування Шелла не є стабільним.
Сортування Шелла названо на честь автора — Дональда Шелла, який опублікував цей алгоритм у 1959[1] році. В деяких пізніших друкованих виданнях алгоритм називають сортуванням Шелла-Мацнера, за ім'ям Нортона Мацнера. Але сам Мацнер стверджував: «Мені не довелось нічого робити з цим алгоритмом, і моє ім'я не має пов'язуватись з ним».[2]
На початку обираються m-елементів: , причому, .
Потім виконується m впорядкувань методом включення, спочатку для елементів, що стоять через , потім для елементів через і т. д. до .
Ефективність досягається тим, що кожне наступне впорядкування вимагає меншої кількості перестановок, оскільки деякі елементи вже стали на свої місця.
Сам алгоритм не залежить від вибору m і d, тому будемо вважати, що вони задані.
1. for to 2. do for to 3. do 4. 5. while and 6. do 7. 8.
Оскільки то на останньому кроці виконується звичайне впорядкування включенням всього масиву, а отже кінцевий масив буде впорядкованим.
Час роботи залежить від вибору значень елементів масиву d. Існує декілька підходів вибору цих значень:
- При виборі час роботи алгоритму, в найгіршому випадку, є .
- Якщо d — впорядкований за спаданням набір чисел виду , то час роботи є .
- Якщо d — впорядкований за спаданням набір чисел виду , то час роботи є .
- Якщо d — впорядкований за спаданням набір чисел одного з видів:
- (з додатковим членом 1 на початку)
- або ,
то час роботи алгоритму становить (Sedgewick, 1986[3]).
- Існують інші, оптимальніші послідовності, для яких не визначена верхня асимптотична оцінка, наприклад:
Проілюструймо роботу алгоритму на вхідному масиві A = (5,16,1,32,44,3,16,7), d = (5,3,1).
- Масив після впорядкування з кроком в 5: (3,16,1,32,44,5,16,7) — зроблено 1 обмін.
- Масив після впорядкування з кроком 3: (3,7,1,16,16,5,32,44) — зроблено 3 обміни.
- Масив після впорядкування з кроком 1: (1,3,5,7,16,16,32,44) — зроблено 5 обмінів.
Отже, весь масив впорядковано за 9 операцій обміну.
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.
void sort_shell(int *a, int N)
{
for (int d = N/2; d >= 1; d /= 2)
for (int i = d; i < N; i++)
for (int j = i; j >= d && a[j-d] > a[j]; j -= d)
swap(a[j], a[j-d]);
}
- ↑ Shell, D.L. (1959). A high-speed sorting procedure. Communications of the ACM. 2 (7): 30—32. doi:10.1145/368370.368387.
- ↑ Shell sort. National Institute of Standards and Technology. Архів оригіналу за 26 червня 2013. Процитовано 17 липня 2007.
- ↑ Sedgewick, Robert (1986). A New Upper Bound for Shellsort. Journal of Algorithms. 7 (2): 159—173. doi:10.1016/0196-6774(86)90001-5.
- ↑ Ciura, Marcin (2001). Best Increments for the Average Case of Shellsort (PDF). У Freiwalds, Rusins (ред.). Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag. с. 106—117. ISBN 3-540-42487-3. Архів оригіналу (PDF) за 30 серпня 2011. Процитовано 23 вересня 2018.
- ↑ Tokuda, Naoyuki (1992). An Improved Shellsort. У van Leeuven, Jan (ред.). Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co. с. 449—457. ISBN 0-444-89747-X.
![]() |
Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |
|