O’zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya texnologiyalari davlat qo’mitasi

“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;ii;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. Quiksort – tez saralash algoritmi

Bu algoritm “bo’lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo’lib, o„rtacha N*log₂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=,

6.3-rasm. Quicksort algoritmida o’rinlashtirish

3. 
   Chapdagi i-elementni key bilan solishtiramiz. Agar key kichik bo’lsa, keyingi qadamga o„tamiz. Aks holda i++ va shu qadamni takrorlaymiz.
   
4. 
   O’ngdagi j-element bilan key solishtiriladi. Agar key katta bo’lsa, keyingi qadamga o„tamiz, aks holda j-- va shu qadamni takrorlaymiz.
   
5.