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

while x<a[j-1] do

begin

a[j]:=a[j-1];

j:=j-1

end;

a[j]:=x

end

End;

Використаннядодатковогоелементавмасиві - "бар’єра" a[0]=x забезпечуєгарантованеприпиненняпроцесупросіювання. Цедозволяєзменшитикількістьлогічнихумоввзаголовкуциклаwhile дооднієї, акількістьлогічнихопераційвід2i-1 доi накожномуетапі. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індекса. На жаль, таке покращення ефективності по кількості порівнянь не зменшує об’єму перестановок елементів.

Аналіз прямого включення. Кількість порівнянь ключів C_i при i -ому просіюванні найбільше дорівнює i , найменше - 1 , а середньоймовірна кількість - i/2 . Кількість же перестановок (переприсвоєнь ключів), включаючи бар’єр, M_i =C_i +2 . Тому для оцінки ефективності алгоритму у випадках початково впорядкованого, зворотньо впорядкованого та довільного масиву можна скористатися наступними співвідношеннями:

; ;

;

;

;

.

Очевидно, що розглянутий алгоритм описує процес стійкого сортування.

1.2 Сортування бінарним включенням

Алгоритм прямого включення можна значно покращити, якщо врахувати, що "готова" послідовність є вже впорядкованою. Тому можна скористатися бінарним пошуком точки включення в "готову" послідовність. Програмна реалізація такого модифікованого методу включення матиме вигляд процедури:

Procedure Binary_Insertion;

Var

i, j, m, L, R : integer; x : basetype;

Begin

for i:=2 to N do

begin

x:=a[i]; L:=1; R:=i;

while L<R do

begin

m:=(L+R) div 2;

if a[m]<=x then L:=m+1 else R:=m