Быстрая сортировка Хоара (Hoare C.A.R.) (алгоритм quicksort) Индекс А 12345678910 Значение ключа 23512457322821812 Индекс А 12345678910 Значение ключа. - презентация

1 Быстрая сортировка Хоара (Hoare C.A.R.) (алгоритм quicksort) Индекс А Значение ключа Индекс А Значение ключа л п Индекс А Значение ключа л п

2 Индекс А Значение ключа л п Индекс А Значение ключа пл

3 function findpivot ( i,j : integer) : integer; var firstkey : тип_ключа; k: integer; begin firstkey:= A[i].key; for k:= i+1 to j do if A[k].key > firstkey then begin findpivot:=k; exit end else if A[k].key < firstkey then begin findpivot:=i; exit end; findpivot:=0; end; function partition ( i,j : integer; pivot : тип_ключа ) : integer; var l, r : integer; begin l:=i; r:=j; repeat swap (A[l], A[k] ); {Написать самостоятельно процедуру обмена двух записей таблицы} while A[l].key < pivot do l:=l+1; {Проход слева} while A[r].key >= pivot do r:=r-1; {Проход справа} until l > r; partition:=l end;

4 procedure qicksort ( i,j : integer) ; {Сортировка элементов массива A[i], …, A[j] } var pivot : тип_ключа; pivotindex : integer; k : integer; begin pivotindex := findpivot (i,j); if pivotindex <> 0 then beginpivot := A[pivotindex].key; k:= portition (i,j, pivot); quicksort( i, k-1); {рекурсивно применяем функцию к левому множеству элементов} quicksort( k, j); { рекурсивно применяем функцию к левому множеству элементов } end end;

5 Двоичные (бинарные) деревья (binary trees) Иван Зоя Вера Олег Нина Петр ветви вершины Петр корень листья В общем случае дерево определяется так: это совокупность вершин, связанных ветвями, причем из каждой вершины может выходить любое количество ветвей, но входить в каждую вершину должна только одна ветвь, за исключением одной вершины, называемой корнем, в которую не входит ни одна ветвь; при этом из корня должны быть доступны все остальные вершины дерева.

6 Представление двоичного дерева Петр Нина Олег nil Зоя nil nil Вера nil nil Иван nil Петр nil T type ТЭД =string[20]; {тип элементов дерева (любой)} адрес = вершина; вершина = record элем: ТЭД; влево, вправо: адрес end; дерево = адрес; var T: дерево;

7 a7 a6a5a4 a3a2 a1 Ива н Зоя Вера Олег Нин а Пет р p в a6a5 a3a2 a1 Олег Нин а Пет р p б a4 a3 a1 Пет р p а a2 Пример Требуется описать на Паскале процедуру Печ Лист(Т), которая выводит на экран имена из всех листьев непустого двоичного дерева Т – при просмотре этих листьев слева направо.

8 procedure Печ Лист(T: дерево); var S: стек; {любое представление, ТЭС=адрес} p: адрес; begin Нач УстСтека(S); p:=T; {по условию задачи p nil} repeat if p.влево<>nil then {есть путь влево} begin if p.вправо<>nil then ВСтек(p.вправо,S); p:=p.влево end else {нет пути влево} if p.вправо<>nil then p:=p.вправо {есть путь вправо} else {p - лист} begin write(p.элем); if Пустой Стек(S) then p:=nil else Из Стека(S,p) until p=nil end;

9 Рекурсивный вариант просмотра двоичного дерева корень дерево procedure Печ Лист(T: дерево); begin if (T.влево=nil) and (T.вправо=nil) then write(T.элем) else {корень – не лист} begin if T.влево<>nil then Печ Лист(T.влево); if T.вправо<>nil then Печ Лист(T.вправо) end end;

10 Самостоятельно разобрать Пример. Требуется описать на Паскале процедуру По Уровням(Т), которая выводит на экран имена из всех вершин непустого двоичного дерева Т, так сказать, по уровням: сначала выводит имя из корня дерева, затем имена (слева направо) из всех вершин 2-го уровня, затем имена (также слева направо) из всех вершин 3-го уровня и т.д. Для нашего конкретного дерева должно быть выдано: Петр Нина Олег Вера Иван Петр Зоя Подсказка: для нерекурсивного варианта использовать как вспомогательную структуру данных - очередь

11 procedure По Уровням(T: дерево); var Q: очередь; {любое представление, ТЭО=адрес} p: адрес; begin Нач УстОчереди(Q); Вочередь(T,Q); {корень -> очередь} repeat Из Очереди(Q,p); write(p.элем); if p.влево<>nil then ВОчередь(p.влево,Q); if p.вправо<>nil then ВОчередь(p.вправо,Q) until Пустая Очередь(Q) end; В качестве самостоятельной работы: написать рекурсивный вариант этой процедуры