то T (N) = N ln N. при всіх N = 2 k. k> 1.
2. При пошуку заданого елемента способом лінійного пошуку (вправа 2 алгоритму сортування вставками) проводиться порівняння з елементами від початку масиву. У відсортованому масиві можна використовувати порівняння шуканого елемента з серединою масиву, потім вибрати ту частину, в якій він буде знаходитися і для цієї частини повторити рекурсивне поділ і так далі - двоіч-
ний пошук. Напишіть програму, що реалізовує даний алгоритм, і доведіть, що час її роботи є Θ (ln N).
3. Цикл while в процедурі Insertion_Sort переглядає всі елементи відсортованого ділянки поспіль. Замість цього можна використовувати метод двійкового
пошуку (вправа 2 алгоритму сортування злиттям), щоб знайти місце вставки за час Θ (ln N). Напишіть відповідну реалізацію процедури
Insertion_Sort і визначте, чи вдасться таким чином зробити загальний час роботи рівним Θ (N ln N).
Алгоритм сортування злиттям
4. Нехай сортування вставками і злиттям виконуються на одній і тій же машині і вимагають 8 N 2 і 64 N ln N операцій відповідно. Для яких значень N сортування вставками є більш ефективною? Як можна поліпшити алгоритм сортування злиттям?
5. При якому найменшому значенні N алгоритм, що вимагає 100 N 2 операцій, ефективніше алгоритму, що вимагає 2 N операцій.
1. асимптотичними сортування злиттям швидше сортування вставками, але для малих значень N співвідношення зворотне. Тому, має сенс досить короткі шматки не розділяти далі, а сортувати вставками.
1.1. Нехай масив розміру N розбитий на k частин розміру N k. Покажіть, що
можна впорядкувати всі частини окремо (за допомогою сортування вставками) за час Θ (kN).
1.2. Покажіть, що після сортування можна злити всі частини в один упорядкований масив за час Θ (N ln (N k)).
1.3. Середній час роботи такого змішаного алгоритму є Θ (Nk + N ln (N k)). Яка максимальна швидкість росту k як функції від
N. при якій цей час як і раніше дорівнює Θ (N ln N)?
1.4. Як визначити оптимальне значення k на практиці.
2. Нехай дано масив a [1. N]. Інверсією в цьому масиві називається пара чисел i
2.1. Яка максимальна кількість інверсій в масиві довжини N.
2.2. Як пов'язано час роботи алгоритму сортування вставками і число інверсій? Поясніть свою відповідь.
2.3. Побудуйте алгоритм, який вважає число інверсій в масиві довжини N за час Θ (N ln N).
Малюнок 3 - Приклад двійковій купи
Алгоритм сортування за допомогою купи (Heap)
Алгоритм сортування за допомогою купи (Heap)
Сортування за допомогою купи вимагає для своєї роботи час T (N) = Θ (N ln N). але на відміну від алгоритмів злиття не вимагає такого великого
обсягу додаткової пам'яті для зберігання змінних. Тобто алгоритм поєднує в собі переваги алгоритмів сортування вставкою (використання малого об'єму додаткової пам'яті) і методом злиття (малий час роботи).
Структура даних, яку використовує алгоритм, називається двійковій купою, вона зручна при використанні черг з пріоритетами.
Двійковій купою називається масив з певними властивостями впорядкованості. Для формулювання властивостей будемо розглядати масив як двійкове дерево. Кожна вершина дерева відповідає елементу - малюнок 3.
Якщо вершина має індекс i. то її батько має індекс int (i / 2). а її по-
Томко 2 i і 2 i + 1. Вершина з індексом i = 1 є коренем. У пам'яті зберігається масив a. його довжина N і спеціальний параметр Heap _ Size - розмір купи, причому
Heap _ Size ≤ N. Купа складається з елементів a [1] ... a [Heap _ Size]. Для переміщення по купі використовуються три функції:
Елементи, що зберігаються в купі, повинні володіти основним властивістю купи: для всіх елементів, крім кореня, має виконуватися умова a Parent (i) ≥ a [i],
тобто значення нащадка повинно бути не більше предка, а це значить, що коренем дерева є максимальний елемент.
Висотою вершини дерева називається висота піддерева з коренем у цій вершині (число ребер в самому довгому шляху з початком в цій вершині вниз по дереву). Висота дерева збігається з висотою його кореня.
У дереві, що становить купу, всі рівні, крім, може бути, останнього, заповнені повністю, тому висота цього дерева дорівнює Θ (ln N). де N - число
елементів в купі.
Розглянемо основні процедури для роботи з купою:
1. Heapify - підтримує основну властивість купи, час виконання одно
Алгоритм сортування за допомогою купи (Heap)
2. Build_Heap - будує купу з вихідного несортоване масиву, час виконання одно Θ (N).
3. Heap_Sort - сортування без використання додаткової пам'яті, час виконання Θ (N ln N).
4. Extract_Max (вилучення найбільшого) і Insert (вставка) використовуються для створення черги з пріоритетами на базі купи. Час роботи обох процедур становить Θ (ln N).
Збереження основного властивості купи
Параметрами процедури Heapify (a, i) є масив a і індекс i. Передбачається, що піддерева з корінням Left (i) і Right (i) вже мають основною властивістю. Процедура переставляє елементи поддерева з вершиною i. після чого воно буде володіти основною властивістю. Ідея проста: якщо основне властивість не здійснимо для вершини, то її слід поміняти з великим з її нащадків, і так далі, поки елемент не «зануриться» до потрібного місця.
Розглянемо процедуру Heapify (A, i)
3 if (L≤Heap_Size) and (a [L]> a [i])
4 then Largest: = L
5 else Largest: = R
6 if (R≤Heap_Size) and (a [R]> a [Largest])
7 then Largest: = R
9 then Swap (a [i], a [Largest])
У змінну Largest поміщається індекс найбільшого з елементів a [i],
a Left (i) і a Right (i). Якщо після закінчення циклу Largest = i. то елемент a [i] вже
«Занурився» до потрібного місця і робота процедури закінчена. Інакше, процедура змінює місцями a [i] і a [Largest]. але при цьому, можливо, мало місце порушення
основного властивості в поддереве з вершиною Largest і рекуррентно викликається процедура Heapify для усунення можливого порушення.
Час виконання в гіршому випадку для цієї процедури T (N) = Θ (ln N).
Нехай дано масив a [1. N]. який слід перетворити в купу. Для цього можна застосовувати процедуру Heapify. застосовуючи її по черзі до всіх вершин, починаючи з нижніх. Вершини з номерами [N 2] + 1 ... N є листям, значить,
піддерева з цими листами вже задовольняють основному властивості купи. Для кожної з решти вершин, в порядку убування індексів, слід застосувати про-
2 For i: = int (N / 2) downto 1 do
Максимальний час роботи процедури становить T (N) = Θ (N).
Сортування за допомогою купи
Алгоритм сортування складається з двох частин, в першій викликається процедура Build_Heap. перетворює масив в купу.
Друга частина безпосередньо впорядковує купу. Максимальний елемент купи знаходиться в корені дерева - елемент a [1]. Цей елемент міняється місцями з
елементом a [N]. зменшується розмір купи на 1 і відновлюється основне властивість купи в кореневій вершині (оскільки в піддерево з корінням Left (1) і Right (1) основне властивість купи немає порушилося) за допомогою процедури Heapify.
Після цього в корені буде перебувати максимальний з решти елемент. Потім виконується перестановка a [1] і a [N - 1]. І знову виконується процедура
Перестановка елементів триває до тих пір, поки не буде відсортований весь масив.
2 For i: = N downto 2 do
Час роботи процедури становить T (N) = Θ (N ln N).
На практиці алгоритми сортування за допомогою купи не є найшвидшими, проте сама купа як структура даних частот виявляється корисною.
Черги з пріоритетами
Черга з пріоритетами (priority queue) - це безліч, елементи якого будемо вважати числами. На практиці елементами безлічі S є пари
чом, α - пов'язана з ним інформація; ця інформація зберігається поряд з елементом і переміщається разом з ним, не впливаючи на його обробку. Для простоти будемо опускати опис роботи з додатковими даними.
Можливі такі операції над чергою з пріоритетами:
1. Insert (S, x) додає елемент х до безлічі S;
2. Maximum (S) повертає найбільший елемент множини;
3. Extract_Max (S) вилучає з безлічі найбільший елемент;
4. Extract_Min (S) вилучає з безлічі найменший елемент.
Черга з пріоритетами може, наприклад, використовуватися в операційній системі з поділом часу. При цьому в ній зберігається список завдань з приори-
Алгоритм сортування за допомогою купи (Heap)
тетамі. Як тільки виконання чергового завдання закінчується, з черги вибирається завдання з найбільшим пріоритетом (операція Extract_Max). Нові завдання додаються в чергу за допомогою операції Insert.
Інше застосування тієї ж структури - кероване подіями моделювання (event-driven simulation). У черзі перебувають події, а пріоритет визначається часом, коли подія має відбутися. Події повинні моделюватися в тому порядку, в якому вони відбуваються. Вибір чергового події проводиться за допомогою операції Extract_Min. додавання подій - за допомогою операції
Будемо зберігати елементи безлічі у вигляді купи. При цьому максимальний елемент знаходиться в корені, так що операція Maximum вимагає часу Θ (1).
Щоб вилучити максимальний елемент з черги, потрібно діяти так само, як і при сортуванні: