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

Улучшенные методы внутренней сортировки

Сравнение прямых методов внутренней сортировки

Сортировка выбором

При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..., a[n],... a[j], a[j+1],..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение. Работа алгоритма иллюстрируется примером в таблице 1.5.

Таблица 1.5. Пример сортировки простым выбором

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	1 23 5 65 44 33 8 6
Шаг 2	1 5 23 65 44 33 8 6
Шаг 3	1 5 6 65 44 33 8 23
Шаг 4	1 5 6 8 44 33 65 23
Шаг 5	1 5 6 8 33 44 65 23
Шаг 6	1 5 6 8 23 44 65 33
Шаг 7	1 5 6 8 23 33 65 44
Шаг 8	1 5 6 8 23 33 44 65

Для метода сортировки простым выбором требуемое число сравнений - n(n-1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n²). Однако порядок среднего числа пересылок есть O(n*ln(n)), что в ряде случаев делает этот метод предпочтительным.

FOR i:=1 TO n-1 DO BEGIN

x:=a[i]; k:=i;

FOR j:=i+1 TO n DO

IF a[j]<x THEN BEGIN x:=a[j]; k:=j END;

a[k]:=a[i]; a[i]:=x;

END;

Для рассмотренных в начале этой части простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). Таблица 2.10 содержит данные, приводимые в книге Никласа Вирта.

Таблица 2.10. Характеристики простых методов сортировки

	Min	Avg	Max
Прямое включение	C = n-1 M = 2^x(n-1)	(n^2 + n - 2)/4(n^2 - 9n - 10)/4	(n^2 -n)/2 - 1(n^2 -3n - 4)/2
Прямой выбор	C = (n^2 - n)/2 M = 3^x(n-1)	(n^2 - n)/2n^x(ln n + 0.57)	(n^2 - n)/2n^2/4 + 3^x(n-1)
Прямой обмен	C = (n^2 - n)/2M = 0	(n^2 - n)/2(n^2 - n)^x0.75	(n^2 - n)/2(n^2 - n)^x1.5

Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием (В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения.). Мы не будем описывать алгоритм в общем виде, а ограничимся случаем, когда число элементов в сортируемом массиве является степенью числа 2. Для массива с 2ⁿ элементами алгоритм работает следующим образом. На первой фазе производится сортировка включением всех пар элементов массива, расстояние между которыми есть 2^(n-1). На второй фазе производится сортировка включением элементов полученного массива, расстояние между которыми есть 2^(n-2). И так далее, пока мы не дойдем до фазы с расстоянием между элементами, равным единице, и не выполним завершающую сортировку с включениями. Применение метода Шелла к массиву, используемому в наших примерах, показано в таблице 1.2.

Таблица 1.2. Пример сортировки методом Шелл

Начальное состояние массива	8 23 5 65 44 33 1 6
Фаза 1 (сортируются элементы, расстояние между которыми четыре)	8 23 5 65 44 33 1 68 23 5 65 44 33 1 68 23 1 65 44 33 5 68 23 1 6 44 33 5 65
Фаза 2 (сортируются элементы, расстояние между которыми два)	1 23 8 6 44 33 5 65 1 23 8 6 44 33 5 65 1 23 8 6 5 33 44 65 1 23 5 6 8 33 44 65 1 6 5 23 8 33 44 651 6 5 23 8 33 44 651 6 5 23 8 33 44 65
Фаза 3 (сортируются элементы, расстояние между которыми один)	1 6 5 23 8 33 44 651 5 6 23 8 33 44 651 5 6 23 8 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65

В общем случае алгоритм Шелла естественно переформулируется для заданной последовательности из t расстояний между элементами h1, h2,..., ht, для которых выполняются условия h_t = 1 и h_(i+1) < h_i. Дональд Кнут показал, что при правильно подобранных t и h сложность алгоритма Шелла является O(n^(1.2)), что существенно меньше сложности простых алгоритмов сортировки.

На первый взгляд можно засомневаться; если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок,

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Однако совсем не очевидно, что такой прием «уменьшающихся расстояний» может дать лучшие результаты, если расстояния не будут степенями двойки. Поэтому приводимая программа не ориентирована на некую определенную последовательность расстояний. Каждая h-сортировка программируется как сортировка с помощью прямого включения.

k:=n;

WHILE k>1 DO BEGIN

k:=k DIV 2;

FOR i:=k+1 TO n DO BEGIN

x:=a[i]; j:=i;

WHILE (x<a[j-k]) AND (j>i-k) DO BEGIN

a[j]:=a[j-k];

j:=j-k;

END;

a[j]:=x;

END;

END;

Анализ сортировки Шелла. Анализ этого алгоритма поставил несколько весьма трудных математических проблем, многие из которых так еще и не решены. В частности, не известно, какие расстояния дают наилучшие результаты. Но вот удивительный факт: они не должны быть множителями один другого. Это позволяет избежать явления уже очевидного из приведенного выше примера, когда при каждом проходе взаимодействуют две цепочки, которые до этого нигде еще не пересекались. И действительно, желательно, чтобы взаимодействие различных цепочек проходило как можно чаще. Справедлива такая теорема: если k-отсортированную последовательность i-отсортировать, то она остается k-отсортированной. Кнут показывает, что имеет смысл использовать такую последовательность (она записана в обратном порядке): 1, 4, 13, 40, 121,..., где h_k-1= 3h_k+1, h_t=1 и t=(log₃n)-1 (t- число расстояний). Он рекомендует и другую последовательность: 1, 3, 7, 15, 31,... где h_k-1= 2h_k+1, h_t=1 и t=(log₂n)-1. Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n^1.2. Хотя это число значительно лучше n², тем не менее мы не ориентируемся в дальнейшем на этот метод, поскольку существуют еще лучшие алгоритмы.

Дата добавления: 2014-01-13