Быстрые алгоритмы сортировки (стр. 2 из 3)
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].
Як і TreeSort, алгоритм HeapSort працює в два етапи:
I. Побудова сортуючого дерева;
II. Просівання елементів по сортуючому дереву.
Дерево, що представляє масив, називається сортуючим, якщо виконуються умови (6). Якщо для деякого i ця умова не виконується, будемо говорити, що має місце (сімейний) конфлікт у трикутнику i.
Як на I-ом, так і на II-ому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура ConSwap).
У результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт (роду) у піддереві з коренем у вершині i. Конфлікт роду вирішується послідовним вирішенням сімейних конфліктів проходом по дереву вниз. (На мал шлях вирішення конфлікту роду у вершині 2 відзначений). Конфлікт роду вирішено, якщо прохід закінчився (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 )
1.3 Швидке сортування Хоара
Удосконаливши метод сортування, який грунтується на обмінах, К. Хоар запропонував алгоритм 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)
У гіршому випадку, коли в якості бар'єрного вибирається, наприклад, максимальний елемент підмассиву, складність алгоритму квадратична.
1.4 Метод цифрового сортування
Іноді при розв’язанні задач типу задачі сортування можна використовувати особливості типу перетворюваних даних для одержання ефективного алгоритму. Розглянемо одну з таких задач - задачу про звертання підстановки.
Підстановкою безлічі 1..n назвемо двовимірний масив A[1..2, 1..n] виду
| 1 | 2 | .......... | n-1 | n |
| J1 | j2 | ........... | jn-1 | jn |
у якому 2-ий рядок містить всі елементи відрізка 1..n. Підстановка B називається зворотньою до підстановки A, якщо B виходить з A сортуванням стовпчиків A у порядку зростання елементів 2-го рядка з наступною перестановкою рядків. Потрібно побудувати алгоритм обчислення зворотньої підстановки. З визначення випливає, що стовпчик [i, ji] підстановки A потрібно перетворити в стовпчик [ji , i] і поставити на ji-те місце в підстановці B.
{Type NumSet = 1..n;
Substitution = array[ 1..2, NumSet] of NumSet; }
Procedure Reverse ( Var A, B : Substitution);
Begin
For i := 1 to n do begin
B[A[2, i], 2] := i; B[A[2, i], 1] := A[2, i]
end
End;
Складність процедури Reverse лінійна, оскільки тіло арифметичного циклу складається з двох операторів присвоювання, в той час як стовпчики підстановки відсортовані.
2. Практична реалізація мовою Паскаль швидких алгоритмів сортування
Практичною метою нашої дослідницької роботи було написання мовою Pascal програми, яка б виконувала сортування будь-якої послідовності елементів. Для того, щоб продемонструвати роботу різних швидких алгоритмів сортування, ми залишили вибір конкретного алгоритму на розсуд користувача програми. Тобто, ми створили основну програму – меню, яка пропонує користувачеві три можливі варіанти швидких алгоритмів сортування: швидке сортування, сортування Хоара та сортування “злиттям”. Вибір певного алгоритму здійснюється за допомогою оператору “caseof”, тобто натисканням клавіш клавіатури 1, 2 або 3. Також ми передбачили варіант, коли користувач програми натискає будь-яку іншу клавішу: в цьому випадку на екрані з’явиться повідомлення про помилку. Також, після проведення сортування за вибраним алгоритмом, користувач зможе продовжити роботу й випробувати інший алгоритм. Для цього потрібно натиснути клавіші клавіатури “у” або “д” або набрати слово “yes” чи “да” коли після завершення роботи одного з обраних алгоритмів сортування на екрані з’явиться запитання “Хотите ли вы продолжить работу с данной программой?”. Якщо ж користувач уже випробував усі алгоритми або за браком часу (або бажання) хоче завершити роботу з програмою, то йому достатньо буде лише натиснути на клавіатурі клавіші “n” або “н” чи набрати слова “no” або “нет” після того, як на екрані з’явиться зазначене вище запитання.
Програма виконує сортування послідовності за трьома алгоритмами сортування. Кожний окремий алгоритм представлений у вигляді окремої процедури.
Так, процедура Qsort виконує швидке сортування масиву, що вводиться. Під час роботи цього алгоритму відбувається аналіз даної послідовності одночасно у двох напрямках ( зліва-направо і зправа-наліво) . комп’ютер порівнює два елементи, що стоять поряд зліва. Якщо ці елементи стоять на своїх місцях, тобто перший з них є меншим за другий, то комп’ютер порівнює перший елемент з останнім. Якщо при порівнянні останній елемент виявиться меншим за перший, то комп’ютер виконає перестановку цих двох елементів. Такі дії будуть відбуватися до тих пір, поки індикатор, якій відповідає за ліву частину послідовності (в нашій процедурі це “i”) не перейде на праву частину, а індикатор, що відповідає за праву частину масиву (в нашій процедурі це “j”) не перейде на праву частину. Далі та ж сама процедура викликається рекурсивно. Тобто, якщо ліва частина вже відсортована, то ми викликаємо ту саму процедуру і комп’ютер виконує ті самі дії, але в параметрах процедури ми змінюємо ліву границю. Те саме відбувається, коли відсортована права частина масиву.
По суті цей алгоритм працює на основі алгоритму сортування обмінами, але цей алгоритм вважається швидким, оскільки перегляд послідовності відбувається у двох напрямках одночасно. Реалізовано ж цей алгоритм за допомогою оператору “if”, який відповідає за порівняння елементів, та пересилань.