Возьмем массив [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
end
end;
Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [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) Просеивать ничего не нужно, сортировка закончена.
Динамические структуры данных. Стек, его применение. Операции над элементами стека.
Называются так потому, что их элементы создаются и уничтожаются во время работы программы.
Stack – динамическая структура данных, у которой в каждый момент доступен верхний последний элемент.
Операции, необходимые для Стека.
Empty (<нач_ст>):Boolean;
Add(<нач_ст>,<нов_элемен>):<нач_ст>;
Take(<нач_ст>):тип_элем;
Del (<нач_ст>):нач_ст;
LIFO (последний зашел первый вышел)
FILO(первым зашел первый вышел)
стеки часто применяются в системном программном обеспечении, включая компиляторы и интерпретаторы.
Динамические структуры данных. Очередь, ее применение. Операции над элементами очереди.
Queue – динамическая структура данный, у которой в любой момент времени доступны два элемента: 1й и последний, НО! В конец очереди можно только добавлять элементы, а из начала только забирать.
Процедуры для реализации очереди
Empty (<нач_оч>):Boolean;
Add(<кон_оч>,<нов_элемен>):<кон_чо>;
Take(<нач_оч>):тип_элем;
Del (<нач_оч>):нач_оч;
В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.
