Лабораторна робота № 9
модуль 1
Тема: Швидкі алгоритми сортування. Сортування Хоара. Динамічне сортування. (2 год)
Мета: Закріпити поняття складності алгоритма. Сформувати вміння застосовувати швидкі алгоритми сортування.
Література:
Архангельский А.Я. Язык Pascal и основы программирования в Delphi
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Культин Н.Б. Turbo Pascal в задачах и примерах
М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0
Меженный О.А. Turbo Pascal
Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal
Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.
Павловская Т.А. Паскаль. Программирование на языке высокого уровня
Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
Короткі теоретичні відомості.
Удосконаливши метод сортування, заснований на обмінах, К. Хоар запропонував алгоритм QuickSort сортування масивів, який дає на практиці відмінні результати і дуже просто програмується. Автор назвав свій алгоритм швидким сортуванням.
Ідея К. Хоара полягає в наступному:
1. Оберемо деякий елемент x масива A випадковим чином;
2. Переглядаємо масив у прямому напрямку (i = 1, 2,...), шукаючи в ньому елемент A[i] не менший, ніж x;
3. Переглядаємо масив у зворотному напрямку (j = n, n-1,..), шукаючи в ньому елемент A[j] не більший, ніж x;
4. Міняємо місцями A[i] і A[j].
Пункти 2-4 повторюємо до тих пір, поки i < j.
В результаті такого зустрічного проходу початок масива A[1..i] і кінець масива A[j..n] виявляються розділеними “бар’єром” x: A[k] ( x при k < i, A[k] ( x при k > j , причому на розмежування ми витратимо не больше n/2 перестановок. Тепер залишилось зробити ті ж дії з початком і кінцем масива, тобто застосувати їх рекурсивно! Таким чином, описана нами процедура Hoare залежить від параметрів k і m – початкового і кінцевого індексів відрізка масива, що обробляється.
Procedure Swap(i, j : Integer);
Var b : Real;
Begin
b := a[i]; a[i] := a[j]; a[j] := b
End;
Procedure Hoare(L, R : Integer);
Var left, right : Integer;
x : Integer;
Begin
If L < R then begin
x := A[(L + R) div 2]; {вибір бар’єра x}
left := L; right := R ;
Repeat {зустрічний проход}
While A[left] < x do Inc(left); {перегляд вперед}
While A[right] > x do Dec(right); {перегляд назад}
If left <= right then begin
Swap(left, right); {перестановка}
Inc(left); Dec(right);
end
until left > right;
Hoare(L, right); {сортуємо початок}
Hoare(left, R) {сортуємо кінець}
end
End;
Program QuickSort;
Const n = 100;
Var A : array[1..n] of Integer;
{ процедури Swap, Hoare, введення і виведення }
Begin
Inp; Hoare(1, n); Out
End.
Аналіз складності алгоритма в средньому, який використовує гіпотезу про рівну ймовірність всіх входів, показує, що C(n) = O(n log2 n), M(n) = O(n log2 n).
У найгіршому випадку, коли у якості бар’єрного обирається, наприклад, максимальний елемент підмасива, складність алгоритма квадратична.
Алгоритм пірамідального сортування HeapSort використовує представлення масива у вигляді дерева. Цей алгоритм не потребує допоміжних масивів, сортуючи “на місці”. Розглянемо спочатку метод представлення масива у вигляді дерева:
Нехай A[1 .. n] – деякий масив. Співставимо йому дерево, використовуючи наступні правила:

1.A[1] – корінь дерева ;
2.Якщо A[i] – вузол дерева і 2i ( n, то A[2*i] – вузол “лівий син” вузла A[i];
3.Якщо A[i] – вузол дерева і 2i + 1 ( n, то A[2*i+1] – вузол - “правий син” вузла A[i].
Правила 1 - 3 визначають у масиві структуру дерева, причому глибина дерева не перевищує [log2 n] + 1. Вони ж задають і спосіб руху по дереву від кореня до листів. Рух вверх задається правилом 4:
4.Якщо A[i] – вузол дерева і i > 1, то A[i mod 2] – вузол - “батько” вузла A[i].
Приклад: Нехай A = [45 13 24 31 11 28 49 40 19 27] - масив. Відповідне йому дерево має вигляд:
Зверніть увагу на те, що всі рівні дерева, за виключенням останнього, повністю заповнені, останній рівень заповнений зліва і індексація елементів масива здійснюється зверху-вниз і зліва-направо. Тому дерево упорядкованого масива задовольняє наступним властивостям: A[i] ( A[2*i], A[i] ( A[2*i+1], A[2*i] ( A[2*i+1].
Як це не дивно, алгоритм HeapSort спочатку будує дерево, яке задовольняє прямо протилежним співвідношенням
A[i] ( A[2*i], A[i] ( A[2*i+1],
а потім міняє місцями A[1] (найбільший елемент) і A[n].
Алгоритм HeapSort працює в два этапа:
I. Побудова сортуючого дерева;
II. Просівання елементів по сортуючому дереву.
Дерево, що представляє масив, називається сортуючим, якщо виконуються умови. Якщо для деякого i ця умова не виконується, будемо говорити, що має місце (сімейний) конфлікт у трикутнику i.
І на I-ому, і на II-ому етапах елементарна дія алгоритма полягає в розв’язанні сімейного конфлікта: якщо найбільший з синів більше, ніж батько, то переставляються батько и цей син (процедура ConSwap).
В результати перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. Таким чином можна говорити про конфлікт (рода) у піддереві з коренем у вершині i. Конфлікт рода розв’язується послідовним розв’язуванням сімейних конфліктів проходом по дереву зверху-вниз. Конфлікт рода розв’язаний, якщо прохід закінчився (i > n div 2) або в результаті перестановки не виник новий сімейний конфлікт. (процедура Conflict)
Procedure ConSwap(i, j : Integer);
Var b : Real;
Begin
If a[i] < a[j] then begin
b := a[i]; a[i] := a[j]; a[j] := b
end
End;
Procedure Conflict(i, k : Integer);
Var j : Integer;
Begin
j := 2*i;
If j = k
then ConSwap(i, j)
else if j < k then begin
if a[j+1] > a[j] then j := j + 1;
ConSwap(i, j); Conflict(j, k)
end
End;
I етап – побудова сортуючого дерева – оформимо у вигляді рекурсивної процедури, використовуючи визначення:
Якщо ліве і праве піддерева T(2i) і T(2i+1) дерева T(i) сортуючі, то для перестройки T(i) необхідно розв’язати конфлікт рода в цьому дереві.
Procedure SortTree(i : Integer);
begin
If i <= n div 2 then begin
SortTree(2*i); SortTree(2*i+1); Conflict(i, n)
end
end;
На II-ому етапі – етапі просіювання – для k від n до 2 повторюються наступні дії:
1.Переставити A[1] і A[k];
2.Побудувати сортуюче дерево початкового відрізка масива A[1..k-1], усунувши конфлікт рода в корені A[1]. Зауважимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.
Program HeapSort;
Const n = 100;
Var A : Array[1..n] of real;
k : Integer;
{процедури ConSwap, Conflict, SortTree, введення, виведення}
Begin
{ введення }
SortTree(1);
For k := n downto 2 do begin
ConSwap(k, 1); Conflict(1, k - 1)
end;
{ виведення }
End.
Нескладно підрахувати, що С(n) = O( n log2 n ), М(n) = O( n log2 n ).
Задачі для самостійного розв’язування
Нехай дано масив a1, a2, ... , an. Необхідно переставити його елементи так, щоб спочатку йшла група елементів, більших того елемента, який у вхідному масиві розташовувався на першому місці, потім – сам цей елемент, потім – група елементів, менших або рівних йому. Кількість порівнянь і переміщень, кожна окремо, не повинна перевищувати n-1.
Реалізувати ітеративну версію алгоритму HeapSort:
a) Замінити рекурсію у процедурі SortTree арифметичним циклом For...downto, який обробляє дерево по рівням, починаючи з нижнього;
б) Замінити рекурсію у процедурі Conflict ітераційним циклом, який керується змінною i. { i := 2i або i := 2i + 1 }.
Реалізувати ітеративну версію алгоритму процедури HoareSeach, замінивши рекурсію ітераційним циклом.
Реалізувати алгоритм “тернарного” пошуку елемента в упорядкованому масиві, розділяючи ділянку пошуку на 3 приблизно рівні частини. Оцінити складність алгоритму у термінах C(n). Порівняти ефективність бінарного і тернарного пошуку.
Відсортувати масив х за зростанням методом злиття (кількість дій не повинна перевищувати C*n*log(n).
Зауваження: Нехай k – додатне ціле число. Розіб’ємо масив x[1]..x[n] на відрізки довжини k. (Перший – x[1]..x[k], потім x[k+1]..x[2k] і т.і.) Останній відрізок буде неповним, якщо n не ділиться на k. Назвемо масив k-упорядкованим, якщо кожний з цих відрізків окремо упорядкований. Будь-який масив 1-упорядкований. Якщо масив k-упорядкований і n<=k, то він упорядкований. Алгоритм перетворення k-упорядкованого масиву в 2k-упорядкований:
k:=1;
{масив x є k-упорядкованим}
while k < n do begin
| .. перетворити k-упорядкований масив у 2k-упорядкований;
| k := 2 * k;
end;
2. Знайти кількість різних чисел серед елементів даного масиву. Число дій порядку n*log n.
Вказівка. Відсортувати числа, а потім порахувати кількість різних, переглядаючи елементи масиву лінійно.
6. Дано n точок на площині. Побудувати їх опуклу оболонку – мінімальну опуклу фігуру, яка містить ці точки. Кількість операцій не більше n*log n.
Вказівка. Упорядкуємо точки. Потім, розглядаючи точки по черзі, будемо будувати опуклу оболонку вже розглянутих точок.
7. Маємо масив цілих чисел a[1]..a[n], причому всі числа невід’ємні і не перевищують m. Відсортувати цей масив; число дій порядку m+n.
Вказівка. Для кожного числа від 0 до m підраховуємо, скільки разів воно зустрічається у масиві. Після цього вхідний масив можна стерти і заповнити знову у порядку зростання, використовуючи відомості про кратність кожного числа. Відзначимо, що цей алгоритм не переставляє числа у масиві, як більшість інших, а "записує їх туди знову".
8. У масиві a[1]..a[n] цілих чисел переставити елементи так, щоб парні числа йшли перед непарними (не змінюючи взаємний порядок у кожній з груп).
Вказівка. Спочатку спишемо (у допоміжний масив) всі парні, а потім – всі непарні.
9. Маємо масив з n чисел від 0 до (2 в степені k) – 1, кожне з яких ми будемо розглядати як k-бітове слово з нулів і одиниць. Використовуючи перевірки "i-ий біт дорівнює 0" і "i-ий біт дорівнює 1" замість порівнянь, відсортувати всі числа за час порядка n*k.
Вказівка. Відсортуємо числа за останнім бітом, потім за передостаннім і таке інше. В результаті вони будуть відсортовані.
10. Маємо квадратну таблицю a[1..n, 1..n]. Відомо, що для деякого i рядок з номером i заповнений одними нулями, а стовбець з номером i – одними одиницями (за виключенням їх перетину на діагоналі, де стоїть невідомо що). Знайти таке i (воно єдине). Кількість дій не перевищує C*n. (Зауважимо, що це суттєво менше кількості елементів у таблиці).
Вказівка. Розгляньте a[i][j] як результат "порівняння" i з j та згадайте, що самий важкий з n каменів може бути знайдений за n порівнянь.
11.Нехай дано масив a1, a2, ... , an. Необхідно переставити його елементи так, щоб спочатку йшла група елементів, більших того елемента, який у вхідному масиві розташовувався на першому місці, потім – сам цей елемент, потім – група елементів, менших або рівних йому. Кількість порівнянь і переміщень, кожна окремо, не повинна перевищувати n-1.
12.Реалиізувати ітеративну версію алгоритма HeapSort:
a) Замінити рекурсію у процедурі SortTree арифметичним циклом For...downto, який обробляє дерево по рівням, починаючи з нижнього;
б) Замінити рекурсію у процедурі Conflict ітераційним циклом, який керується змінною i. { i := 2i або i := 2i + 1 }.
13.Реалізувати ітеративну версію алгоритма процедури HoareSeach, замінивши рекурсію ітераційним циклом.
14.Реалізувати алгоритм “тернарного” пошуку елемента в упорядкованому масиве, розділяючи ділянку пошуку на 3 приблизно рівні частини. Оцінити складність алгоритма у термінах C(n). Порівняти ефективність бінарного і тернарного пошуку.
15.Відсортувати масив х за зростанням методом злиття (кількість дій не повинна перевищувати C*n*log(n).
Зауваження: Нехай k – додатнє ціле число. Розіб’ємо масив x[1]..x[n] на відрізки довжини k. (Перший – x[1]..x[k], потім x[k+1]..x[2k] і т.і.) Останній відрізок буде неповним, якщо n не ділиться на k. Назвемо масив k-упорядкованим, якщо кожний з цих відрізків окремо упорядкований. Будьякий масив 1-упорядкований. Якщо масив k-упорядкований і n<=k, то він упорядкований. Алгоритм перетворення k-упорядкованого масива в 2k-упорядкований:
k:=1;
{масив x є k-упорядкованим}
while k < n do begin
| .. перетворити k-упорядкований масив у 2k-упорядкований;
| k := 2 * k;
end;