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 )).
6.6.
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
