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

Сортировка Шелла была названа в честь ее изобретателя – Дональда Шелла, который опубликовал этот алгоритм в 1959 году. Общая идея сортировки Шелла состоит в сравнении на начальных стадиях сортировки пар значений, расположенных достаточно далеко друг от друга в упорядочиваемом наборе данных. Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов).

Общая схема метода состоит в следующем.

Шаг 1. Происходит упорядочивание элементов пар для .

Шаг 2. Упорядочиваются элементы в группах из четырех элементов для .

Шаг 3. Упорядочиваются элементы уже в группах из восьми элементов и т.д.

На последнем шаге упорядочиваются элементы сразу во всем массиве . На каждом шаге для упорядочивания элементов в группах используется метод сортировки вставками (рис. 2).

В настоящее время неизвестна последовательность , оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что , а . Начинается процесс с , что . Иногда значение h вычисляют проще: . Это упрощенное вычисление h и будем использовать далее.

Рис.2. Демонстрация сортировки по неубыванию методом Шелла

//Описание функции сортировки Шелла

void Shell_Sort (int n, int *x){

int h, i, j;

for (h = n/2 ; h > 0 ; h = h/2)

for (i = 0 ; i < n-h ; i++)

for (j = i ; j >= 0 ; j = j - h)

if (x[j] > x[j+h])

Exchange (j, j+h, x);

else j = 0;

}

//процедура обмена двух элементов

void Exchange (int i, int j, int *x){

int tmp;

tmp = x[i];

x[i] = x[j];

x[j] = tmp;

}

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту.

Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется , для худшего случая оценкой является .