Lajittelu on perusoperaatio, jossa taulukon elementit on järjestetty tiettyyn järjestykseen, jotta sen hakukykyä voidaan parantaa. Yksinkertaisesti sanoen tiedot lajitellaan siten, että ne voidaan helposti etsiä.
Vertailukaavio
| Vertailun perusteet | Lisäys Lajittele | Valinta Lajittele |
|---|---|---|
| perustiedot | Tiedot lajitellaan lisäämällä tiedot olemassa olevaan lajiteltuun tiedostoon. | Tiedot lajitellaan valitsemalla ja asettamalla peräkkäiset elementit lajiteltuun paikkaan. |
| luonto | Vakaa | Epävakaa |
| Seurattava prosessi | Elementit ovat tiedossa etukäteen, kun sijainti niiden sijoittamiseksi etsitään. | Sijainti on aiemmin tunnettu, kun elementtejä haetaan. |
| Välitön tieto | Lisälajittelu on elävä lajittelutekniikka, joka voi käsitellä välitöntä tietoa. | Se ei pysty käsittelemään välitöntä tietoa, sen on oltava läsnä alussa. |
| Paras tapa monimutkaisuus | Päällä) | O (n 2 ) |
Lisäyksen lajittelu
Lisäysluokka toimii lisäämällä arvojen joukko olemassa olevaan lajiteltuun tiedostoon. Se rakentaa lajitellun taulukon asettamalla yksittäisen elementin kerrallaan. Tämä prosessi jatkuu, kunnes koko taulukko on järjestetty jonkun järjestyksen mukaan. Syöttölajin taustalla oleva ensisijainen käsite on lisätä jokainen kohde sopivaan paikkaan lopullisessa luettelossa. Lisälajittelumenetelmä säästää tehokkaan määrän muistia.
Lisälaitteen työskentely
- Se käyttää kahta joukkoa taulukoita, joissa yksi tallentaa lajitellut tiedot ja muut lajittelemattomiin tietoihin.
- Lajittelualgoritmi toimii, kunnes lajittelemattomassa sarjassa on elementtejä.
- Oletetaan, että joukossa on n numeron elementtejä. Aluksi lajittelussa on elementti, jolla on indeksi 0 (LB = 0). Jäljellä olevat elementit ovat luettelon lajittelemattomassa osiossa.
- Lajittelemattoman osan ensimmäisellä elementillä on taulukkoindeksi 1 (jos LB = 0).
- Jokaisen iteroinnin jälkeen se valitsee lajittelemattoman osion ensimmäisen elementin ja lisää sen oikeaan paikkaan lajitellussa sarjassa.
Lisälajittelun edut
- Helposti toteutettava ja erittäin tehokas, kun sitä käytetään pienten tietojen kanssa.
- Lisämuistitilaa vaativa lisäysluokitus on pienempi (eli O (1)).
- Sitä pidetään live-lajittelutekniikana, koska luetteloa voidaan lajitella uusien elementtien vastaanottamisen jälkeen.
- Se on nopeampi kuin muut lajittelualgoritmit.
Esimerkki:
Valinnan lajittelu
Valinta lajittelee suorittamalla lajittelun etsimällä minimiarvon numeron ja asettamalla sen ensimmäiseen tai viimeiseen paikkaan järjestyksen mukaan (nouseva tai laskeva). Vähimmäisavainhakua ja sen sijoittamista oikeaan kohtaan jatketaan, kunnes kaikki elementit on sijoitettu oikeaan asentoon.
Valinnan lajittelu
- Oletetaan array ARR, jossa on N-elementtejä muistissa.
- Ensimmäisessä siirrossa pienin avain etsitään sen sijainnin kanssa ja ARR [POS] vaihdetaan ARR: n [0] kanssa. Siksi ARR [0] on lajiteltu.
- Toisessa läpiviennissä pienimmän arvon sijainti määritetään uudelleen N-1-elementtien alaryhmässä. Vaihda ARR [POS] ja ARR [1].
- Läpikulussa N-1 suoritetaan sama prosessi N-elementtien lukumäärän lajittelemiseksi.
Esimerkki:
Lisälajittelun ja valinnan keskeiset erot
- Lisäysluokka suorittaa tavallisesti insertin toiminnon. Sitä vastoin valintalaji suorittaa vaadittujen elementtien valinnan ja paikannuksen.
- Lisäyslajin sanotaan olevan vakaa, kun taas valinta lajittelu ei ole vakaa algoritmi.
- Lisälajittelualgoritmissa elementit ovat aikaisemmin tunnettuja. Sen sijaan valinta lajittelee sijainnin etukäteen.
- Lisälajittelu on elävä lajittelutekniikka, jossa saapuvat elementit lajitellaan välittömästi luettelossa, kun taas valinta lajittelu ei toimi hyvin välittömillä tiedoilla.
- Lisälajittelussa on O (n) -käyntiaika parhaassa tapauksessa. Sitä vastoin paras lajitteluajan monimutkaisuus on lajittelussa O (n2).
Lisäyksen monimutkaisuus
Lisälajittelun paras tapa-monimutkaisuus on O (n) kertaa, eli kun matriisi on aiemmin lajiteltu. Samalla tavalla, kun taulukkoa lajitellaan päinvastaisessa järjestyksessä, lajittelemattoman ryhmän ensimmäistä elementtiä verrataan lajitellun joukon jokaiseen elementtiin. Niinpä pahimmassa tapauksessa Insertion-lajin juoksuaika on neliö, eli O (n2) . Keskimäärin myös sen on tehtävä vähintään (k-1) / 2 vertailua. Tällöin myös keskimääräinen tapaus on neliöajonopeus O (n2).
Valinnan monimutkaisuus
Koska valinta, lajittelu ei riipu taulukon elementtien alkuperäisestä järjestyksestä, joten parhaan tapauksen ja valitun lajittelun pahimman tapauksen välillä ei ole paljon eroa.
Valintalaji valitsee vähimmäisarvoelementin, valintaprosessissa skannataan kaikki n 'elementtien lukumäärä; n-1-vertailut tehdään siis ensimmäisessä passissa. Sitten elementit vaihdetaan keskenään. Samoin toisessa läpiviennissä on myös löydettävä toinen pienin elementti, jossa vaaditaan loput n-1-elementtien skannaus ja prosessi jatkuu, kunnes koko taulukko lajitellaan.
Siten valintalajittelun juoksuaikakompleksi on O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
johtopäätös
Molempien lajittelualgoritmien joukossa lisäyslaji on nopea, tehokas, vakaa, kun valintaluokka toimii tehokkaasti vain silloin, kun pieni joukko elementtejä on mukana tai lista on osittain aiemmin lajiteltu. Valintalajikkeilla tehtyjen vertailujen lukumäärä on suurempi kuin suoritetut liikkeet, kun taas insertiossa lajittelu kertoo, kuinka monta kertaa elementti siirretään tai vaihdetaan on suurempi kuin tehdyt vertailut.
