и далее серым цветом выделяем

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

86

1
7				5
4		9		12
11	2	10	3

10 99 10

1
7				5
11		8	12
11	2	3	6

11 44 11

1
7				5
10		8	12
2	9	3	6

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

12 55 12

1
7
11		10		8
4	2	9	3	6

11 77 11

1
5
10		8	12
4	2	9	3	6

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

12 11 12

11
7 1		10		8	5
4	2	9	3	6

8 11 8

12
11
7		10		5
4	2	9	3	6

6 11 6

12
11				8
7		10		5
4	2	9	3

Итак, мы превратили исходный массив в пирамиду: в любой тройке 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 end end;

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

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий