Tanlash orqali saralash algoritmi
Mazkur usul quyidagi tamoyillarga asoslangan:
1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element birinchi element bilan o’rin almashinadi.
3. Keyin mazkur jarayon qolgan
n-1, n-2 elementlar bilan takrorlanib, to bitta
eng “katta” element qolguncha davom ettiriladi.
for(int i=0;i
for(int j=i+1;j
if (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}
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.
Misol : massiv - 4, 3, 7, 2, 1, 6.
Pufaksimon usulni massiv elementlarida pastdan
yuqoriga va yuqoridan
pastga o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.
Taqqoslashlar soni:
Almashtirishlar soni:
“Pufaksimon” saralash usulini hisoblashga misol
Massivni pufaksimon saralashga misol
Massivni pufaksimon saralashga misoldagi 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
“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--)
