6-ma’ruza. Saralash turlari va algoitmlar samardorligi. Saralashning qat’iy va yaxshilangan usullari. Reja

Algoritm samaradorligi:
Taqqoslashlar soni M = .
Almashtirishlar soni C_min = 3(n - 1), C_max = 3(n - 1)
(n² tartib).
Ushbu usul bo’yicha saralash bajarilsa, eng yomon xolda taqqoslashlar va almashtirishlar soni tartibi n² bo’ladi.
To’g’ridan-to’g’ri almashtirish usuli bilan saralash (pufaksimon). Ushbu usulni g’oyasi quyidagicha: n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo’lsa, u holda ular o’rni almashtiriladi.

C++ tilidagi dasturi:
for (int i=0;i
for (int j=n-1;j>i;j--)
if (a[j] < a[j - 1]){
int x= a[j - 1];
a[j - 1] = a[j];
a[j] = x;
}
Bizning xolatda bitta o’tish “bekor” bo’ldi. Elementlarni ortiqcha o’rinlashtirmaslik uchun bayroqcha kiritish mumkin.
Pufaksimon usulni yaxshilangan usuli bu sheyker saralash usuli bo’lib, har bir o’tishdan keyin sikl ichida yo’nalish o’zgartiriladi.
Algoritm samaradorligi:
taqqoslashlar soni M = ,
almashtirishlar soni C_max = 3 .
Saralashning yaxshilangan usullari
Quiksort – tez saralash usuli
G’oyasi: Bu usul almashtirish usulidagi saralashga tegishli bo’lib uning asosini kalitlarni tanlangan kalitga nisbatan ajratish tashkil qiladi.

6 dan chap tomonda kalitlari kichik, o’ng tomonda esa kalitlari 6 dan katta bo’lgan elementlar joylashadi (yuqoridagi chizma).
procedure Sort (L, R: integer);
begin
i := L;
j := r;
x := a[(L + r) div 2];
repeat
while a[i] < x do
i := i + 1;
while a[j] > x do
j := j - 1;
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
i := i + 1;
j := j - 1
end;
until i > j;
if L < j then sort (L, j);
if i < r then sort (i, r);
end;


procedure QuickSort;
begin
sort (1, n);
end;