🗊Презентация Пирамидальная сортировка 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 Пирамида Хеопса
Описание слайда:
Пирамидальная сортировка HeapSort Пирамида Хеопса

Слайд 2


Пирамидальная сортировка или метод Вильямса – Флойда ( Williams, Floyd, 1964) Пирамидальная сортировка основана на алгоритме построения пирамиды. Определение Последовательность aL , aL+1 , … , aR называется пирамидой, если неравенство ai ≤ min (a2i , a2i+1 ) выполняется для всех i, для которых хотя бы один из элементов a2i и a2i+1 существует.
Описание слайда:
Пирамидальная сортировка или метод Вильямса – Флойда ( 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 - не пирамида
Описание слайда:
Пример 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 удовлетворяет условию пирамиды, то пирамида построена.
Описание слайда:
Построение пирамиды Пусть aL+1 , …, aR - пирамида, необходимо добавить элемент Х, чтобы получить новую пирамиду aL , …, aR. Новый элемент добавляем в начало, расширяя последовательность влево. Если aL удовлетворяет условию пирамиды, то пирамида построена.

Слайд 5


Построение пирамиды Иначе найдутся такие a2L или a2L+1 , что не будут удовлетворять условию пирамиды. Возьмем минимальный элемент из a2L и a2L+1 , обозначим его за aj и обменяем с aL . В результате получим a’L ≤ a2L и a’L ≤ a2L+1 , что удовлетворяет условию пирамиды.
Описание слайда:
Построение пирамиды Иначе найдутся такие 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
Описание слайда:
Построение пирамиды Теперь элемент Х попал на место 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<R и aj+1  aj ) j=j+1 FI IF ( xaj ) OD FI ai= aj i:=j OD ai:=x
Описание слайда:
Построение пирамиды (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

Слайд 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
Описание слайда:
Трудоемкость алгоритма Трудоемкость алгоритма построения пирамиды Определим верхнюю границу трудоемкости алгоритма. На каждой итерации цикла выполняется максимум два сравнения и одна пересылка. Найдем наибольшее количество итераций ( 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. Отсекаем последний элемент и повторяем действия, пока пирамида не исчезнет.
Описание слайда:
Пирамидальная сортировка (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
Описание слайда:
| 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 К У Р А П О В А П О В А А П О В А Р А П О В А В А П О Р А У В А П О Р А А В У П О Р А А В А П О Р У К А В А П О Р У А К В А П О Р У А А В К П О Р У
Описание слайда:
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 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У П О А В К Р У П О В К О У П Р Р К О У П В К Р О У П К П О У Р
Описание слайда:
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У П О А В К Р У П О В К О У П Р Р К О У П В К Р О У П К П О У Р

Слайд 13


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

Слайд 15


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию