|
Zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya
|
| bet | 43/47 | | Sana | 15.11.2023 | | Hajmi | 490,46 Kb. | | #99136 |
“Pufaksimon” usulni yaxshilash
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”.
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.
Oraliq sifatida 0 dan n-1 gacha bo„lgan massivning barcha elementlarini olamiz.
Oraliq o„rtasidagi kalit elementni tanlaymiz, ya‟ni
key=(+)/2, i=,
6.3-rasm. Quicksort algoritmida o„rinlashtirish
Chapdagi i-elementni key bilan solishtiramiz. Agar key kichik bo„lsa, keyingi qadamga o„tamiz. Aks holda i++ va shu qadamni takrorlaymiz.
O„ngdagi j-element bilan key solishtiriladi. Agar key katta bo„lsa, keyingi qadamga o„tamiz, aks holda j-- va shu qadamni takrorlaymiz.
|
| |
