Pufaksimonsaralashalgoritmi
Ushbuusulningg„oyasiquyidagicha: n - 1 martamassivdaquyidanyuqorigaqarabyuribkalitlarjufti-juftibilantaqqoslanadi. Agar pastkikalitqiymatiyuqoridagijuftikalitidankichikbo„lsa, u holdaularningo„rnialmashtiriladi (1- rasm).
Misol :massiv - 4, 3, 7, 2, 1, 6.
1-rasm. Pufaksimonsaralashusulidamassivelementlariningo„rninialmashtirish
Pufaksimonusulnimassivelementlaridapastdanyuqorigavayuqoridanpastgao„tishnibirvaqtdaamalgaoshirishnatijasidayaxshilashmumkin.
Taqqoslashlarsoni:
M=(n/2)(n/2)=n2/4
Almashtirishlarsoni:
Cmax=3n2/4
2-rasm. Massivnipufaksimonsaralashgamisol
2-rasmda berilganmisolda 5 ta elementdaniboratmassivberilgan. Demak, massivdapastdanyuqoriga (yuqoridanpastga) o„tishlarsoni 5-1=4 martabo„ladi. Misoldanko„rinibturibdiki, algoritmichkisiklda 3-qadamdan boshlabmassivni “bekor” qaytaishlaydi, 4-qadamni bajarmasa ham bo„ladi.
Berilganusullarningafzalligi:
1) Engsoddaalgoritm;
2) Amalga oshirishsodda;
3) Qo„shimchao„zgaruvchilarshartemas.
Kamchiliklari:
1) Kattamassivlarniuzoqqaytaishlaydi;
2) Har qanday holatda ham o„tishlar soni kamaymaydi.
“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’rinlashtirishvataqqoslashlarsoni: (n* log( n )).
Quiksort – tezsaralashalgoritmi
Bu algoritm “bo„libolvaegalikqil” tamoyiliningyaqqolmisolidir. Bu algotirmrekursivbo„lib, o„rtachaN*log2N ta solishtirishnatijasidasaralaydi. Algoritmberilganmassivnisaralashuchununi 2 tagabo„liboladi. Bo„libolishuchunixtiyoriyelementnitanlabundan 2 ta qismgaajratiladi. 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 algoritmidao„rinlashtirish
3. Chapdagii-elementnikey bilansolishtiramiz. Agar key kichikbo„lsa, keyingiqadamgao„tamiz. Aksholdai++ vashuqadamnitakrorlaymiz.
4. O„ngdagij-element bilankey solishtiriladi. Agar key kattabo„lsa, keyingiqadamgao„tamiz, aksholdaj-- vashuqadamnitakrorlaymiz.
5. i- vaj-elementlarningo„rnialmashtiriladi. Agar i<=j bo„lsa, 3-qadamga o„tiladi.
Birinchio„tishdankeyintanlangan element o„ziningjoyigakelibjoylashadi.
6. Endishuko„rilayotganoraliqdakey kalitning chap tomonidaelementlarmavjudbo„lsa, ularustidayuqoridagiamallarnibajarishlozim, ya‟niko„riladiganoraliq0 dankey-1 gacha deb belgilanadiva 2-qadamga o„tiladi. Aksholdakeyingiqadamgao„tiladi.
7. Endishuko„rilayotganoraliqdakey kalitningo„ngtomonidaelementlarmavjudbo„lsa, ularustidayuqoridagiamallarnibajarishlozim, ya‟niko„riladiganoraliqkey+1 dann-1 gacha deb belgilanadiva 2-qadamga o„tiladi. Aksholdaalgoritmtugaydi.
Shu algoritmgamisolko„ribchiqamiz.
Misol: Talabalar ism-sharifivatartibraqamidaniboratjadvalni quicksort algoritmibilansaralangvanechtao„rinlashtirishamalgaoshirilganinianiqlang.
Do'stlaringiz bilan baham: |