Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
; є повторюваним виконанням процедури Sift при зміні параметра L=Ndiv2, ..., 1 :
L:=N div 2 +1;
while L>1 do
begin
L:=L-1;
Sift(L, N)
end;
Для ілюстації алгоритму розглянемо попередній варіант масиву :
44 |
44 |
44 |
44 | 42
06
Тут жирним шрифтом виділені добавлювані до піраміди елементи; підкреслені - елементи, з якими проводився обмін.
Для того, щоб отримати не тільки часткове, а і повне впорядкування серед елементів послідовності, потрібно виконати N зсувних етапів. Після кожного проходу на вершину дерева виштовхуватиметься черговий найменший ключ. Знову виникає питання : де зберігати "спливаючі" верхні елементи і чи можна проводити перестановки "на тому ж місці"? Це легко реалізувати, якщо кожен раз брати останню компоненту піраміди - це буде просіюваний ключ x, ховати верхній елемент з попереднього етапу в звільнене позицію, а x зсувати на відповідне місце. Зрозуміло, що після кожного етапу розглядувана піраміда буде скорочуватися на один елемент справа. Таким чином, впорядкування масиву буде здійснено за N-1 прохід :
06 42 12 55 94 18 44 67обмін 67 і 06
67 42 12 55 94 18 44 | 06просіювання 67
12 42 18 55 94 67 44 | 06обмін 44 і 12
44 42 18 55 94 67 | 12 06просіювання 44
18 42 44 55 94 67 | 12 06обмін 67 і 18
67 42 44 55 94 | 18 12 06просіювання 67
42 55 44 67 94 | 18 12 06обмін 94 і 42
94 55 44 67 | 42 18 12 06просіювання 94
44 55 94 67 | 42 18 12 06обмін 67 і 44
67 55 94 | 44 42 18 12 06просіювання 67
55 67 94 | 44 42 18 12 06обмін 94 і 55
94 67 | 55 44 42 18 12 06просіювання 94
67 94 | 55 44 42 18 12 06обмін 94 і 67
94 | 67 55 44 42 18 12 06просіювання 94
94 | 67 55 44 42 18 12 06
Тут жирним шрифтом виділені просіювані по піраміді елементи; підкреслені - елементи, між якими проводився обмін.
Процес сортування описується за допомогою процедури Sift таким чином:
R:=N;
while R>1 do
begin
x:=a[1]; a[1]:=a[R]; a[R]:=x;
R:=R-1;
Sift(1, R)
end;
Як видно з прикладу, отриманий порядок ключів фактично є зворотнім. Це легко виправити, помінявши напрямок відношення порівняння в процедурі Sift на протилежний. Остаточно процедура сортування масиву методом Heap Sort матиме вигляд :
Procedure Heap_Sort;
Var
L, R : integer; x : basetype;
Procedure Sift(L, R : integer);
Var
i, j : integer; x : basetype;
Begin
i:=L; j:=2*L; x:=a[L];
if (j<R) and (a[j]<a[j+1]) then j:=j+1;
while (j<=R) and (x<a[j]) do
begin
a[i]:=a[j]; a[j]:=x; i:=j; j:=2*j;
if (j<R) and (a[j]<a[j+1]) then j:=j+1
end
End;
Begin
L:=N div 2 +1; R:=N;
while L>1 do
begin L:=L-1; Sift(L, N) end;
while R>1 do
begin
x:=a[1]; a[1]:=a[R]; a[R]:=x;
R:=R-1;
Sift(1, R)
end
End;
Аналіз алгоритму Heap Sort. Як вже раніше відмічалося, складність алгоритму по операціях порівняння є величиною порядку O(N*log(N)+N). Кількість переміщень елементів суттєво залежить від стартового розміщення ключів в послідовності.
Однак при початково-впорядкованому масиві не слід чекати максимальної ефективності. Адже обєм перестановок в цьому випадку є досить великим під час просіювання "важких" елементів після побудови піраміди. Фактично на кожному етапі такого просіювання виконується log(K) перестановок плюс ще N-1 обмін перед просіюванням, де K - кількість елементів в піраміді, в якій проводиться просіювання. Таким чином, в цьому випадку
.
Тому можна вважати, що розглядуваний метод як і по порівняннях так і по перестановках має ефективність порядку O(N*log(N)+N).
2.5 Порівняльна характеристика швидкодії деяких швидких алгоритмів сортування
Щоб порівняти швидкодію певних алгоритмів сортування, зокрема Quick_Sort, Heap_Sort, Shell_Sort, ми створили одновимірний масив із елементів n=50000, типу integer. При цьому розглядалися різні варіанти масиву А(n). А саме, коли вихідний масив А(n) вже є відсортований за зростанням (за спаданням), коли всі члени масиву А(n) рівні, а також, коли елементи масиву генеруються випадковим чином. За отриманими результатами ми подували таблицю, яка дає змогу проаналізувати дані, і виявити кращі алгоритми сортування у різних випадках.
№Алгоритм сортуванняСортування відсортованого масиву по зростанню (мс)Сортування по зростанню відсортованого масиву по спаданню (мс)Сортування масиву, всі елементи однакові (мс)Сортування масиву генерованого випадковим чином (мс)1Quick_Sort170001100014252Heap_Sort40408553Shell_Sort40504677
Висновки
Отже, ми розглянули як працюють швидкі алгоритми сортування іь спробували визначити їх складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба памятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
Так, алгоритм сортування деревом, хоча й працює однаково на всіх входах (так, що його складність в гіршому випадку співпадає зі складністю в середньому), але цей алгоритм має і досить суттєвий недолік: для нього потрібна додаткова память розміром 2n-1.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортува?/p>