Аналіз сортування

Cmin= 2(n-1) Mmin=0

Cср =1/2(n2+n-2)  Mср= 1/4(n2+9n-10)

Cmax =(n2+n)–1  Mmax= 1/2(n2+3n-4)

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

Алгоритм простими включеннями можна легко поліпшити, користуючись тим, що готова послідовність a1,..., ai-1, у яку потрібно включити новий елемент, вже упорядкована. Тому місце включення можна знайти швидким бінарним методом.

procedure binaryinsertion (var a: massiv);

var

i,j,l,r,m: integer;

x: integer;

n1,n: integer;

begin

n1:= low(a);

n:= high(a);

for i:= k+1 to n do

begin

x:=a[i];

  l:=k;

  r:=i-1;

while (l<=r) do

  begin

  m:=(l+r) div 2;

  if x<a[m] then r:=m-1 else l:=m+1;

end;

for j:=i-1 downto  l do a[j+1]:=a[j];

a[l]:=x;

end;

end

Аналіз: кількість порівнянь C стає порядку n log n. Однак, це поліпшення не є вирішальним. Більш важливий показник М залишається порядку n2.

Важлива властивість сортування включеннями: метод є стійким, тобто він залишає незмінним порядок елементів з однаковими ключами.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27 28  Наверх ↑