Selection sort

Ilustrace řazení výběrem na náhodné množině

Selection sort (řazení výběrem) je jednoduchý řadicí algoritmus 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 Heapsort nebo Mergesort.

Algoritmus je univerzální (pracuje na základě porovnávání dvojic prvků), pracuje lokálně (nevyžaduje pomocnou paměť) a není stabilním (prvkům se stejným klíčem může změnit vzájemnou polohu)..

Princip

Budeme uvažovat o vzestupném řazení. Seřazenou část budeme mít vlevo a vždy budeme hledat minimum z neseřazené části. Analogicky opačně se tento princip může aplikovat pro sestupné řazení.

1. Rozdělíme si posloupnost na seřazenou a neseřazenou část
2. Najdeme prvek s nejmenší hodnotou v neseřazené části posloupnosti
3. Zaměníme ho s prvkem na první pozici neseřazené části
4. První prvek neseřazené části zahrneme do seřazené části a zároveň neseřazenou část zmenšíme o 1 prvek zleva
5. Zbytek posloupnosti se uspořádá opakováním kroků 2 až 5 pro zbylou neseřazenou část

Nestabilita řazení

Algoritmus není stabilním (může změnit pořadí u prvků se shodným klíčem).

Je to dáno tím, že se prohazují nesousední prvky. Například pokud uvážíme množinu $M = \{5, 3_1, 1, 3_2, 2\}$, tak nám ji algoritmus seřadí jako $M = \{1, 2, 3_2, 3_1, 5\}$. Zde je jasně vidět, že algoritmus prohodil prvky $\{3_1\}$ a $\{3_2\}$, což stabilní algoritmus řazení neudělá.

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;
        }
}

Implementace algoritmu v jazyce Java

public static void selectionSort1(int[] x) {
    for (int i=0; i<x.length-1; i++) {
        for (int j=i+1; j<x.length; j++) {
            if (x[i] > x[j]) {
                //... Exchange elements
                int temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            }
        }
    }
}