|
O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti
|
| bet | 78/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tAlgoritm samaradorligi:
Taqqoslashlar soni M = .
Almashtirishlar soni Cmin = 3(n - 1), Cmax = 3(n - 1)
(n2 tartib).
Ushbu usul bo’yicha saralash bajarilsa, eng yomon xolda taqqoslashlar va almashtirishlar soni tartibi n2 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.
Paskal tilidagi dasturi:
for i := 2 to n do
for j := n downto i do
if a[j - 1] > a[j] then
begin
x := a[j - 1];
a[j - 1] := a[j];
a[j] := x;
end;
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 Cmax = 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;
|
| |
