Avainten ero - lisäyslajittelu vs. valintalajittelu
Lisälajittelu ja valintalajittelu ovat kaksi lajittelualgoritmia, joita käytetään tietojen kokoamiseen. Joskus on tarpeen järjestää tiedot tietyssä järjestyksessä. Lajittelualgoritmit ovat mekanismeja tietojoukon lajittelemiseksi. Lajittelussa tiedot järjestetään numeerisen tai leksikografisen järjestyksen mukaan. Jos tiedot on lajiteltu oikein, tiedoista olisi helppo etsiä nopeammin. Jos puhelinluettelossa olevat puhelinnumerot eivät ole lajiteltuina, tietyn puhelinnumeron löytäminen on vaikeaa. Samalla tavalla, jos sanakirjan sanoja ei ole järjestetty aakkosjärjestykseen, on vaikea löytää sanoja. Siksi lajittelusta on hyötyä jokapäiväisessä elämässä. Tietojenkäsittelytieteessä on lajittelualgoritmeja tietokokoelman lajittelemiseksi. Kaksi tällaista algoritmia ovat lisäyslajittelu ja valintalajittelu. Lisäämislajittelu on lajittelualgoritmi, joka lajittelee matriisin siirtämällä elementtejä yksi kerrallaan. Valintalajittelu on lajittelualgoritmi, joka löytää matriisista pienimmän elementin ja vaihtaa elementin ensimmäisen sijainnin kanssa, etsi sitten toisen pienimmän elementin ja vaihtaa sen toisessa asemassa olevan elementin kanssa ja jatkaa prosessia, kunnes koko taulukko on lajiteltu. Tärkein ero lisäyslajittelun ja valintalajittelun välillä on se, että lisäyslajittelu vertaa kahta elementtiä kerrallaan, kun taas lajittelulaji valitsee minimielementin koko taulukosta ja lajittelee sen.etsi sitten toinen pienin elementti ja vaihda se toisessa asemassa olevan elementin kanssa ja jatkaa prosessia, kunnes koko taulukko on lajiteltu. Tärkein ero lisäyslajittelun ja valintalajittelun välillä on se, että lisäyslajittelu vertaa kahta elementtiä kerrallaan, kun taas lajittelulaji valitsee minimielementin koko taulukosta ja lajittelee sen.etsi sitten toinen pienin elementti ja vaihda se toisessa asemassa olevan elementin kanssa ja jatkaa prosessia, kunnes koko taulukko on lajiteltu. Tärkein ero lisäyslajittelun ja valintalajittelun välillä on se, että lisäyslajittelu vertaa kahta elementtiä kerrallaan, kun taas lajittelulaji valitsee minimielementin koko taulukosta ja lajittelee sen.
SISÄLLYS
1. Yleiskatsaus ja avainerot
2. Mikä on lisäyslajittelu
3. Mikä on valintalajittelu
4. Lisälajittelun ja valintalajittelun yhtäläisyydet
5. Vertailu vierekkäin - lisäyslajittelu vs. valintalajittelu taulukkomuodossa
6. Yhteenveto
Mikä on lisäyslajittelu?
Lisälajittelu on paikan päällä tehty vertailupohjainen lajittelualgoritmi. Tässä menetelmässä taulukkoa etsitään askel askeleelta. Lajittelemattomat kohteet siirretään ja lisätään taulukkolajitteluun. Lisäyslajittelualgoritmi voidaan selittää seuraavan esimerkin avulla.
Ota esimerkiksi alkutaulukoksi 77,33, 44,11,88. Tässä lajittelualgoritmissa ensimmäinen vaihe on valita nykyinen elementti.
Nykyinen elementti on 77. Nykyistä elementtiä verrataan kaikkiin vasemman puolen elementteihin. 77 on ensimmäinen elementti, eikä vasemmalla puolella ole elementtejä. Nykyisen sijainnin indeksi on 0.
Sitten nykyisen sijainnin indeksiä lisätään 1: llä. Nyt indeksi on 1 ja nykyinen elementti on 33. Kun verrataan sitä vasemmalla olevaan elementtiin, se on pienempi kuin 77. Sitten molemmat arvot vaihdetaan. Nyt 33 on indeksissä 0 ja 77 on indeksissä 1.
Nyt taulukko on 33, 77, 44, 11, 88.
Jälleen indeksi kasvaa. Hakemisto on 2 ja nykyinen elementti on 44. Sitä verrataan vasemmalla puolella oleviin elementteihin. 44 on alle 77. Joten nämä kaksi arvoa vaihdetaan. Nyt taulukko on 33,44,77,11,88. On tarpeen verrata kaikkia vasemmalla olevia elementtejä. 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 kasvaa. Hakemisto on 3 ja nykyinen elementti on 11. Sitä verrataan kaikkiin vasemmalla oleviin elementteihin. 11 on alle 77, joten nämä kaksi vaihdetaan. Nyt taulukko on 33,44,11,77,88. Verrattaessa 11 ja 44, 11 on alle 44. Joten nämä kaksi vaihdetaan. Nyt matriisit ovat 33,11,44,77,88. Jälleen 11 verrataan 33: een. 11 on alle 33, joten nämä kaksi arvoa vaihdetaan.
Nyt taulukko on 11,33,44,77,88.
Indeksin korottaminen tekee indeksistä arvon 4. Arvo on 88. Se on suurempi kuin 77. Vaihtoa ei siis tarvitse. Lopuksi lajiteltu taulukko on 11,33,44,77,88.
Kuva 01: Esimerkki lisäyslajittelusta
Lisäyslajittelun toteutus on kuten yllä. Alkuperäinen taulukko oli 77,33, 44,11,88. Lajittelun jälkeen se antaa tuloksen 11,33,44,77,88.
Mikä on valintalajittelu?
Valintalajittelu on paikan päällä tehty vertailupohjainen lajittelualgoritmi. Taulukot on jaettu osiin. Lajiteltu osa on vasemmassa päässä. Lajittelematon osa on oikeassa päässä. Ensinnäkin tulisi löytää pienin arvo. Sitten se vaihdetaan vasemman elementin kanssa. Nyt tämä elementti on lajiteltu taulukossa. Tämä prosessi jatkaa lajittelemattoman matriisirajan siirtämistä yhdestä elementistä oikealle. Valintalajittelualgoritmi voidaan selittää seuraavan esimerkin avulla.
Ota esimerkiksi alkutaulukoksi 77,33, 44,11,88,22. Tässä lajittelualgoritmissa taulukon pienin löytyy. Pienin elementti on 11. Se vaihdetaan elementin kanssa taulukon 0-indeksissä.
Nyt taulukko on 11,33,44,77,88,22.
Pienin elementti on indeksissä 0, joten 11 on nyt lajiteltu. Muusta elementtien pienin on 22. vaihtuu kanssa 1 st indeksin elementti.
Nyt taulukko on 11,22,44,77,88,33.
Elementit 11 ja 22 on jo lajiteltu. Muusta, pienin arvo on 33. Se vaihtaminen onnistuu 2 toisen indeksin elementti.
Nyt taulukko on 11,22,33,77,88,44.
Elementit 11, 22 ja 33 on jo lajiteltu. Muusta, pienin arvo on 44. vaihtuu kanssa 3 rd indeksin elementti.
Nyt taulukko on 11,22,33,44,88,66.
Elementit 11,22,33,44 on jo lajiteltu. Muut elementit ovat 88 ja 66. elementti 66 on vaihdettu 4 : nnen indeksin elementti.
Nyt taulukko on 11,22,33,44,66,88.
Se on lajiteltu taulukko, joka käyttää valintalajittelualgoritmia.
Kuva 02: Esimerkki valinnan lajittelusta
Lisäyslajittelun toteutus on kuten yllä. Alkuperäinen taulukko oli 77,33, 44,11,88. Lajittelun jälkeen se antaa tuloksen 11,33,44,77,88.
Mikä on lisäyslajittelun ja valintalajittelun samankaltaisuus?
Sekä lisäyslajittelu että valintalajittelu ovat lajittelualgoritmeja
Mikä ero on lisäyslajittelun ja valintalajittelun välillä?
Erilainen artikkeli keskellä taulukkoa
Lisälajittelu vs. valintalajittelu |
|
| Lisäämislajittelu on lajittelualgoritmi, joka lajittelee matriisin siirtämällä elementtejä yksi kerrallaan. | Valintalajittelu on lajittelualgoritmi, joka löytää matriisista pienimmän elementin ja vaihtaa elementin ensimmäisen sijainnin kanssa, etsi sitten toisen pienimmän elementin ja vaihtaa sen toisessa asemassa olevan elementin kanssa ja jatkaa prosessia, kunnes koko taulukko on lajiteltu. |
| Käsitellä asiaa | |
| Lisälajittelun tarkoituksena on lajitella alaluettelo vertaamalla kahta elementtiä, kunnes koko taulukko on lajiteltu. | Valintalaji valitsee minimielementin ja vaihtaa sen ensimmäiseen sijaintiin, valitsee jälleen vähimmäismäärän muille ja vaihtaa toisen sijainnin ja jatkaa tätä prosessia loppuun asti. |
| Vakaus | |
| Lisälajittelu on vakaa lajittelualgoritmi. | Valintalajittelu ei ole vakaa lajittelualgoritmi. |
Yhteenveto - lisäyslajittelu vs. valintalajittelu
Joskus on tarpeen lajitella tietoja. Tietojenkäsittelytieteen tiedoissa on algoritmeja tietojen lajittelemiseksi. Tässä artikkelissa käsiteltiin kahta lajittelualgoritmia, jotka ovat lisäyslajittelu ja valintalajittelu. Lisäämislajittelu on lajittelualgoritmi, joka lajittelee matriisin siirtämällä elementtejä yksi kerrallaan. Valintalajittelu on lajittelualgoritmi, joka löytää matriisista pienimmän elementin ja vaihtaa elementin ensimmäisen sijainnin kanssa, etsi sitten toisen pienimmän elementin ja vaihtaa sen toisessa asemassa olevan elementin kanssa ja jatkaa prosessia, kunnes koko taulukko on lajiteltu. Ero lisäyslajittelun ja valintalajittelun välillä on se, että lisäyslajittelu vertaa kahta elementtiä kerrallaan, kun taas lajittelulaji valitsee minimielementin koko taulukosta ja lajittelee sen.
Lataa PDF-tiedosto Insertion Sort vs Selection Sort -sivulta
Voit ladata tämän artikkelin PDF-version ja käyttää sitä offline-tarkoituksiin lainausviestin mukaan. Lataa PDF-versio täältä: Ero lisäyslajittelun ja valintalajittelun välillä
