Valintalajittelu
![](http://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif)
Valintalajittelu (engl. selection sort) on tietojenkäsittelytieteessä tehoton mutta yksinkertainen ja intuitiivinen lajittelualgoritmi. Sen keskimääräinen asymptoottinen suoritusaika on O(n2).
Algoritmi
Algoritmi voidaan ilmaista seuraavasti:
- Etsitään taulukon pienin alkio ja vaihdetaan se taulukon ensimmäiseksi alkioksi.
- Nyt ensimmäinen alkio on pienin.
- Etsitään taulukon toisesta alkiosta alkaen pienin arvo ja vaihdetaan se toiseksi alkioksi.
- Nyt kaksi ensimmäistä alkiota ovat suuruusjärjestyksessä.
- Tehdään sama kolmannelle alkiolle, neljännelle alkiolle...
- Kun toiseksi viimeinen alkio on saatu käsiteltyä, koko taulukko on järjestyksessä.
T: taulukko first: T:n ensimmäinen lajiteltava indeksi last: T:n viimeinen lajiteltava indeksi for i := first to last – 1 do min := pienin alkio väliltä T[i]...T[last] vaihda T[i] <–> min end for
Tällöin silmukkainvariantti on:
- T[first], ... , T[i] on järjestyksessä
- T[i–1] ≤ T[i], ... , T[last], kun i > 0
Toteutus
C++-kielellä koko algoritmi, mukaan lukien minimiarvon etsiminen, voidaan kirjoittaa seuraavasti:
void selectionSort(int T[], int pituus) { int i, j, min; for (i = 0; i < pituus - 1; i++) { min = i; for (j = i+1; j < pituus; j++) if (T[j] < T[min]) min = j; swap(T[i], T[min]); } }
Katso myös
Algoritmeista
- Asymptoottinen suoritusaika
- Lajittelualgoritmi
Muita lajittelualgoritmeja
- Vaihtolajittelu (hyvin samanlainen)
- Lisäyslajittelu (yksinkertainen ja todella nopea, jos lajiteltavaa on vähän)
- Pikalajittelu (asymptoottisesti keskimäärin tehokkaampi)
- Lomituslajittelu (pahimmassakin tapauksessa asymptoottisesti tehokkaampi)
- Kekolajittelu (valintalajittelu yhdistettynä kekoon on tehokas algoritmi)
Aiheesta muualla
- Timo Männikkö: Johdatus ohjelmointiin -luentomoniste: 1.2.2 Yleistäminen (intuitiivinen vertaus korttipakkaan)
- L. Malmi, A. Korhonen ja V. Karavirta: TRAKLA2: Valintajärjestäminen (Arkistoitu – Internet Archive)
- LiteratePrograms wiki: Category:Selection sort (Arkistoitu – Internet Archive)
Kirjallisuutta
- Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0.