Эффективность алгоритма УлШелл

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

Пример сравнения сортировок: Вновь возьмем последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):

5 3 4 3 6 2 1

Теперь применим к ней метод Шелла.

Здесь N = 7, поэтому:

t= trunc(log 7) = 2k= 2²-1 = 3 {начнем с 3-сортировки}p= 7 mod 3 = 1 {кол-во длинных подпоследовательностей}s= (7 div 3)+1 = 3 {длина длинной подпоследовательности}

1. 3-сортировки:

2. 5 3 1 -> 1 3 5 {3 сдвига: 7 пересылок, 5 сравнений}3. 3 6 -> 3 6 {0 сдвигов: 0 пересылок, 1 сравнение}4 2 -> 2 4 {1 сдвиг: 3 пересылки, 2 сравнения}

Всего 4 сдвига: 10 пересылок, 8 сравнений Итог 3-сортировок: 1 3 2 3 6 4 5

4. 1-сортировка:

5. Состояние массива Сдвиги Сравнения Пересылки данных6. 7. 0 шаг: 1323645 8. 1 шаг: 1323645 0 1 09. 2 шаг: 1323645 1 1+1 1+210.3 шаг: 1233645 0 1 011.4 шаг: 1233645 0 1 012.5 шаг: 1233645 1 1+1 1+213.6 шаг: 1233465 1 1+1 1+2результат: 1233456 3 9 9

При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% - на сравнениях)¹⁰. Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.

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

Пирамидальная сортировка

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.

Просеивание

Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах¹¹ последовательно задерживаются сначала крупные, а затем все более мелкие частицы.

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

a[1]
a[2]	a[3]
a[4]	a[5]	a[6]	a[7]
a[8]	a[9]	a[10]	a[11]	a[12]

Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1]. И в каждой такой тройке максимальный элемент должен находится "сверху". Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.

Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i].

При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды:

for i:= (N div 2)downto 1 do begin j:= i; while j<=(N div 2) do begin k:= 2*j; if (k+1<=N) and (a[k]<a[k+1]) then k:= k+1; if a[k]>a[j] then begin x:= a[j]; a[j]:= a[k]; a[k]:= x; j:= k end else break endend;

Пример результата просеивания

Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).

Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):

После первых трех просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):

	10 9
		9 10

 

11 4
4 11

Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов - для каждого из них будет достаточно только одного шага:

	12 5
			5 12
11 7
7 11

А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:

12 1
	1 12
7 1
	8 1
		1 8

 

		6 1
				1 6

Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".

Алгоритм УлПир

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

· поменять местами очередной "рабочий" элемент с первым;

· просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

Реализация алгоритма УлПир

Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте "Просеивание", поэтому здесь ограничимся только реализацией основного шага 1:

for i:= N downto 2 do begin x:= a[1]; a[1]:= a[i]; a[i]:= x; j:= 1; while j<=((i-1)div 2) do begin k:= 2*j; if (k+1<=i-1) and (a[k]<a[k+1]) then k:= k+1; if a[k]>a[j] then begin x:= a[j]; a[j]:= a[k]; a[k]:= x; j:= k end else break endend;

Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12,11,8,7,10,6,5,4,2,9,3,1]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт - элементы, исключенные из дальнейшей обработки:

1) Меняем местами a[1] и a[12]: [1,11,8,7,10,6,5,4,2,9,3,12];2) Просеиваем элемент a[1], получаем: [11,10,8,7,9,6,5,4,2,1,3,12];3) Меняем местами a[1] и a[11]: [3,10,8,7,9,6,5,4,2,1,11,12];4) Просеиваем a[1], получаем: [10,9,8,7,3,6,5,4,2,1,11,12];5) Меняем местами a[1] и a[10]: [1,9,8,7,3,6,5,4,2,10,11,12];6) Просеиваем элемент a[1]: [9,7,8,4,3,6,5,1,2,10,11,12];7) Меняем местами a[1] и a[9]: [2,7,8,4,3,6,5,1,9,10,11,12];8) Просеиваем элемент a[1]: [8,7,6,4,3,2,5,1,9,10,11,12];9) Меняем местами a[1] и a[8]: [1,7,6,4,3,2,5,8,9,10,11,12];10) Просеиваем элемент a[1]: [7,4,6,1,3,2,5,8,9,10,11,12];11) Меняем местами a[1] и a[7]: [5,4,6,1,3,2,7,8,9,10,11,12];12) Просеиваем элемент a[1]: [6,4,5,1,3,2,7,8,9,10,11,12];13) Меняем местами a[1] и a[6]: [2,4,5,1,3,6,7,8,9,10,11,12];14) Просеиваем элемент a[1]: [5,4,2,1,3,6,7,8,9,10,11,12];15) Меняем местами a[1] и a[5]: [3,4,2,1,5,6,7,8,9,10,11,12];16) Просеиваем элемент a[1]: [4,3,2,1,5,6,7,8,9,10,11,12];17) Меняем местами a[1] и a[4]: [1,3,2,4,5,6,7,8,9,10,11,12];18) Просеиваем элемент a[1]: [3,1,2,4,5,6,7,8,9,10,11,12];19) Меняем местами a[1] и a[3]: [2,1,3,4,5,6,7,8,9,10,11,12];20) Просеивать уже ничего не нужно;21) Меняем местами a[1] и a[2]: [1,2,3,4,5,6,7,8,9,10,11,12];22) Просеивать ничего не нужно, сортировка закончена.

Эффективность алгоритма УлПир

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.

В среднем этот алгоритм имеет сложность, пропорциональную N*log N.

Быстрая сортировка

Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка¹². Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).

 

Типовые алгоритмы обработки одномерных массивов. Сортировка методом "Пузырька"

Сортировку данным методом рассмотрим на примере. Дан массив (табл.), элементы которого необходимо отсортировать в порядке возрастания:

Рис. 4.1. Сортировка 'Пузырьком'