Pufaksimon saralash algoritmi Ushbu usulning g„oyasi quyidagicha: n 1

951-20 guruhi talabasi Ablayeva Oygul

HISOBOT № 2
(6-7-8-9-10-laboratoriyalar)
6- Laboratoriya mashg’uloti. Saralashning yaxshilangan usullari va ularning qo‘llanilishi.


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 (6.1- rasm).
Misol : massiv - 4, 3, 7, 2, 1, 6.

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:


n n n²
M  

Almashtirishlar soni:

_n2 C_mzx3 ₄
“Pufaksimon” saralash usulini hisoblashga misol

2-rasm. Massivni pufaksimon saralashga misol

6.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.