Алгоритм на псевдокоде
Пирамидальная сортировка
L:=ën/2û
DO (L>0)
<Построение (L,n) пирамиды>
L:=L-1
OD
R:=n
DO (R>1)
a1↔aR
R:=R-1
<Построение (1,R) пирамиды >
OD
Общее количество операций сравнений и пересылок для пирамидальной сортировки: C ≤ 2n log n+n+2, M ≤ n log n+6.5n-4. Таким образом, С=O(n log n), М=O(n log n) при n → ∞.
Отметим некоторые свойства пирамидальной сортировки. Метод пирамидальной сортировки неустойчив и не зависит от исходной отсортированности массива.
4.2 Метод Хоара
Метод Хоара или метод быстрой сортировки заключается в следующем. Возьмём произвольный элемент массива х. Просматривая массив слева, найдём элемент ai ≥x. Просматривая массив справа, найдём aj ≤x. Поменяем местами ai и aJ . Будем продолжать процесс просмотра и обмена, до тех пор пока i не станет больше j. Тогда массив можно разбить на две части: в левой части все элементы не больше х, в правой части массива не меньше х. Затем к каждой части массива применяется тот же алгоритм.
Пример:Отсортировать слово методом быстрой сортировки.
Условные обозначения: X ведущий элемент
X сравнение с ведущим элементом при просмотре справа
сравнение с ведущим элементом при просмотре слева
| разделение массива на части обмен элементов
К | У | Р | А | П | О | В | А | Е |
Е | У | Р | А | П | О | В | А | К |
Е | А | Р | А | П | О | В | У | К |
Е | А | В | А | П | О | Р | У | К |
Е | А | В | А | П | О | Р | У | К |
А | А | В | Е | К | О | Р | У | П |
А | А | В | К | О | Р | У | П | |
А | А | В | П | У | Р | |||
А | В | У | Р | |||||
Р | У | |||||||
А | А | В | Е | К | О | П | Р | У |
Рисунок 9 Метод Хоара
Дата добавления: 2022-02-05; просмотров: 255;