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 програми, яка б виконувала сортування будь-якої послідовності елементів. Для того, щоб продемонструвати роботу різних швидких алгоритмів сортування, ми залишили вибір конкретного алгоритму на розсуд користувача програми. Тобто, ми створили основну програму – меню, яка пропонує користувачеві три можливі варіанти швидких алгоритмів сортування: швидке сортування, сортування Хоара та сортування “злиттям”. Вибір певного алгоритму здійснюється за допомогою оператору “case of”, тобто натисканням клавіш клавіатури 1, 2 або 3. Також ми передбачили варіант, коли користувач програми натискає будь-яку іншу клавішу: в цьому випадку на екрані з’явиться повідомлення про помилку. Також, після проведення сортування за вибраним алгоритмом, користувач зможе продовжити роботу й випробувати інший алгоритм. Для цього потрібно натиснути клавіші клавіатури “у” або “д” або набрати слово “yes” чи “да” коли після завершення роботи одного з обраних алгоритмів сортування на екрані з’явиться запитання “Хотите ли вы продолжить работу с данной программой?”. Якщо ж користувач уже випробував усі алгоритми або за браком часу (або бажання) хоче завершити роботу з програмою, то йому достатньо буде лише натиснути на клавіатурі клавіші “n” або “н” чи набрати слова “no” або “нет” після того, як на екрані з’явиться зазначене вище запитання.
Програма виконує сортування послідовності за трьома алгоритмами сортування. Кожний окремий алгоритм представлений у вигляді окремої процедури.
Так, процедура Qsort виконує швидке сортування масиву, що вводиться. Під час роботи цього алгоритму відбувається аналіз даної послідовності одночасно у двох напрямках ( зліва-направо і зправа-наліво) . комп’ютер порівнює два елементи, що стоять поряд зліва. Якщо ці елементи стоять на своїх місцях, тобто перший з них є меншим за другий, то комп’ютер порівнює перший елемент з останнім. Якщо при порівнянні останній елемент виявиться меншим за перший, то комп’ютер виконає перестановку цих двох елементів. Такі дії будуть відбуватися до тих пір, поки індикатор, якій відповідає за ліву частину послідовності (в нашій процедурі це “i”) не перейде на праву частину, а індикатор, що відповідає за праву частину масиву (в нашій процедурі це “j”) не перейде на праву частину. Далі та ж сама процедура викликається рекурсивно. Тобто, якщо ліва частина вже відсортована, то ми викликаємо ту саму процедуру і комп’ютер виконує ті самі дії, але в параметрах процедури ми змінюємо ліву границю. Те саме відбувається, коли відсортована права частина масиву.
По суті цей алгоритм працює на основі алгоритму сортування обмінами, але цей алгоритм вважається швидким, оскільки перегляд послідовності відбувається у двох напрямках одночасно. Реалізовано ж цей алгоритм за допомогою оператору “if”, який відповідає за порівняння елементів, та пересилань.
Завантажити реферат