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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Пирамидальная сортировка HeapSort. Пирамида Хеопса. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Пример 2 3 4 5 6 7 8 - пирамида 3 2 6 3 4 5 7 1 2 3 4 5 6 7 - не пирамида

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Построение пирамиды Теперь элемент Х попал на место 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

Слайд 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

Слайд 8

Описание слайда:

Трудоемкость алгоритма Трудоемкость алгоритма построения пирамиды Определим верхнюю границу трудоемкости алгоритма. На каждой итерации цикла выполняется максимум два сравнения и одна пересылка. Найдем наибольшее количество итераций ( 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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

| 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

Слайд 11

Описание слайда:

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 К У Р А П О В А П О В А А П О В А Р А П О В А В А П О Р А У В А П О Р А А В У П О Р А А В А П О Р У К А В А П О Р У А К В А П О Р У А А В К П О Р У

Слайд 12

Описание слайда:

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У П О А В К Р У П О В К О У П Р Р К О У П В К Р О У П К П О У Р

Слайд 13

Описание слайда:

Р П О У К Р П О У К О П Р У У П Р О П У Р Р У П Р У У Р У Р П О К В А A

Слайд 14

Описание слайда:

Трудоемкость пирамидальной сортировки (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 Пирамидальная сортировка не устойчива. Метод практически не зависит от исходной упорядоченности массива.