Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы,поясняющий данный алгоритм.

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

§ отсутствие потребности в памяти под стек;

§ отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Принцип действия:

Сортировка Шелла также является модификацией сортировки вставками. Метод данной сортировки основан на группировке элементов массива на несколько групп, например, на 8 групп по 2 записи. При этом элементы каждой группы отстоят друг от друга «расстоянии» h. Элементы каждой группы упорядочиваются методом простой вставки. Далее элементы массива снова группируются: на 4 группы по 4 элемента. Далее группировка выполняется на 8 групп по 2 элемента, и процесс завершается сортировкой всех элементов массива. При такой группировке упорядоченность элементов осуществляется большими скачками, что значительно сокращает количество перестановок.

Выигрыш по сравнению с методом простых вставок составляет примерно 50%

Для больших N (скажем, N = 10000) преимущество метода Шелла станет ещё заметнее.

Алгоритм Шелла имеет сложность ~N^3/2. И хотя это несколько хуже, чем N*logN, все-таки эта сортировка относится к улучшенным.

Пример:

Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .

На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

Фрагмент программы:

/* Пример из книги Герберта Шилдта */

void shell(char*items,int count)

{

registerint i, j, gap, k;

char x, a[5];

a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

for(k=0; k <5; k++){

gap= a[k];

for(i=gap; i < count;++i){

x = items[i];

for(j=i-gap;(x < items[j])&&(j >=0); j=j-gap)

items[j+gap]= items[j];

items[j+gap]= x;

}

}

}