Texnalogiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot

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*log2N 
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=.
3-rasm. Quicksort algoritmida o’rinlashtirish
3. Chapdagi i-elementni 
key 
bilan solishtiramiz. Agar 
key 
kichik bo’lsa, keyingi qadamga 
o’tamiz. Aks holda