Алгоритм на псевдокоде

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

L:=ën/2û

DO (L>0)

<Построение (L,n) пирамиды>

L:=L-1

OD

R:=n

DO (R>1)

a₁↔a_R

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 Метод Хоара

Метод Хоара или метод быстрой сортировки заключается в следующем. Возьмём произвольный элемент массива х. Просматривая массив слева, найдём элемент a_i ≥x. Просматривая массив справа, найдём a_j ≤x. Поменяем местами a_i и a_J . Будем продолжать процесс просмотра и обмена, до тех пор пока i не станет больше j. Тогда массив можно разбить на две части: в левой части все элементы не больше х, в правой части массива не меньше х. Затем к каждой части массива применяется тот же алгоритм.

Пример:Отсортировать слово методом быстрой сортировки.

Условные обозначения: X ведущий элемент

X сравнение с ведущим элементом при просмотре справа

сравнение с ведущим элементом при просмотре слева

| разделение массива на части обмен элементов

 

К	У	Р	А	П	О	В	А	Е
Е	У	Р	А	П	О	В	А	К
Е	А	Р	А	П	О	В	У	К
Е	А	В	А	П	О	Р	У	К
Е	А	В	А	П	О	Р	У	К
А	А	В	Е	К	О	Р	У	П
А	А	В		К	О	Р	У	П
А	А	В				П	У	Р
	А	В					У	Р
							Р	У
А	А	В	Е	К	О	П	Р	У

Рисунок 9 Метод Хоара