Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів

Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів

Содержание

• 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 i:=L; j:=R; x:=a[i]; while j>i do begin while xi then begin a[i]:=a[j]; a[j]:=x; i:=i+1 end; while a[i]i then begin a[j]:=a[i]; a[i]:=x; j:=j-1 end end; k:=k+1; if R-i