33.1. Метод Шелла
 

Метод Шелла является улучшением метода сортировки с помощью прямого включения и основан на сортировке посредством включений с уменьшающимися расстояниями. Сначала отдельно группируются и сортируются методом прямых включений элементы, отстоящие друг от друга на некотором расстоянии h₁, затем на расстоянии h₂ < h₁ и т.д., последнее расстояние должно быть равно 1. Таким образом, если для сортировки будет использовано t расстояний, то h_t=1, h_i+1i. Желательно, чтобы расстояния обеспечивали бы взаимодействие различных цепочек как можно чаще.

Учитывая этот факт имеет смысл использовать такие последовательности (записаны в обратном порядке): 1, 4, 13, 40, 121, ...,т.е. h_k-1 = 3h_k+ 1,h_t=1, t = [Iog₃n]- 1 или 1,3,7, 15,31, ..., т.е. h_k-1 = 2h_k + 1,h_t= 1, t = [Iog₂n] - 1. В последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n^1,2, что значительно лучше n² , но хуже n*log₂n. Часто используют h₁ = n/2, h₂ = n/4, ..., и т.д.

На каждом шаге методом включения сортируются группы a₁, а_1+h, a_1+2h,…,a_1+kh, 1+kh≤n; a₂,a_2+h,… . Так как начальный шаг является наибольшим, то число элементов массива в начальной группе является наименьшим, например, если h = n/2, то группируются только два элемента. При втором проходе шаг уменьшается, а число элементов в группе увеличивается, и при h = 1 группа включает всю последовательность целиком.

Рассмотрим процесс сортировки последовательности из 8 целых чисел при h₁ = 4: 5, 6, 2, 4, 8, 3, 1, 7.

При h₁ = 4 сортируются четыре группы по два элемента в каждой: 5, 8; 6, 3; 2, 1; 4, 7. В результате перестановок 6—3 и 2—1 получаем частично упорядоченную последовательность 5, 3, 1, 4, 8, 6, 2, 7. При h₂= 2 сортируются две группы по четыре элемента: 5, 1, 8, 2 и 3, 4, 6, 7. В первой группе после перестановки 5—1 получим 1, 5, 8, 2, затем включение 2 в упорядоченную часть приведет к сдвигам 8 и 5: 1, 2, 5, 8. Поскольку вторая группа упорядочена, то последовательность примет вид: 1, 3, 2, 4, 5, 6, 8, 7. Сортировка с шагом h₃ = 1 приводит к окончательному результату: 1, 2, 3, 4, 5, 6, 7, 8.

Рассмотрим пример.
Пример.

/* СОРТИРОВКА МЕТОДОМ ШЕЛЛА */
#include
#define n 15
int A[n]={12,3,14,15,6,1,7,8,9,5,11,2,13,4,10};
int main()
{ void Shell(int A[],int nn);
int j;
printf("\n Исходный массив: \n");
printf("\t");
for (j=0; j<n;j++)
printf("%d”,A[j]);
printf("\n Отладочная печать по шагам сортировки");
Shell(A,n);
printf("\n Отсортированный массив :\n");
for (j=0; j<n;j++)
printf("%d”,A[j]);
printf("\n");
getch(); return 0;
}
/* ФУНКЦИЯ СОРТИРОВКИ МЕТОДОМ ШЕЛЛА*/
void Shell(int A[],int nn)
{ int i,j,k,x;
k=(nn+1)/2;
while (k 𕟳)
{
for (i=k; i<nn; i++)
{ if (A[i-k] > А[i])
{ x=A[i]; j=i-k;
M: A[j+k]=A[j];
if (j>k)
       { if (A[j-k] > x)
{j=j-k;
goto M;
}
}
А[j]=х;
}
}
/* Отладочная печать */
printf(" \nk=%d ",k);
for (i=0; i<nn;i++)
printf(" %d",A[i]);
if (k>2)
k=(k+1)/2;
else
k=k/2;
}
}
Исходный массив:
12   3   14   15   6    1   7   8    9   5   11  2   13   4   10.
Отладочная печать по шагам сортировки:
k = 8   9  3   11   2  6  1  7  8   12  5  14  15  13  4  10
k = 4    6  1  7  2  9  3  10  8  12  4  11  15  13  5   14
k = 2   6  1  7   2  9  3  10  4  11  5   12  8   13  15  14
k = 1   1  2  3   4  5  6  7   8   9  10  11  12  13  14  15
Отсортированный массив:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15.