Avainero – lisäyslajittelu vs valintalajittelu
Lisäyslajittelu ja valintalajittelu ovat kaksi lajittelualgoritmia, joita käytetään tietokokoelman lajitteluun. Joskus on tarpeen järjestää tiedot tiettyyn järjestykseen. Lajittelualgoritmit ovat mekanismeja datajoukon lajitteluun. Lajittelussa tiedot järjestetään numeeriseen tai leksikografiseen järjestykseen. Jos tiedot on lajiteltu oikein, tietojen hakeminen olisi helppoa nopeammin. Jos puhelinluettelon puhelinnumerot eivät ole lajiteltuina, on vaikea löytää tiettyä puhelinnumeroa. Samoin jos sanakirjassa olevia sanoja ei ole järjestetty aakkosjärjestykseen, sanojen löytäminen olisi erittäin vaikeaa. Siksi lajittelusta on hyötyä jokapäiväisessä elämässä. Tietojenkäsittelytieteessä on lajittelualgoritmeja datakokoelman lajittelemiseksi. Kaksi tällaista algoritmia ovat lisäyslajittelu ja valintalajittelu. Lisäyslajittelu on lajittelualgoritmi, joka lajittelee taulukon siirtämällä elementtejä yksitellen. Valintalajittelu on lajittelualgoritmi, joka löytää taulukon pienimmän elementin ja vaihtaa elementin ensimmäiseen paikkaan, löytää sitten toiseksi pienimmän elementin ja vaihtaa sen toisessa asemassa olevaan elementtiin ja jatkaa prosessia, kunnes koko taulukko on lajiteltu.. Keskeinen ero lisäyslajittelun ja valintalajittelun välillä on se, että lisäyslajittelu vertaa kahta elementtiä kerrallaan, kun taas valintalajittelu valitsee vähimmäiselementin koko taulukosta ja lajittelee sen.
Mikä on lisäyslajittelu?
Lisäyslajittelu on paikallaan oleva vertailupohjainen lajittelualgoritmi. Tässä menetelmässä taulukkoa etsitään askel askeleelta. Lajittelemattomat kohteet siirretään ja lisätään taulukon lajiteltuun aliluetteloon. Lisäyslajittelualgoritmi voidaan selittää seuraavan esimerkin avulla.
Ota esimerkiksi alkutaulukko 77, 33, 44, 11, 88. Tässä lajittelualgoritmissa ensimmäinen askel on valita nykyinen elementti.
Nykyinen elementti on 77. Nykyistä elementtiä verrataan kaikkiin vasemman reunan elementteihin. 77 on ensimmäinen elementti, eikä vasemmalla puolella ole elementtejä. Nykyisen sijainnin indeksi on 0.
Sitten nykyisen sijainnin indeksiä kasvatetaan 1:llä. Nyt indeksi on 1 ja nykyinen elementti on 33. Kun sitä verrataan vasemmalla olevaan elementtiin, se on pienempi kuin 77. Silloin molemmat arvot vaihdetaan. Nyt 33 on indeksissä 0 ja 77 on indeksissä 1.
Nyt taulukko on 33, 77, 44, 11, 88.
Jälleen indeksiä kasvatetaan. Indeksi on 2 ja nykyinen elementti on 44. Sitä verrataan vasemman puolen elementteihin. 44 on pienempi kuin 77. Joten nämä kaksi arvoa vaihdetaan. Nyt taulukko on 33, 44, 77, 11, 88. Kaikkia elementtejä on verrattava vasemmalla. Joten 44:ää verrataan 33:een. 33 on pienempi kuin 44. Näitä elementtejä ei siis tarvitse vaihtaa.
Nyt taulukko on 33, 44, 77, 11, 88.
Jälleen indeksiä kasvatetaan. Indeksi on 3 ja nykyinen elementti on 11. Sitä verrataan kaikkiin vasemmalla oleviin elementteihin. 11 on pienempi kuin 77, joten nämä kaksi vaihdetaan. Nyt matriisi on 33, 44, 11, 77, 88. Verrattaessa lukuja 11 ja 44, 11 on pienempi kuin 44. Joten nämä kaksi vaihdetaan. Nyt taulukot ovat 33, 11, 44, 77, 88. Taas 11 verrataan 33:een. 11 on pienempi kuin 33, joten nämä kaksi arvoa vaihdetaan.
Nyt taulukko on 11, 33, 44, 77, 88.
Indeksin kasvattaminen tekee indeksistä 4. Arvo on 88. Se on suurempi kuin 77. Joten vaihtamista ei tarvitse tehdä. Lopuksi lajiteltu matriisi on 11, 33, 44, 77, 88.
Kuva 01: Esimerkki lisäyksen lajittelusta
Lisäyslajittelu toteutetaan kuten yllä. Alkuperäinen taulukko oli 77, 33, 44, 11, 88. Lajittelun jälkeen se antaa tulostuksen 11, 33, 44, 77, 88.
Mikä on valintalajittelu?
Valintalajittelu on vertailupohjainen lajittelualgoritmi. Taulukot on jaettu osiin. Lajiteltu osa on vasemmassa päässä. Lajittelematon osa on oikeassa päässä. Ensin on löydettävä pienin arvo. Sitten se vaihdetaan vasemman elementin kanssa. Nyt tämä elementti on lajitetussa taulukossa. Tämä prosessi jatkaa lajittelemattoman taulukon rajan siirtämistä yhdestä elementistä oikealle. Valinnan lajittelualgoritmi voidaan selittää seuraavan esimerkin avulla.
Otetaan esimerkiksi alkutaulukko 77, 33, 44, 11, 88, 22. Tässä lajittelualgoritmissa löytyy taulukon pienin. Pienin elementti on 11. Se vaihdetaan taulukon 0-indeksin elementtiin.
Nyt taulukko on 11, 33, 44, 77, 88, 22.
Pienin elementti on indeksissä 0, joten 11 on nyt lajiteltu. Muista elementeistä pienin on 22. Se vaihdetaan indeksielementillä 1st.
Nyt taulukko on 11, 22, 44, 77, 88, 33.
Elementit 11 ja 22 on jo lajiteltu. Muista, pienin arvo on 33. Se vaihdetaan indeksielementillä 2nd.
Nyt taulukko on 11, 22, 33, 77, 88, 44.
Elementit 11, 22 ja 33 on jo lajiteltu. Muista, pienin arvo on 44. Se vaihdetaan indeksielementillä 3rd.
Nyt taulukko on 11, 22, 33, 44, 88, 66.
Elementit 11, 22, 33, 44 on jo lajiteltu. Loput elementit ovat 88 ja 66. Elementti 66 vaihdetaan indeksielementillä 4th.
Nyt taulukko on 11, 22, 33, 44, 66, 88.
Se on lajiteltu matriisi valintalajittelualgoritmin avulla.
Kuva 02: Valintalajitteluesimerkki
Lisäyslajittelu toteutetaan kuten yllä. Alkuperäinen taulukko oli 77, 33, 44, 11, 88. Lajittelun jälkeen se antaa tulostuksen 11, 33, 44, 77, 88.
Mikä on samank altaisuus lisäyslajittelun ja valintalajittelun välillä?
Sekä lisäyslajittelu että valintalajittelu ovat lajittelualgoritmeja
Mitä eroa lisäyslajittelulla ja valintalajittelulla on?
Lisäyslajittelu vs valintalajittelu |
|
| Lisäyslajittelu on lajittelualgoritmi, joka lajittelee taulukon siirtämällä elementtejä yksitellen. | Valintalajittelu on lajittelualgoritmi, joka löytää taulukon pienimmän elementin ja vaihtaa elementin ensimmäiseen sijaintiin, löytää sitten toiseksi pienimmän elementin ja vaihtaa sen toisessa asemassa olevaan elementtiin ja jatkaa prosessia, kunnes koko joukko on lajiteltu. |
| Prosessi | |
| Lisäyslajittelu on aliluettelon lajittelu vertaamalla kahta elementtiä, kunnes koko taulukko on lajiteltu. | Valintalajittelu valitsee minimielementin ja vaihtaa sen ensimmäiseen paikkaan, valitse uudelleen minimielementti lopuille ja vaihda se toiseen kohtaan ja jatkaa tätä prosessia loppuun asti. |
| Vakaus | |
| Lisäyslajittelu on vakaa lajittelualgoritmi. | Valinnan lajittelu ei ole vakaa lajittelualgoritmi. |
Yhteenveto – lisäyslajittelu vs valintalajittelu
Joskus tiedot on lajiteltava. Tietojenkäsittelytieteessä on algoritmeja tietojen lajitteluun. Tässä artikkelissa käsiteltiin kahta lajittelualgoritmia, jotka ovat lisäyslajittelu ja valintalajittelu. Lisäyslajittelu on lajittelualgoritmi, joka lajittelee taulukon siirtämällä elementtejä yksitellen. Valintalajittelu on lajittelualgoritmi, joka löytää taulukon pienimmän elementin ja vaihtaa elementin ensimmäiseen paikkaan, löytää sitten toiseksi pienimmän elementin ja vaihtaa sen toisessa asemassa olevaan elementtiin ja jatkaa prosessia, kunnes koko taulukko on lajiteltu.. Ero lisäyslajittelun ja valintalajittelun välillä on se, että lisäyslajittelu vertailee kahta elementtiä kerrallaan, kun taas valintalajittelu valitsee vähimmäiselementin koko taulukosta ja lajittelee sen.
Lataa PDF-tiedosto lisäyslajittelusta vs. valintalajittelusta
Voit ladata tämän artikkelin PDF-version ja käyttää sitä offline-tarkoituksiin lainaushuomautuksen mukaisesti. Lataa PDF-versio tästä: Ero lisäyslajittelun ja valintalajittelun välillä
