Презентация Пирамидальная сортировка HeapSort. Пирамида Хеопса онлайн

Содержание слайда: Пирамидальная сортировка HeapSort Пирамида Хеопса

Содержание слайда: Пирамидальная сортировка или метод Вильямса – Флойда ( Williams, Floyd, 1964) Пирамидальная сортировка основана на алгоритме построения пирамиды. Определение Последовательность aL , aL+1 , … , aR называется пирамидой, если неравенство ai ≤ min (a2i , a2i+1 ) выполняется для всех i, для которых хотя бы один из элементов a2i и a2i+1 существует.

Содержание слайда: Пример 2 3 4 5 6 7 8 - пирамида 3 2 6 3 4 5 7 1 2 3 4 5 6 7 - не пирамида

Содержание слайда: Построение пирамиды Пусть aL+1 , …, aR - пирамида, необходимо добавить элемент Х, чтобы получить новую пирамиду aL , …, aR. Новый элемент добавляем в начало, расширяя последовательность влево. Если aL удовлетворяет условию пирамиды, то пирамида построена.

Содержание слайда: Построение пирамиды Иначе найдутся такие a2L или a2L+1 , что не будут удовлетворять условию пирамиды. Возьмем минимальный элемент из a2L и a2L+1 , обозначим его за aj и обменяем с aL . В результате получим a’L ≤ a2L и a’L ≤ a2L+1 , что удовлетворяет условию пирамиды.

Содержание слайда: Построение пирамиды Теперь элемент Х попал на место aj и для него необходимо проверить условие пирамиды, и так до конца массива. Пример: 1 2 3 4 5 6 7 8 3 2 6 3 4 5 7 6 3 2 6 3 4 5 7 2 3 6 6 3 4 5 7 2 3 4 6 3 6 5 7

Содержание слайда: Построение пирамиды (L ,R) Алгоритм на псевдокоде aL+1, …, a R – на входе пирамида (L+1,R) aL – новый элемент x := aL, i := L DO j := 2i IF ( j>R) OD FI IF ( j<R и aj+1  aj ) j=j+1 FI IF ( xaj ) OD FI ai= aj i:=j OD ai:=x

Содержание слайда: Трудоемкость алгоритма Трудоемкость алгоритма построения пирамиды Определим верхнюю границу трудоемкости алгоритма. На каждой итерации цикла выполняется максимум два сравнения и одна пересылка. Найдем наибольшее количество итераций ( k ). Наихудший случай, когда в перестановках участвуют элементы aL , a2L , a4L … aL … a2L a2L+1 … a4L a4L+1 … am amL+1 … aR 21 22 2k mL ≤ R L ≤ R ≤ k≤ C = 2k M = k+2 C = 2 M = + 2

Содержание слайда: Пирамидальная сортировка (HeapSort) Пирамидальная сортировка (HeapSort) Первый этап. Построение пирамиды из элементов массива. В соответствии со свойством 3 правая часть массива уже пирамида. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в нее не войдут все элементы массива. Второй этап. Собственно сортировка. По свойству 2 в пирамиде первый элемент минимальный. Производим двустороннее усечение пирамиды: уберем элементы а1 и аn. По свойству 1 a2, .., an-1 – пирамида. Поставим элемент а1 на последнее место, а элемент аn добавим к пирамиде a2,..,an-1. Отсекаем последний элемент и повторяем действия, пока пирамида не исчезнет.

Содержание слайда: | L := n/2 | L := n/2 | DO ( L>0 ) 1 | Построение пирамиды (L, n) | L := L-1 | OD | R := n | DO ( R>1) 2 | a1↔aR | R := R-1 | Построение пирамиды (1, R) | OD

Содержание слайда: 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 К У Р А П О В А П О В А А П О В А Р А П О В А В А П О Р А У В А П О Р А А В У П О Р А А В А П О Р У К А В А П О Р У А К В А П О Р У А А В К П О Р У

Содержание слайда: 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У П О А В К Р У П О В К О У П Р Р К О У П В К Р О У П К П О У Р

Содержание слайда: Р П О У К Р П О У К О П Р У У П Р О П У Р Р У П Р У У Р У Р П О К В А A

Содержание слайда: Трудоемкость пирамидальной сортировки (HeapSort) Трудоемкость пирамидальной сортировки (HeapSort) Оценим трудоемкость сортировки, используя уже известную оценку трудоемкости построения пирамиды: C = 2 M = + 2 На первом этапе построение пирамиды производится n/2 раз, на втором этапе – n-1 раз. Очевидно, трудоемкость пирамидальной сортировки имеет порядок O(n log2n), , n→∞. Количество операций сравнения и пересылки оценивается следующими неравенствами: C < 2 n log2n + n + 2 M < n log2n + 6.5n - 4 Пирамидальная сортировка не устойчива. Метод практически не зависит от исходной упорядоченности массива.

Содержание слайда: