7-8-ma’ruza. Saralashning sodda algoritmlari. Saralashning yaxshilangan algoritmlari (4 soat) Reja

Algoritm samaradorligi: 
taqqoslashlar soni M = 
n n
n
2 2
4
2
 
, 
almashtirishlar soni C
max
= 3
n
2
4
. 
 
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; 
Algoritm samaradorlig: 
O(n log n) – eng samarali usul. 
Shell saralashi (qisqarib boruvchi qadamlar orqali saralash) 

---

To’g’ri 
qo’shish 
usulini 
1959 
yilda 
D. 
Shell 
tomonidan 
mukammallashtirish taklif qilingan. Quyidagi chizmada ushbu usul tasvirlangan: 
Boshida bir biridan 4 qadamda joylashgan elementlar o’zaro guruhlanib 
saralash amalga oshiriladi. Bunday jarayon to’rtlik saralash deb ataladi. Birinchi 
o’tishdan keyin elementlar qayta guruhlanib, endi har ikki qadamdagi elementlar 
taqqoslanadi. Bu esa ikkilik saralash deb nomlanadi. Va nihoyat, uchinchi 
o’tishda oddiy yoki yakkalik saralashi amalga oshiriladi.
Bir qarashda mazkur usul bilan saralash amalga oshirilganda saralash 
jarayoni kamayish o’rniga ortib boradigandek tuyulsada, elementlarni o’rin 
almashtirishlar nisbatan kam amalga oshiriladi.
Ko’rinib turibdiki, bu usul natijasida tartiblangan massiv hosil bo’lib, har 
bir o’tishdan keyin saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni 
yakkalik saralash amalga oshiradi.
Baryer usulidan foydalanilganda har bir saralash o’zining baryeriga ega 
bo’lishi lozim hamda dastur uning joyini aniqlashi uchun uni iloji boricha 
osonlashtirish lozim. Shuning uchun massivni [-h1..N] gacha kengaytirish lozim 
bo’ladi. 
h[1..t] – qadamlar o’lchami massivi 
a[1..n] - saralanayotgan massiv 
k – saralash qadami 
x – qo’shilayotgan element qiymati