Метод за сортиране “Шел”

Шел сортирането е открито от Доналд Шел през 1959 година. То подобрява метода на мехурчето и сортирането чрез вмъкване чрез преместването на елементите през повече от една позиция в даден момент. Може да бъде описано като нареждане на последователни елементи в двумерен масив и след това сортирането на колоните на масива чрез сортиране чрез вмъкване

Реализация на метода:
void shellSort(double *a,int length){
int h = 0, i, j;
double x;
while(2*(3*h+1) < = length) h = 3*h+1;
while(h > 0){
for(i = h; i < length; i++){
x = a[i];
for(j = i-h; j > = 0; j = j-h)
if(x < a[j])
a[j+h] = a[j];
else
break;
a[j+h] = x;
}
h = h/3;
}
}

Първо, всички елементи, които са на разстояние седем позиции един от друг се
групират и сортират по отделно. Този процес се нарича сортиране със стъпка 7. В
пример с 10 елемента всяка група съдържа точно по два елемента. След това
елементите се прегрупират така, че във всяка група те да са през три позиции и се
сортират отново – сортиране със стъпка 3. Най-после при третото преминаване
елементите се сортират чрез обикновено сортиране или сортиране със стъпка 1.

Сортировката на Шел носи името на своя откривател – Donald Shell. Това е един от първите алгоритми, които преодолява квадратичното време за изпълнение. Той работи, сравнявайки елементи, които се намират на определено разстояние един от друг. Разстоянието между елементите намалява, като при последната фаза се сравняват близи помежду си елементи. Ето защо този алгоритъм понякога прилича на инкрементално намаляващо сортиране.

Сортировката на Шел използва редица от числа h₁, h₂, …, h_t, която се нарича редица на нарастването. Всички редици на нарастването започват с h₁ = 1, но няко са по-ефективни от други. На определена фаза от сортирането, при стойност на h = h­_k, за всяко i е изпълнено условието:

При сортировката на Шел за всяка позиция i при редица на нарастването h_k­­, h_k+1, …, N-1, елементът се поставя на правилната позиция в рамките на i, i-h_k, i-2h_k и т.н. Всъщност всяко h_k сортиране представлява сортиране чрез вмъкване на h_k независими подмасиви.

Предложената от Шел редица на нарастването не дава много добри резултати. Тя се изчислява по следния начин:

h_t=[N/2] h_k=[h_k+i/2]

Кодът по-долу реализира сортировката на Шел с предложената от негo редица на нарастването.

int j;

/*1*/ for ( int gap = N/2; gap > 0; gap /= 2 )

/*2*/ for ( int i = gap; i < N; i++)

{

/*3*/ tmp = a[i];

/*4*/ for (j = i; j >= gap && tmp < a{j-gap]; j-= gap)

/*5*/ a[j] = a[j-gap];

/*6*/ a[j] = temp;

}

https://www.youtube.com/watch?v=IlRyO9dXsYE