Selection sort

Z Wikipedie, otevřené encyklopedie

Selection sort (zkráceně Selectsort) je jednoduchý algoritmus uspořádávání s časovou složitostí O(N²). 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

1. Najdeme prvek s nejmenší hodnotou v posloupnosti dat
2. Zaměníme ho s prvkem na první pozici
3. 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;
        }
}

Tento článek je pahýl. Můžete pomoci Wikipedii tím, že jej rozšíříte.