Yra keli pagrindiniai masyvo rūšiavimo problemos sprendimo algoritmai. Vienas iš žinomiausių iš jų yra įterpimo rūšiavimas. Dėl savo aiškumo ir paprastumo, bet mažo efektyvumo šis metodas daugiausia naudojamas mokant programuoti. Tai leidžia suprasti pagrindinius rūšiavimo mechanizmus.
Algoritmo aprašymas
Įterpimo rūšiavimo algoritmo esmė yra ta, kad pradiniame masyve suformuojamas tinkamai sutvarkytas segmentas. Kiekvienas elementas po vieną lyginamas su patikrinta dalimi ir įterpiamas į reikiamą vietą. Taigi, pakartoję visus elementus, jie išsirikiuoja teisinga tvarka.
Elementų pasirinkimo tvarka gali būti bet kokia, juos galima pasirinkti savavališkai arba pagal tam tikrą algoritmą. Dažniausiai nuoseklus išvardijimas naudojamas nuo masyvo pradžios, kur formuojamas tvarkingas segmentas.
Rūšiavimo pradžia gali atrodyti taip:
- Paimkite pirmąjį masyvo elementą.
- Kadangi nėra su kuo lyginti, paimkite patį elementą kaip nurodytaseka.
- Eiti į antrą elementą.
- Palyginkite jį su pirmuoju pagal rūšiavimo taisyklę.
- Jei reikia, sukeiskite elementus vietomis.
- Paimkite pirmuosius du elementus kaip sutvarkytą seką.
- Eiti į trečią elementą.
- Palyginkite su antruoju, jei reikia, pakeiskite.
- Jei pakeitimas atliktas, palyginkite jį su pirmuoju.
- Paimkite tris elementus kaip sutvarkytą seką.
Ir taip iki pradinio masyvo pabaigos.
Realus įterpimo rūšiavimas
Dėl aiškumo verta pateikti pavyzdį, kaip šis rūšiavimo mechanizmas naudojamas kasdieniame gyvenime.
Paimkite, pavyzdžiui, piniginę. Šimto, penkių šimtų ir tūkstančio dolerių kupiūros guli netvarkoje banknotų skyriuje. Tai netvarka, tokiame maišelyje sunku iš karto rasti tinkamą popieriaus lapą. Banknotų masyvas turi būti surūšiuotas.
Pats pirmasis yra 1000 rublių banknotas, o iškart po jo - 100. Paimame šimtuką ir padedame priešais. Trečias iš eilės yra 500 rublių, jam tinkama vieta yra nuo šimto iki tūkstančio.
Panašiai rūšiuojame gautas kortas žaidžiant „Kvailys“, kad būtų lengviau jas naršyti.
Operatoriai ir pagalbinės funkcijos
Įterpimo rūšiavimo metodas kaip įvestis paima pradinį rūšiuojamą masyvą, palyginimo funkciją ir, jei reikia, funkciją, kuri nustato elementų surašymo taisyklę. Dažniausiai naudojamas vietojreguliaraus ciklo sakinys.
Pirmasis elementas pats savaime yra sutvarkytas rinkinys, todėl palyginimas pradedamas nuo antrojo.
Algoritmas dažnai naudoja pagalbinę funkciją, kad pakeistų dvi reikšmes (sukeisti). Jis naudoja papildomą laikinąjį kintamąjį, kuris eikvoja atmintį ir šiek tiek sulėtina kodą.
Alternatyva – masiškai perkelti elementų grupę ir į laisvą vietą įterpti esamą. Šiuo atveju perėjimas prie kito elemento įvyksta, kai palyginimas davė teigiamą rezultatą, o tai rodo teisingą tvarką.
Įdiegimo pavyzdžiai
Konkretus įgyvendinimas labai priklauso nuo naudojamos programavimo kalbos, jos sintaksės ir struktūrų.
Klasikinis C įgyvendinimas naudojant laikinąjį kintamąjį vertėms keistis:
int i, j, temp; for (i=1; i =0; j--) { if (masyvas[j] < temp) pertrauka; masyvas[j + 1]=masyvas[j]; masyvas[j]=temp; } }
PHP diegimas:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Čia pirmiausia visi elementai, kurie neatitinka rūšiavimo sąlygos, perkeliami į dešinę, o tada dabartinis elementas įterpiamas į laisvą vietą.
Java kodas naudojant while kilpą:
viešas statinis void įterpimas Rūšiuoti(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Bendra kodo reikšmė išlieka nepakitusi: kiekvienas masyvo elementas nuosekliai lyginamas su ankstesniais ir, jei reikia, sukeičiamas su jais.
Numatomas veikimo laikas
Akivaizdu, kad geriausiu atveju algoritmo įvestis bus masyvas, jau sutvarkytas tinkamu būdu. Esant tokiai situacijai, algoritmas tiesiog turės patikrinti kiekvieną elementą, kad įsitikintų, jog jis yra tinkamoje vietoje, neatlikdamas keitimų. Taigi veikimo laikas tiesiogiai priklausys nuo pradinio masyvo ilgio O(n).
Blogiausio atvejo įvestis yra masyvas, surūšiuotas atvirkštine tvarka. Tam reikės daugybės permutacijų, vykdymo trukmė priklausys nuo elementų skaičiaus kvadratu.
Tikslus visiškai netvarkingo masyvo permutacijų skaičius gali būti apskaičiuotas naudojant formulę:
n(n-1)/2
kur n yra pradinio masyvo ilgis. Taigi, norint sutvarkyti 100 elementų teisinga tvarka, prireiktų 4950 permutacijų.
Įterpimo metodas yra labai efektyvus rūšiuojant mažas arba iš dalies surūšiuotas matricas. Tačiau nerekomenduojama jį taikyti visur dėl didelio skaičiavimų sudėtingumo.
Algoritmas naudojamas kaip pagalbinė priemonė daugelyje kitų sudėtingesnių rūšiavimo metodų.
Rūšiuoti lygias reikšmes
Įterpimo algoritmas priklauso vadinamosioms stabilioms rūšims. Tai reiškia,kad nekeičiami identiški elementai, o išsaugoma jų pirminė tvarka. Stabilumo indeksas daugeliu atvejų yra svarbus teisingam užsakymui.
Aukščiau pateiktas puikus vaizdinis įterpimo rūšiavimo šokyje pavyzdys.
