Valintalajittelu (engl. selection sort) on tietojenkäsittelytieteessä tehoton mutta yksinkertainen ja intuitiivinen lajittelualgoritmi. Sen keskimääräinen asymptoottinen suoritusaika on O(n2).
Valintalajittelu (engl. selection sort) on tietojenkäsittelytieteessä tehoton mutta yksinkertainen ja intuitiivinen lajittelualgoritmi. Sen keskimääräinen asymptoottinen suoritusaika on O(n2).
Algoritmi voidaan ilmaista seuraavasti:
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:
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]);
}
}