Программирование на языке Pascal



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


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

86
1
75
4912
112103

10 99 10
1
75
11812
11236

11 44 11
1
75
10812
2936

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

12 55 12
1
7
11108
42936

11 77 11
1
5
10812
42936

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

12 11 12
11
7 11085
42936

8 11 8
12
11
7105
42936

6 11 6
12
118
7105
4293

Итак, мы превратили исходный массив в пирамиду: в любой тройке 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]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт - элементы, исключенные из дальнейшей обработки:




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