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.
6.5. “Pufaksimon” usulni yaxshilash
1) Agar massivda o„tishlar
nafaqat yuqoridan pastga, balki bir vaqtning
116
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 )).
