Вы здесь

Сортировка Шелла

Исходный код на C++: 

Теория

Сортировка Шелла является модифицированным вариантом сортировки вставками. При использовании сортировки Шелла массив делиться на n частей. Первая часть массива содержит элементы 0,n,2n,3n и т.д., вторая часть 1,n+1,2n+1,3n+1 и т.д. Каждая часть последовательности сортируются независимо при помощи сортировки вставками с шагом n. Далее уменьшаем шаг в 2 раза (n=n/2) и повторим алгоритм. Повторяя итерационный процесс, пока шаг не станет равным 1. На выходе мы получим отсортированный массив. Приведём пример. Дан входной массив чисел: 15,-9,1,34,61,-79,22,-33. Значение n=4(количество элементов в массиве делённое пополам, но можно выбрать произвольное значение, часто используют значения кратные двойки 32,16,8….). Первый шаг работы алгоритма
j=0, i=4 (15 и 61). Оставляем без изменений. Массив равен 15,-9,1,34,61,-79,22,-33.
j=1, i=5 (-9 и -79). Изменяем порядок следования элементов. Массив равен 15,-79,1,34,61,-9,22,-33.
j=2, i=6 (1 и 22). Оставляем без изменений. Массив равен 15,-79,1,34,61,-9,22,-33.
j=3,i=7 (34 и -33). Изменяем порядок следования элементов. Массив равен 15,-79,1,-33,61,-9,22,34. В итоге получаем после первого шага (рис. 1).

После первого шага работы алгоритма
Рис.1 шаг 1.

После первого шага работы алгоритма уменьшим шаг в 2 раза (n=2) и повторим процесс (рис 2).

После второго шага работы алгоритма
Рис.2 шаг 2.

Продолжая итерационный процесс, мы получаем отсортированный массив.

Программная реализация

void sort_shella(int count,double *mass)
{
int i,j,p,m,k;
double min;
for(m=count/2;m;m=m/2)//постоянно уменьшаем шаг от count/2 до 1(разбиваем массив на группы)
{
for(k=0;k<m;k++)//двигаемся внутри группы
for(i=m+k;i<count;i+=m)//сортировка вставками с учётом шага
{
min=mass[i];
for(j=k;j<i;j+=m)
if(mass[j]>min) break;
for(p=i-m;p>=j;p-=m)
mass[p+m]=mass[p];
mass[j]=min;
}
}
}