Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів
1, 3, 7, 15, 31, ... , де h i-1 =2 h i +1 , h t =1 , t=[ log 2 N]-1 .
З обчислювальної практики відомо, що загалом метод Шелла має ефективність порядку O(N1,2 ).
2.2 Сортування обміном на великих відстанях – алгоритм Quick Sort
Основна причина повільної роботи алгоритму прямого обміну полягає в тому, що всі порівняння і перестановки елементів в послідовності a 1 , a 2 , ..., a N відбуваються для пар із сусідніх елементів. При такому способі потрібно відносно більше часу, щоб поставити деякий ключ, який знаходиться не на своєму місці, в потрібну позицію у сортованій послідовності. Природньо попробувати пришвидшити цей процес, порівнюючи пари елементів, що знаходяться далеко один від одного в масиві. К. Хоор розробив алгоритм Quick Sort із середнім часом роботи порядку O(N*lnN).
Припустимо, що перший елемент масиву, що сортується, є хорошим наближенням елемента, який вкінці опиниться на своєму місці у відсортованій послідовності. Приймемо його значення в якості ведучого елемента, відносно якого ключі будуть мінятися місцями. Для зручності реалізації алгоритму використаємо два вказівники I, J , перший з яких вестиме відлік вздовж розглядуваної частини масиву зліва, а другий - справа. Початково їх значення будуть відповідно I=1, J=N . Таким чином ведучим елементом буде значення a[I] . Перестановки ключів проводяться за такими принципами :
1) порівнюються елементи a[I] та a[J] ; якщо a[I] £a[J] , то здійснюється крок вліво J:=J-1 і порівняння повторюється; зменшення J продовжується доти, поки не виконається умова a[I]> a[J] ;
2) якщо при порівнянні елементів досягнута умова a[I]> a[J] , то проводиться обмін місцями кючів a[I] та a[J] і здійснюється крок вправо I:=I+1 ; таким чином ведучий елемент перейшов в позицію J ; порівняння ключів із збільшенням I продовжується доти, поки знову не виконається умова a[I]> a[J] ;
3) у випадку виконання умови a[I]> a[J] проводиться обмін місцями кючів a[I] та a[J] і здійснюється крок вліво J:=J-1 ; при цьому ведучий елемент знову повертається в позицію I .
Цей процес із почерговим зменшенням J та збільшенням I повторюється з обох кінців послідовності до "середини"до тих пір, поки не досягнеться I=J .
Тепер мають місце два факти. По-перше, ключ, що був першим у вихідній послідовності, в результаті такого впорядкування опиняється на "своєму" місці. По-друге, всі елементи зліва будуть меншими за нього, а всі ключі справа - більшими.
Ту ж саму процедуру можна використати для впорядкування лівої і правої підпослідовностей і т. д. до повного сортування всьго масиву. Таким чином розглянутий алгоритм має чітко виражений рекурсивний характер. Виходячи з цього, значення індексів крайніх елементів меншої з двох невідсортованих підпослідовностей варто помістити в стекову структуру даних, і приступити до впорядкування більшої підпослідовності.
Оскільки короткі послідовності скоріше сортуються при допомозі прямих методів, то алгоритм Quick Sort матиме вхідний параметр - деяке число S , що визначає нижню межу його використання. Провівши нескладний математичний аналіз нерівності, яка пов’язує ефективності алгоритму Quick Sort та прямих алгоритмів сортування
,
можна встановити значення числа S , яке буде нижньою межею використання швидкого сортування. Остання нерівність дає результат 
.
Однак, якщо крім основних операцій порівняння ключів ще враховувати порівняння індексів та перестановки елементів, то це значення можна збільшити в 2-3 рази.
В якості прикладу наводиться програмна реалізація цього алгоритму у вигляд процедури Quick_Sort . В ній використовується два масиви left і right , де зберігатимуться індексні номери відповідно лівої і правої границь підпослідовностей, які ще будуть впорядковуватися на наступних етапах.
Procedure Quick_Sort;
Const S=20;
Var
k, L, R, i, j : integer;
x : basetype;
left, right : array [1..N] of integer;
Begin
k:=1; left[k]:=1; right[k]:=N;
while k>0 do
begin
L:=left[k]; R:=right[k]; k:=k-1;
while R-L>S do
begin