Valintalajittelu

Wikipedia
Loikkaa: valikkoon, hakuun

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

Algoritmi[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

Algoritmeista[muokkaa | muokkaa wikitekstiä]

Muita lajittelualgoritmeja[muokkaa | muokkaa wikitekstiä]

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]

Kirjallisuutta[muokkaa | muokkaa wikitekstiä]