Selection sort
Z Wikipedie, otevřené encyklopedie
Selection sort (zkráceně Selectsort) je jednoduchý algoritmus uspořádávání s časovou složitostí O(N2). Pro svou jednoduchou implementaci a nízký overhead bývá často používán pro uspořádávání malých množství dat. Pro větší objem dat se používají algoritmy s nižší časovou složitostí (O(N log N)) jako Quicksort nebo Mergesort.
[editovat] Princip
- Najdeme prvek s nejmenší hodnotou v posloupnosti dat
- Zaměníme ho s prvkem na první pozici
- Na první pozici se nyní nachází správný prvek, zbytek posloupnosti se uspořádá opakováním těchto kroků pro zbylých n-1 prvků, dokud je n > 1
[editovat] Implementace algoritmu v jazyce C
void selectionSort(int data[], int count)
{
int i, j, mi, tmp;
for (i = 0; i < count - 1; i++) {
/* najdeme minimum */
mi = i;
for (j = i+1; j < count; j++)
if (data[j] < data[mi])
mi = j;
/* vyměníme data[i] a data[mi] */
tmp = data[i];
data[i] = data[mi];
data[mi] = tmp;
}
}
