Valintalajittelu

Valintalajittelu () 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 
 LiteratePrograms wiki: Category:Selection sort 

 Kirjallisuutta 
 Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. .

Luokka:Lajittelualgoritmit