zvolit - online puzzle

Ř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

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í.

Rozdělíme si posloupnost na seřazenou a neseřazenou část

Najdeme prvek s nejmenší hodnotou v neseřazené části posloupnosti

Zaměníme ho s prvkem na první pozici neseřazené části

První prvek neseřazené části zahrneme do seřazené části a zároveň neseřazenou část zmenšíme o 1 prvek zleva

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

}

{\displaystyle M=\{3_{1},2,3_{2},1\}}

, tak nám ji algoritmus seřadí jako

M

=

{

1

,

2

,

3

2

,

3

1

}

{\displaystyle M=\{1,2,3_{2},3_{1}\}}

.