Valintalaji on yksinkertainen lajittelualgoritmi. Tämä lajittelualgoritmi on in-place-vertailuun perustuva algoritmi, jossa luettelo on jaettu kahteen osaan, lajiteltuun osaan vasemmassa päässä ja lajittelemattomaan osaan oikeassa päässä. Aluksi lajiteltu osa on tyhjä ja lajittelematon osa on koko lista.
järjestämättömästä ryhmästä valitaan pienin alkuaine ja vaihdetaan vasemmanpuoleisimpaan alkuaineeseen, ja kyseisestä alkuaineesta tulee osa lajiteltua joukkoa. Tämä prosessi jatkuu liikkuvat lajittelematon array rajan yksi elementti oikealle.
tämä algoritmi ei sovellu suurille tietojoukoille, koska sen keskimääräinen ja huonoimman tapauksen kompleksisuus on Ο(n2), jossa n on alkioiden lukumäärä.
Miten Valinnan Lajittelu Toimii?
pidetään esimerkkinä seuraavaa kuvattua joukkoa.
lajitellun luettelon ensimmäistä paikkaa varten koko lista skannataan peräkkäin. Ensimmäinen paikka, jossa 14 on tallennettu tällä hetkellä, etsimme koko luettelon ja todeta, että 10 on pienin arvo.
joten korvaamme 14: n 10: llä. Yhden iteroinnin jälkeen 10, joka sattuu olemaan luettelon vähimmäisarvo, ilmestyy lajitellun luettelon ensimmäiseen kohtaan.
toisen kannan osalta, jossa on 33, alamme skannata listan loppuosaa lineaarisesti.
havaitsemme, että 14 on listan toiseksi pienin arvo ja sen pitäisi näkyä toisella sijalla. Vaihdamme näitä arvoja.
kahden iteroinnin jälkeen kaksi pienintä arvoa sijoitetaan alkuun järjestetysti.
samaa prosessia sovelletaan myös joukon muihin kohtiin.
Seuraavassa on kuvallinen Kuvaus Koko lajitteluprosessista –
nyt opetellaan joitakin ohjelmointinäkökohtia valintalajittelusta.
algoritmi
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
pseudokoodi
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
jos haluat tietää valintalajittelun toteutuksesta C-ohjelmointikielellä, klikkaa tästä.