“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--) 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 )). Quiksort – tez saralash algoritmi Bu algoritm “bo’lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu
algotirm rekursiv bo’lib, o’rtacha
N*log 2 N ta solishtirish natijasida saralaydi.
Algoritm berilgan massivni saralash uchun uni 2 taga bo’lib oladi. Bo’lib olish
uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi. Lekin o’rtadagi
elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma
‟
qul. Tanlangan kalit
elementga nisbatan chapdagi va o’ngdagi har bir element solishtiriladi. Kalit
elementdan kichiklar chapga, kattalar o’ng tomonga o’tkaziladi (6.3-rasm). Endi
massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya
‟
ni bu
oraliqlarning o’rtasidagi elementlar kalit sifatida olinadi va h.k.
Misol uchun rasmdagi massivni saralash algoritmini ko’rib chiqamiz.
1. Oraliq sifatida
0 dan
n-1 gacha bo’lgan massivning barcha elementlarini olamiz.
2. Oraliq o’rtasidagi kalit elementni tanlaymiz, ya
‟
ni
key=(+)/2, i=,
j=.
