В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения.
Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на 4 позиции. Такой процесс называется четвертной сортировкой.
После первого прохода элементы перегруппировываются — теперь каждый элемент группы отстоит от другого на 2 позиции — и вновь сортируются (двойная сортировка).
На третьем проходе идет обычная сортировка.
Кажется, что необходимость нескольких проходов сортировки, в каждом из которых участвуют все элементы, потребует большего количества машинных ресурсов, чем обычная сортировка. Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок.
Такой метод в результате дает упорядоченный массив, и каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой).
Расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным. В самом плохом случае последний проход сделает всю работу.
Реализация сортировки Шелла на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
// Функция сортировки Шелла
void shellSort(int *num, int size)
{
int increment = 3; // начальное приращение сортировки
while (increment > 0) // пока существует приращение
{
for (int i = 0; i < size; i++) // для всех элементов массива
{
int j = i; // сохраняем индекс и элемент
int temp = num[i];
// просматриваем остальные элементы массива, отстоящие от j-ого
// на величину приращения
while ((j >= increment) && (num[j - increment] > temp))
{ // пока отстоящий элемент больше текущего
num[j] = num[j - increment]; // перемещаем его на текущую позицию
j = j - increment; // переходим к следующему отстоящему элементу
}
num[j] = temp; // на выявленное место помещаем сохранённый элемент
}
if (increment > 1) // делим приращение на 2
increment = increment / 2;
else if (increment == 1) // последний проход завершён,
break; // выходим из цикла
}
}
int main()
{
int m[10];
// Вводим элементы массива
for (int i = 0; i<10; i++)
{
printf("m[%d]=", i);
scanf("%d", &m[i]);
}
shellSort(m, 10); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i<10; i++)
printf("%.2d ", m[i]);
getchar(); getchar();
return 0;
}
Результат выполнения
Анализ алгоритма
Приводимая программа не ориентирована на некую определенную последовательность расстояний. Все t расстояний обозначаются соответственно
h1, h2, ..., ht ,
для них выполняются условия
ht=1;
hi+1<hi.
Каждая h-сортировка программируется как сортировка с помощью прямого включения.
В алгоритме не известно, какие расстояния дают наилучшие результаты.
Дональд Кнут рекомендует такую последовательность:
1, 3, 7, 15, 31, ...,
то есть
hk-1=2hk+1,
ht=1 и t = [log2n] - 1.
Назад: Алгоритмы сортировки и поиска
2
3
4
5
6
increment = increment/2;
else if (increment == 1) // increment = 1
increment = 0;
else // increment = 2
increment = 1;