Ідея методу полягає в порівняння розділених на групи елементів послідовності, що знаходяться один від одного на деякій відстані. Спочатку ця відстань дорівнює d або N / 2, де N - загальне число елементів. На першому кроці кожна група включає в себе два елементи розташованих один від одного на відстані N / 2; вони порівнюються між собою, і, в разі необхідності, міняються місцями. На наступних кроках також відбуваються перевірка і обмін, але відстань d скорочується на d / 2, і кількість груп, відповідно, зменшується. Поступово відстань між елементами зменшується, і на d = 1 прохід по масиву відбувається в останній раз.
Далі, на прикладі послідовності цілих чисел, показаний процес сортування масиву методом Шелла. Для зручності і наочності, елементи однієї групи виділені однаковим кольором.
Перше значення, відповідне відстані d дорівнює 10/2 = 5. На кожному кроці воно зменшується вдвічі. Елементи, що входять в одну групу, порівнюються і якщо значення будь-якого елемента, що стоїть лівіше того з яким він порівнюється, виявляється більше (сортування по зростанню), тоді вони міняються місцями. Так, елементи шляхом внутрішньогрупових перестановок поступово стають на свої позиції, і на останньому кроці (d = 1) сортування зводиться до проходу по одній групі, що включає в себе всі N елементів масиву. При цьому число необхідних обмінів виявляється зовсім невеликим.
Код програми на C ++:
Код програми на Pascal:
program ShellSorting;
uses crt;
type massiv = array # 91; 1. 100 # 93; of integer;
var i. j. n. d. count. integer;
A. massiv;
procedure Shell # 40; A. massiv; n. integer # 41; ;
begin
d: = n;
d: = d div 2;
while # 40; d> 0 # 41; do
begin
for i: = 1 to n - d do
begin
j: = i;
while # 40; # 40; j> 0 # 41; and # 40; A # 91; j # 93;> A # 91; j + d # 93; # 41; # 41; do
begin
count: = A # 91; j # 93; ;
A # 91; j # 93; : = A # 91; j + d # 93; ;
A # 91; j + d # 93; : = Count;
j: = j - 1;
end;
end;
d: = d div 2;
end;
writeln;
for i: = 1 to n do write # 40; ''. A # 91; i # 93; # 41; ;
end;
begin
write # 40; 'Розмір масиву>' # 41; ; read # 40; n # 41; ;
for i: = 1 to n do
begin write # 40; i. 'Елемент>' # 41; ; readln # 40; A # 91; i # 93; # 41; ; end;
write # 40; 'Результуючий масив:' # 41; ;
Shell # 40; A. n # 41; ;
end.
Сортування Шелла поступається в ефективності швидкого сортування, але виграє у сортування вставками. Порівняти швидкість роботи цих трьох алгоритмів можна, скориставшись наступною таблицею.