В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.
Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.
Далее, на примере последовательности целых чисел, показан процесс сортировки массива методом Шелла. Для удобства и наглядности, элементы одной группы выделены одинаковым цветом.
Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.
Код программы на C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include "stdafx.h" #include <iostream> using namespace std; int i, j, n, d, count; void Shell(int A[], int n) //сортировка Шелла { d=n; d=d/2; while (d>0) { for (i=0; i<n-d; i++) { j=i; while (j>=0 && A[j]>A[j+d]) { count=A[j]; A[j]=A[j+d]; A[j+d]=count; j--; } } d=d/2; } for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива } //главная функция void main() { setlocale(LC_ALL,"Rus"); cout<<"Размер массива > "; cin>>n; int *A= new int[n]; //объявление динамического массива for (i=0; i<n; i++) //ввод массива { cout<<i+1<<" элемент > "; cin>>A[i]; } cout<<"\nРезультирующий массив: "; Shell(A, n); delete [] A; //освобождение памяти system("pause>>void"); } |
Код программы на Pascal:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
program ShellSorting; uses crt; type massiv=array[1..100] of integer; var i, j, n, d, count: integer; A: massiv; procedure Shell(A: massiv; n: integer); {сортировка Шелла} begin d:=n; d:=d div 2; while (d>0) do begin for i:=1 to n-d do begin j:=i; while ((j>0) and (A[j]>A[j+d])) do begin count:=A[j]; A[j]:=A[j+d]; A[j+d]:=count; j:=j-1; end; end; d:=d div 2; end; writeln; for i:=1 to n do write(' ', A[i]); {вывод массива} end; {основной блок программы} begin write('Размер массива > '); read(n); for i:=1 to n do {ввод массива} begin write(i, ' элемент > '); readln(A[i]); end; write('Результирующий массив: '); Shell(A, n); end. |
|
Сортировка вставками |
Сортировка Шелла |
Быстрая сортировка |
|
|
Худший случай |
O(n2) |
O(n2) |
O(n2) |
|
Лучший случай |
O(n) |
O(n log n) |
O(n log n) |
|
Средний случай |
O(n2) |
Зависит от расстояния между элементами |
O(n log n) |
Похожие записи:
«count» не является однозначным.
В Вижуал студио 2017 выдаёт такую ошибку.
напиши вместо count другое название переменной в цикле и в начале, в инициализации переменной, например, на s. У меня заработало
переименуйте переменную)
нужно изменить имя переменной count