Valintalajittelu

Animaatio valintalajittelun etenemisestä.

Valintalajittelu (engl. selection sort) on tietojenkäsittelytieteessä tehoton mutta yksinkertainen ja intuitiivinen lajittelualgoritmi. Sen keskimääräinen asymptoottinen suoritusaika on O(n²).

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

Esimerkki viiden luvun valintalajittelusta. Listan pienin luku vaihtaa listan ensimmäisen luvun kanssa paikkaa. Loppulistan pienin (eli listan toiseksi pienin) luku vaihtaa listan toisen luvun kanssa paikkaa. Näin jatkaen lista lajittuu.

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.