Verze z 16. 5. 2012, 07:47 editovat MerlIwBot (diskuse \| příspěvky) 117 702 editací m Robot: Přidávám th:การเรียงลำดับแบบเลือก ← Přejít na předchozí porovnání		Verze z 14. 11. 2012, 01:08 editovat zrušit editaci Vaclav.Makes (diskuse \| příspěvky) 6 623 editací rozšíření textu, přeformulování některých částí, odstraněn {{Pahýl}} Přejít na další porovnání →
Řádek 1: [[File:Selection sort animation.gif\|thumb\|Ilustrace řazení výběrem na náhodné množině]] '''Selection sort''' ('''řazení výběrem''') je jednoduchý [[Algoritmus řazení\|řadicí algoritmus]] ~~uspořádávání~~ s časovou složitostí {{math\|[[asymptotická složitost\|''O'']](<var>N</var>²)}}. Pro svou jednoduchou [[implementace\|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í ({{math\|''O''(<var>N</var> log <var>N</var>)}}) jako [[Heapsort]] nebo [[Merge sort\|Mergesort]]. Algoritmus je univerzální (pracuje na základě porovnávání dvojic prvků), pracuje lokálně (nevyžaduje pomocnou paměť) a není [[Stabilní řazení\|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í. # Najdeme prvek s nejmenší hodnotou v posloupnosti dat▼ # Zaměníme ho s prvkem na první pozici▼ # Rozdělíme si posloupnost na seřazenou a neseřazenou část ~~# 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~~ ▲# Najdeme prvek s nejmenší hodnotou v ~~posloupnosti~~neseřazené ~~dat~~čá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í řazení\|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žina\|množinu]] <math>M = \{5, 3_1, 1, 3_2, 2\}</math>, tak nám ji algoritmus seřadí jako <math>M = \{1, 2, 3_2, 3_1, 5\}</math>. Zde je jasně vidět, že algoritmus prohodil prvky <math>\{3_1\}</math> a <math>\{3_2\}</math>, což stabilní algoritmus řazení neudělá. == Implementace algoritmu v jazyce [[C (programovací jazyk)\|C]] == Řádek 42 ⟶ 53: } </source> ~~{{Pahýl}}~~ [[Kategorie:Řadicí algoritmy]]

Řazení výběrem: Porovnání verzí