Вопрос 24.1. Как реализуется сортировка Шелла и какова временная сложность этого метода сортировки

Этот метод назван по имени его изобретателя (D.L. Shell). Он построен на основе метода вставки с минимизацией промежуточных шагов. Сначала выполняется сортировка элементов, отстоящих друг от друга на три позиции. После этого сортируются элементы, отстоящие друг от друга на две позиции. Наконец выполняется сортировка смежных элементов.

Точная последовательность изменения приращений может изменяться. Единственным требованием остается равенство последнего приращения 1. Например, хорошо себя зарекомендовала последовательность 9, 5, 3, 2, 1, которая использована в нижеприведенном примере реализации алгоритма Шелла. Избегайте последовательностей степеней 2, поскольку математически строго доказано, что это снижает эффективность алгоритма (который, тем не менее, работает и в этом случае).

Время выполнения алгоритма пропорционально n^1,2 при сортировке n элементов. Это - существенный прогресс по сравнению с n-квадратичными методами сортировки. Однако метод быстрой сортировки еще более эффективен, чем метод Шелла.

void shell_sort(int *array, int n)

{

int i, j, k, gap, temp;

int a[] = {9, 5, 3, 2, 1};

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

gap = a[k];

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

temp = array[i];

for (j = i-gap; temp < array[j] && j >= 0; j-=gap)

array[j+gap] = array[j];

array[j+gap] = temp;

}

}

}

Внутренний цикл for имеет два условия проверки. Очевидно, что сравнение temp < array[j] необходимо по условиям процесса сортировки. Условие j >= 0 предотвращает выход за пределы массива array . Эти дополнительные проверки в некоторой степени снизят производительность алгоритма Шелла. Улучшенные сии алгоритма используют специальные элементы массива, называемые стражами. Стражи не являются частью сортируемого массива. Они содержат завершающие элементы, обозначающие наибольший и наименьший возможные элементы массива. Это делает ненужной проверку границ массива, но требует конкретной информации о данных, что ограничивает общность функции сортировки.