Masivni saralash muammosini hal qilish uchun bir nechta asosiy algoritmlar mavjud. Ularning eng mashhurlaridan biri - qo'shish tartibi. Aniqligi va soddaligi, lekin samaradorligi pastligi tufayli bu usul asosan dasturlashni o'rgatishda qo'llaniladi. Bu sizga asosiy saralash mexanizmlarini tushunish imkonini beradi.
Algoritm tavsifi
Qoʻshishni tartiblash algoritmining mohiyati shundan iboratki, boshlangʻich massiv ichida toʻgʻri tartiblangan segment hosil boʻladi. Har bir element belgilangan qism bilan birma-bir taqqoslanadi va kerakli joyga kiritiladi. Shunday qilib, barcha elementlarni takrorlashdan keyin ular to'g'ri tartibda joylashadilar.
Elementlarni tanlash tartibi har qanday bo'lishi mumkin, ular o'zboshimchalik bilan yoki qandaydir algoritmga muvofiq tanlanishi mumkin. Ko'pincha ketma-ket ro'yxatga olish massiv boshidan qo'llaniladi, bu erda tartiblangan segment hosil bo'ladi.
Saralashning boshlanishi quyidagicha koʻrinishi mumkin:
- Masivning birinchi elementini oling.
- Uni solishtirish uchun hech narsa yo'qligi sababli, elementning o'zini buyurtma bo'yicha olingketma-ketlik.
- Ikkinchi elementga oʻting.
- Saralash qoidasi asosida uni birinchisi bilan solishtiring.
- Agar kerak boʻlsa, elementlarni joyiga almashtiring.
- Birinchi ikkita elementni tartiblangan ketma-ketlik sifatida oling.
- Uchinchi bandga oʻting.
- Uni ikkinchisi bilan solishtiring, kerak boʻlsa almashtiring.
- Agar almashtirilgan boʻlsa, uni birinchisi bilan solishtiring.
- Uch elementni tartiblangan ketma-ketlik sifatida oling.
Va shunga oʻxshash asl massiv oxirigacha.
Haqiqiy hayotda kiritish tartibi
Aniqlik uchun ushbu tartiblash mexanizmi kundalik hayotda qanday qoʻllanilishiga misol keltirish kerak.
Masalan, hamyonni olaylik. Yuz, besh yuz va ming dollarlik kupyuralar banknot bo'limida tartibsiz yotibdi. Bu tartibsizlik, bunday hodgepodgeda darhol kerakli qog'ozni topish qiyin. Banknotlar massivi saralanishi kerak.
Eng birinchisi 1000 rubllik banknot, undan keyin esa 100. Biz yuzni olib, uni oldiga joylashtiramiz. Ketma-ket uchinchisi - 500 rubl, buning uchun munosib joy - yuzdan minggacha.
Huddi shunday tarzda biz “Ahmoq” oʻynaganimizda qabul qilingan kartalarni saralab, ularni boshqarishni osonlashtiramiz.
Operatorlar va yordamchi funksiyalar
Qoʻshish saralash usuli kirish sifatida saralanadigan boshlangʻich massivni, taqqoslash funksiyasini va agar kerak boʻlsa, elementlarni sanash qoidasini aniqlaydigan funksiyani oladi. Buning o'rniga ko'pincha ishlatiladioddiy tsikl bayonoti.
Birinchi elementning oʻzi tartiblangan toʻplamdir, shuning uchun taqqoslash ikkinchidan boshlanadi.
Algoritm koʻpincha ikkita qiymatni almashish uchun yordamchi funksiyadan foydalanadi (almashtirish). U qoʻshimcha vaqtinchalik oʻzgaruvchidan foydalanadi, u xotirani sarflaydi va kodni biroz sekinlashtiradi.
Muqobil variant - elementlar guruhini ommaviy siljitish va keyin joriy elementni bo'sh joyga kiritish. Bunday holda, keyingi elementga o'tish taqqoslash ijobiy natija berganda sodir bo'ladi, bu to'g'ri tartibni ko'rsatadi.
Amalga misollar
Muayyan amalga oshirish koʻp jihatdan ishlatiladigan dasturlash tili, uning sintaksisi va tuzilmalariga bogʻliq.
Qiymatlarni almashish uchun vaqtinchalik oʻzgaruvchidan foydalangan holda Klassik C ilovasi:
int i, j, temp; uchun (i=1; i =0; j--) { if (massiv [j] < temp) tanaffus; massiv[j + 1]=massiv[j]; massiv[j]=temp; } }
PHP-ni joriy qilish:
insertion_sort(&$a) { uchun ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Bu yerda, avvalo, tartiblash shartiga mos kelmaydigan barcha elementlar oʻngga siljiydi, soʻngra joriy element boʻsh joyga kiritiladi.
while siklidan foydalanadigan Java kodi:
ommaviy statik bekor kiritishSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Kodning umumiy ma'nosi o'zgarishsiz qoladi: massivning har bir elementi ketma-ket avvalgilari bilan taqqoslanadi va agar kerak bo'lsa, ular bilan almashtiriladi.
Taxminiy ish vaqti
Shubhasiz, eng yaxshi holatda, algoritm kiritilishi allaqachon toʻgʻri tartiblangan massiv boʻladi. Bunday vaziyatda algoritm har bir elementni almashtirishsiz to'g'ri joyda ekanligiga ishonch hosil qilish uchun tekshirishi kerak bo'ladi. Shunday qilib, ish vaqti bevosita O(n) asl massiv uzunligiga bog'liq bo'ladi.
Eng yomon holatda kiritish teskari tartibda tartiblangan massivdir. Buning uchun koʻp miqdordagi almashtirishlar kerak boʻladi, ish vaqti funksiyasi elementlarning kvadratiga bogʻliq boʻladi.
Toʻliq tartibsiz massiv uchun almashtirishlarning aniq sonini quyidagi formula yordamida hisoblash mumkin:
n(n-1)/2
bu erda n - asl massivning uzunligi. Shunday qilib, 100 ta elementni toʻgʻri tartibda joylashtirish uchun 4950 ta almashtirish kerak boʻladi.
Qoʻshish usuli kichik yoki qisman tartiblangan massivlarni saralash uchun juda samarali. Biroq, hisob-kitoblarning murakkabligi tufayli uni hamma joyda qo'llash tavsiya etilmaydi.
Algoritm boshqa murakkabroq saralash usullarida yordamchi sifatida ishlatiladi.
Teng qiymatlarni saralash
Qoʻshish algoritmi barqaror deb ataladigan turlarga tegishli. Bu … bildiradi,u bir xil elementlarni almashtirmaydi, balki ularning asl tartibini saqlaydi. Barqarorlik indeksi ko'p hollarda to'g'ri tartiblash uchun muhim ahamiyatga ega.
Yuqoridagilar raqsga kiritishning ajoyib vizual namunasidir.
