“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

114 
a[i]= k; 
}
Algoritm samaradorligi: 

Taqqoslashlar soni 
2
)
1
(
2
2
N
N
N
N
C






Massiv tartiblanganda o„rinlashtirishlar soni 
)
1
(
3
min



N
M

Massiv teskari tartiblanganda o„rinlashtirishlar soni 
2
)
1
(
3
2
min
max
N
N
N
M
M






Ushbu usul bo„yicha saralash bajarilsa, eng yomon holda taqqoslashlar va 
o„rinlashtirishlar soni tartibi n
2
bo„ladi. 
6.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 (6.1-
rasm). 
Misol : 
massiv - 4, 3, 7, 2, 1, 6. 
6.1-rasm. Pufaksimon saralash usulida massiv
elementlarining o„rnini almashtirish 
Pufaksimon 
usulni 
massiv elementlarida pastdan yuqoriga va 

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

Download 1,33 Mb.