Řazení výběrem

Řazení výběrem je v informatice implementačně 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 řazení haldou nebo řazení slučováním.

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

Animace řazení výběrem. Červeně je zvýrazněno aktuální minimum. Žlutě je označena srovnaná část seznamu. Modrá je aktuální položka

Algoritmus je univerzální (pracuje na základě porovnávání dvojic prvků), pracuje lokálně (nevyžaduje pomocnou paměť), není stabilním (prvkům se stejným klíčem může změnit vzájemnou polohu) a nepatří mezi přirozené řadicí algoritmy (částečně seřazený seznam se bude zpracovávat stejně dlouho jako neseřazený).

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=\{3_{1},2,3_{2},1\}$, tak nám ji algoritmus seřadí jako $M=\{1,2,3_{2},3_{1}\}$. Zde je jasně vidět, že algoritmus prohodil prvky $\{3_{1}\}$ a $\{3_{2}\}$, což stabilní algoritmus řazení neudělá.

Řazení výběrem je možno implementovat i stabilně, pokud se místo záměny prvků použije přesunutí nalezeného nejmenšího prvku na příslušné místo, k tomu je ovšem potřeba použití datové struktury s rychlým vkládáním a odstraňováním, například spojový seznam, jinak výrazně zhorší výkonnost algoritmu.

Implementace algoritmu

Příklad 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;
	}
}

Externí odkazy

• Obrázky, zvuky či videa k tématu selection sort na Wikimedia Commons