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

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

Вашему вниманию предлагается презентация на тему «Пирамидальная сортировка HeapSort. Пирамида Хеопса», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 15 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 2.72 MB

Просмотреть и скачать

Pic.1
Пирамидальная сортировка HeapSort Пирамида Хеопса
Пирамидальная сортировка HeapSort Пирамида Хеопса
Pic.2
Пирамидальная сортировка или метод Вильямса – Флойда ( Williams, Floyd, 1964) Пирамидальная сортиров
Пирамидальная сортировка или метод Вильямса – Флойда ( Williams, Floyd, 1964) Пирамидальная сортировка основана на алгоритме построения пирамиды. Определение Последовательность aL , aL+1 , … , aR называется пирамидой, если неравенство ai ≤ min (a2i , a2i+1 ) выполняется для всех i, для которых хотя бы один из элементов a2i и a2i+1 существует.
Pic.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 - не пирамида
Pic.4
Построение пирамиды Пусть aL+1 , …, aR - пирамида, необходимо добавить элемент Х, чтобы получить нов
Построение пирамиды Пусть aL+1 , …, aR - пирамида, необходимо добавить элемент Х, чтобы получить новую пирамиду aL , …, aR. Новый элемент добавляем в начало, расширяя последовательность влево. Если aL удовлетворяет условию пирамиды, то пирамида построена.
Pic.5
Построение пирамиды Иначе найдутся такие a2L или a2L+1 , что не будут удовлетворять условию пирамиды
Построение пирамиды Иначе найдутся такие a2L или a2L+1 , что не будут удовлетворять условию пирамиды. Возьмем минимальный элемент из a2L и a2L+1 , обозначим его за aj и обменяем с aL . В результате получим a’L ≤ a2L и a’L ≤ a2L+1 , что удовлетворяет условию пирамиды.
Pic.6
Построение пирамиды Теперь элемент Х попал на место aj и для него необходимо проверить условие пирам
Построение пирамиды Теперь элемент Х попал на место 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
Pic.7
Построение пирамиды (L ,R) Алгоритм на псевдокоде aL+1, …, a R – на входе пирамида (L+1,R) aL – новы
Построение пирамиды (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
Pic.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
Pic.9
Пирамидальная сортировка (HeapSort) Пирамидальная сортировка (HeapSort) Первый этап. Построение пира
Пирамидальная сортировка (HeapSort) Пирамидальная сортировка (HeapSort) Первый этап. Построение пирамиды из элементов массива. В соответствии со свойством 3 правая часть массива уже пирамида. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в нее не войдут все элементы массива. Второй этап. Собственно сортировка. По свойству 2 в пирамиде первый элемент минимальный. Производим двустороннее усечение пирамиды: уберем элементы а1 и аn. По свойству 1 a2, . . , an-1 – пирамида. Поставим элемент а1 на последнее место, а элемент аn добавим к пирамиде a2,. . ,an-1. Отсекаем последний элемент и повторяем действия, пока пирамида не исчезнет.
Pic.10
| L := n/2 | L := n/2 | DO ( L>0 ) 1 | Построение пирамиды (L, n) | L := L-1 | OD | R := n |
| 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
Pic.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 К У Р А П О В А П О В А А П О В А Р А П О В А В А П О Р А У В А П О Р А А В У П О Р А А В А П О Р У К А В А П О Р У А К В А П О Р У А А В К П О Р У
Pic.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 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У П О А В К Р У П О В К О У П Р Р К О У П В К Р О У П К П О У Р
Pic.13
Р П О У К Р П О У К О П Р У У П Р О П У Р Р У П Р У У Р У Р П О К В А A
Р П О У К Р П О У К О П Р У У П Р О П У Р Р У П Р У У Р У Р П О К В А A
Pic.14
Трудоемкость пирамидальной сортировки (HeapSort) Трудоемкость пирамидальной сортировки (HeapSort) Оц
Трудоемкость пирамидальной сортировки (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 Пирамидальная сортировка не устойчива. Метод практически не зависит от исходной упорядоченности массива.
Pic.15
Пирамидальная сортировка HeapSort. Пирамида Хеопса, слайд 15


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!