1-Labaratoriya mashg’uloti. Ma’lumotlarni saralash algoritmlarini tartibli statistikasi

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 (1- rasm).  

Misol : massiv - 4, 3, 7, 2, 1, 6.  

 

1-rasm. Pufaksimon saralash usulida massivelementlarining o’rnini almashtirish  

 

Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga 

o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.  

Taqqoslashlar soni:  

M=(n/2)(n/2)=n

2

/4 

Almashtirishlar soni:  

C

max

=3n

2

/4 

 

2-rasm. Massivni pufaksimon saralashga misol 

 

---

4 

 

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.