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

Міністерство освіти і науки України

Вінницький національний технічний університет

Факультет інформаційних технологій та комп’ютерної інженерії

Кафедра комп’ютерних наук

Лабораторна робота №4

З дисципліни «Теорія Алгоритмів»

Тема: «Аналіз алгоритму сортування методом купи»

Виконав:

Студент групи 1КН-18б

Дзигар В. Ю.

Перевірив:

Арсенюк І. Р.

Вінниця, 2018

Тема: Аналіз алгоритму сортування методом купи.

Мета: навчитись аналізувати алгоритми на прикладі алгоритму сортування методом купи.

Сортування купою — алгоритм сортування, працює в найгіршому, в середньому і в найкращому випадку (тобто гарантовано) за Θ(n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто потребує додаткову пам’ять O (1), а не О(n),як сортування злиттям.

Алгоритм сортування за допомогою купи використовує структуру даних - двійкову купу.

Двійковою купою називається масив з визначеними властивостями впорядкованості. Щоб сформулювати ці властивості, будемо розглядати масив як двійкове дерево.

• Кожна вершина дерева відповідає елементу масива. Якщо вершина має індекс і, то її батько має індекс i/2. Вершина з індексом 1 -це корінь, а її дочірні вершини мають індекси 2і та 2і+1.
• Купа може не займати весь масив -тому зберігатимемо не лише масив Аі його довжину length[A], а й розмір купи heap-size[A], причому heap-size[A]≤ length[A].  Купа складається з елементів A[1], …, A[heap-size[A]].
• Рух по дереву здійснюється за допомогою процедур

PARENT(i)  —>return i/2

LEFT(i)        —>return 2i;

RIGHT(i)         —>return 2i + 1.

Властивість купи: значення нащадка не перевищує значення батька. Таким чином, найбільший елемент дерева (або будь-якого піддерева) знаходиться у кореневій вершині цього дерева (або піддерева).

Висота вершини дерева – це число ребер у найдовшому шляху, який починається у цій вершині, йде вниз по дереву і закінчується листком. Тобто, висота дерева збігається з висотою його кореня.

У дереві, що утворює купу, усі рівні (крім, можливо, останнього) заповнені повністю. Тому висота цього дерева дорівнює О(logn), де n–число елементів купи.

Час роботи основних операцій над купою пропорційний висоті дерева і , відповідно, складає О(logn).

Основні операції над купою :

• Процедура HEAPIFY дозволяє підтримувати головні властивості купи. Час її роботи складає θ(logn).

• Процедура BUILD-HEAP будує купу з вихідного (невідсортованого) масиву. Час її роботи θ(n).

• Процедура HEAPSORT сортує масив, не використовуючи допоміж-ної пам’яті. Час її роботи θ (n⋅logn).

• Процедури EXTRACT-MAX (отримання найбільшого) і INSERT (доповнення елементу) використовується при моделюванні черги.

Ідея  алгоритму:

Якщо головна властивість не виконана для вершини i, то її слід поміняти із старшою         з її дочірніх вершин і т. д., доти, поки елемент А[i] не „завантажиться” до потрібного місця.

[pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

Процедура  HEAPIFY

[pic 6]

Приклад виконання процедури HEAPIFY

[pic 7]

Побудова купи. Процедура BUILD-HEAP

Для перетворення масиву А[1...n] на купу можна використати процедуру HEAPIFY, застосовуючи її по черзі до усіх вершин, починаючи з нижніх.  

Приклад роботи процедури BUILD-HEAP

[pic 8]

[pic 9]

Алгоритм сортування за допомогою купи

Даний алгоритм має 2 частини:

1) Спочатку викликається процедура BUILD-HEAP, після виконання якої масив стає купою.

2) Ідея другої частини така: максимальний елемент масиву тепер знаходиться у корені дерева А[1]. Його слід поміняти з елементом А[n], зменшити розмір купи на 1 і відновити головну властивість у кореневій вершині.

...