Samarqand davlat universiteti raqamli texnologiyalar fakulteti optimal boshqaruv usullari kafedrasi

key=(+)/2, i=,
j=.

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. i- va j-elementlarning o'rni almashtiriladi. Agar i<=j bo'lsa, 3-qadamga o'tiladi.
Birinchi o'tishdan keyin tanlangan element o'zining joyiga kelib joylashadi.
6. Endi shu ko'rilayotgan oraliqda key kalitning chap tomonida elementlar mavjud bo'lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya'ni ko'riladigan oraliq 0 dan key-1 gacha deb belgilanadi va 2-qadamga o'tiladi. Aks holda keyingi qadamga o'tiladi.
7. Endi shu ko'rilayotgan oraliqda key kalitning o'ng tomonida elementlar mavjud bo'lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya'ni ko'riladigan oraliq key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o'tiladi. Aks holda algoritm tugaydi.
Shu algoritmga misol ko'rib chiqamiz.
Misol: Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort algoritmi bilan saralang va nechta o'rinlashtirish amalga oshirilganini aniqlang.
Ishni bajarishga namuna
Masalaning qo'yilishi – tabalarning ism, familiyalarini optimallashtirilgan pufaksimon usuli bilan tartibga keltirish dasturini tuzamiz va saralash nechta o'rin almashtirish bilan amalga oshirilganini aniqlaymiz.
Algoritm
1. Jadvalga talabalar ism-sharifini kiritamiz.
2. Jadvaldagi 1-elementni olamiz, i=0.
3. Jadvaldagi n-1 oxirgi elementdan to i-elementgacha barcha elementni FIO maydonini o'zidan oldin turgan element FIO maydoni bilan solishtiramiz. Agar zarur bo'lsa, o'rin almashtiramiz va o'rin almashtirishlar hisoblagichi l ning qiymatini bittaga oshiramiz, ya'ni l++.
4. Agar ibo'lsa, i++ va 3-qadamga o'tamiz.
5. Natijaviy saralangan massivni ekranga chiqaramiz.
Akademik liseylar, kasb-hunar kollejlari va umumta’lim maktablari o’quvchilarining umumta’lim fanlari bo’yicha Respublika olimpiadalarini o’tkazish va xalqaro fan olimpiadalari ishtirokchilarini tanlash to’g’risida