Matriisin lajitteluongelman ratkaisemiseen on useita perusalgoritmeja. Yksi tunnetuimmista niistä on lisäyslajittelu. Selkeyden ja yksinkertaisuuden, mutta alhaisen tehokkuuden vuoksi tätä menetelmää käytetään pääasiassa ohjelmoinnin opetuksessa. Sen avulla voit ymmärtää lajittelun perusmekanismit.
Algoritmin kuvaus
Lisäyslajittelualgoritmin ydin on, että alkutaulukon sisään muodostetaan oikein järjestetty segmentti. Jokaista elementtiä verrataan yksitellen tarkistettuun osaan ja lisätään oikeaan paikkaan. Siten kaikkien elementtien iteroinnin jälkeen ne asettuvat oikeaan järjestykseen.
Elementtien valintajärjestys voi olla mikä tahansa, ne voidaan valita mieliv altaisesti tai jonkin algoritmin mukaan. Useimmiten peräkkäistä numerointia käytetään taulukon alusta, jossa muodostetaan järjestetty segmentti.
Lajittelun alku saattaa näyttää tältä:
- Ota taulukon ensimmäinen elementti.
- Koska sitä ei voi verrata mihinkään, ota itse elementti tilauksen mukaanjärjestys.
- Siirry toiseen kohtaan.
- Vertaa sitä ensimmäiseen lajittelusäännön perusteella.
- Vaihda elementtejä tarvittaessa paikoin.
- Ota kaksi ensimmäistä elementtiä järjestetyksi sekvenssiksi.
- Siirry kolmanteen kohteeseen.
- Vertaa sitä toiseen, vaihda tarvittaessa.
- Jos vaihto tehdään, vertaa sitä ensimmäiseen.
- Ota kolme elementtiä järjestetyksi sekvenssiksi.
Ja niin edelleen alkuperäisen taulukon loppuun asti.
Tosielämän lisäyslajittelu
Selvyyden vuoksi kannattaa antaa esimerkki siitä, kuinka tätä lajittelumekanismia käytetään jokapäiväisessä elämässä.
Otetaan esimerkiksi lompakko. Sadan, viidensadan ja tuhannen dollarin seteleitä makaavat setelilokerossa sekaisin. Tämä on sotku, tällaisessa hodgepodgessa on vaikea löytää heti oikeaa paperia. Setelijoukko on lajiteltava.
Ensimmäinen on 1000 ruplan seteli ja heti sen jälkeen 100. Otamme sata ja asetamme sen eteen. Kolmas peräkkäin on 500 ruplaa, oikea paikka sille sadasta tuhanteen.
Samalla tavalla lajittelemme vastaanotetut kortit pelattaessa "Fool" -peliä helpottaaksemme niiden navigoimista.
Operaattorit ja aputoiminnot
Lisäyslajittelumenetelmä ottaa syötteenä lajiteltavan alustavan taulukon, vertailufunktion ja tarvittaessa funktion, joka määrittää elementtien luettelointisäännön. Useimmiten käytetty sen sijaantavallinen silmukkalause.
Ensimmäinen elementti on itse järjestetty joukko, joten vertailu alkaa toisesta.
Algoritmi käyttää usein aputoimintoa kahden arvon vaihtamiseen (vaihto). Se käyttää ylimääräistä väliaikaismuuttujaa, joka kuluttaa muistia ja hidastaa koodia hieman.
Vaihtoehtona on massasiirtää elementtiryhmää ja lisätä sitten nykyinen vapaaseen tilaan. Tässä tapauksessa siirtyminen seuraavaan elementtiin tapahtuu, kun vertailu antoi positiivisen tuloksen, mikä osoittaa oikean järjestyksen.
Toteutusesimerkkejä
Erityinen toteutus riippuu pitkälti käytetystä ohjelmointikielestä, sen syntaksista ja rakenteista.
Klassinen C-toteutus väliaikaismuuttujan avulla arvojen vaihtamiseen:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; taulukko[j + 1]=taulukko[j]; taulukko[j]=lämpötila; } }
PHP-toteutus:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Tässä ensin kaikki elementit, jotka eivät vastaa lajitteluehtoa, siirretään oikealle, ja sitten nykyinen elementti lisätään vapaaseen tilaan.
Java-koodi käyttäen while-silmukkaa:
julkinen staattinen void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[edellinenKey+1]=arr[edellinenAvain]; arr[edellinenKey]=currElem; prevKey--; } } }
Koodin yleinen merkitys säilyy ennallaan: taulukon jokaista elementtiä verrataan peräkkäin aikaisempiin ja vaihdetaan niiden kanssa tarvittaessa.
Arvioitu käyttöaika
Ilmeisesti, parhaassa tapauksessa algoritmin syötteenä on jo oikealla tavalla järjestetty taulukko. Tässä tilanteessa algoritmin on yksinkertaisesti tarkistettava jokainen elementti varmistaakseen, että se on oikeassa paikassa ilman vaihtoja. Siten ajoaika riippuu suoraan alkuperäisen taulukon pituudesta O(n).
Pahimmassa tapauksessa syöte on matriisi, joka on lajiteltu käänteiseen järjestykseen. Tämä vaatii suuren määrän permutaatioita, ajonaikainen funktio riippuu elementtien lukumäärästä neliössä.
Täysin järjestämättömän taulukon permutaatioiden tarkka määrä voidaan laskea kaavalla:
n(n-1)/2
jossa n on alkuperäisen taulukon pituus. Näin ollen 100 elementin järjestäminen oikeaan järjestykseen vaatisi 4950 permutaatiota.
Lisäysmenetelmä on erittäin tehokas pienten tai osittain lajiteltujen taulukoiden lajittelussa. Sitä ei kuitenkaan suositella käyttämään kaikkialla laskelmien monimutkaisuuden vuoksi.
Algoritmia käytetään apuvälineenä monissa muissa monimutkaisemmissa lajittelumenetelmissä.
Lajittele yhtä suuret arvot
Lisäysalgoritmi kuuluu niin kutsuttuihin stabiileihin lajikkeisiin. Se tarkoittaa,että se ei vaihda identtisiä elementtejä, vaan säilyttää niiden alkuperäisen järjestyksen. Vakausindeksi on monissa tapauksissa tärkeä oikean järjestyksen kann alta.
Yllä oleva on loistava visuaalinen esimerkki lisäyslajittelusta tanssissa.
