3-amaliy mashg‟ulot Mavzu: Saralash usullarini tadqiq qilish. Ishdan maqsad

3.4. Pufaksimon saralash algoritmi 
Ushbu usulning 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 ularning o„rni almashtiriladi (3.1-
rasm). 
Misol : massiv - 4, 3, 7, 2, 1, 6. 
3.1-rasm. Pufaksimon saralash usulida massiv elementlarining o„rnini almashtirish 
Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan 
pastga o„tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin. 
Taqqoslashlar soni: 
4
2
2
2
n
n
n
M



Almashtirishlar soni: 
4
3
2
n
C
mzx


“Pufaksimon” saralash usulini hisoblashga misol 
3.2-rasm. Massivni pufaksimon saralashga misol 

---

3.2-rasmda berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, 
massivda pastdan yuqoriga (yuqoridan pastga) o„tishlar soni 5-1=4 marta bo„ladi. 
Misoldan ko„rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni 
“bekor” qayta ishlaydi, 4-qadamni bajarmasa ham bo„ladi. 
Berilgan usullarning afzalligi: 
1) Eng sodda algoritm; 
2) Amalga oshirish sodda; 
3) Qo„shimcha o„zgaruvchilar shart emas. 
Kamchiliklari: 
1) Katta massivlarni uzoq qayta ishlaydi; 
2) Har qanday holatda ham o„tishlar soni kamaymaydi. 
3.5. “Pufaksimon” usulni yaxshilash 
1) Agar massivda o„tishlar nafaqat yuqoridan pastga, balki bir vaqtning
o„zida pastdan yuqoriga ham bo„lsa, u holda “yengil” elementlar “yuqoriga suzib” 
chiqadi va “og„ir” elementlar esa “cho„kadi”. 
2) Massivda “bekor” o„tishni yo„q qilish uchun, tashqi siklda 
massiv saralanganligini tekshiruvchi belgi qo„yish lozim. 
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; 
} 
O„rinlashtirish va taqqoslashlar soni: (n* log( n )).