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


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

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;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.