Selection sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Ilustrace řazení výběrem na náhodné množině
Animace selection sortu. Červeně je zvýrazněno aktuální minimum. Žlutě je označena srovnaná část seznamu. Modrá je aktuální položka

Řazení výběrem (anglicky selection sort) je 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 Heapsort nebo Mergesort.

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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