druh - online puzzle
Řadicí nebo třídicí algoritmus je algoritmus zajišťující uspořádání dané sady (pole, seznamu, souboru) datových záznamů do požadovaného pořadí. Pro porovnávání se obvykle nepoužívá celý záznam, ale jeho jedna nebo více jeho položek nazývaných klíče. Tyto položky bývají zpravidla numerické, které se řadí podle hodnoty nebo řetězcové, které se řadí abecedně. Řazení je velmi častá úloha, která je také částí mnoha dalších algoritmů; vývoji co možná nejefektivnějších algoritmů řazení se proto věnuje velké úsilí.
Z hlediska řazení se vstupní data chápou jako soubor dvojic klíč–hodnota, přičemž po seřazení je posloupnost klíčů monotónní, zatímco na připojené hodnoty se při řazení nebere zřetel a pouze se přesouvají vždy s odpovídajícím klíčem. Podle toho, zda se zachovává pořadí položek se stejným klíčem, rozlišuje algoritmy řazení na stabilní a nestabilní.
Definice problému
Na vstupu je posloupnost záznamů
S
=
(
S
1
,
S
2
,
…
,
S
n
)
{\displaystyle S=(S_{1},S_{2},\ldots,S_{n})}
; cílem je najít takovou posloupnost
S
′
=
(
S
1
′
,
S
2
′
,
…
,
S
n
′
)
{\displaystyle S'=(S_{1}',S_{2}',\ldots,S_{n}')}
, pro kterou platí dvě základní kritéria:
Tato posloupnost je seřazená:
S
1
′
≤
S
2
′
≤
⋯
≤
S
n
′
{\displaystyle S_{1}'\leq S_{2}'\leq \cdots \leq S_{n}'}
.
Posloupnost
S
′
{\displaystyle S'}
je permutací původní posloupnosti
S
{\displaystyle S}
(obsahuje tedy stejná data, jen v jiném pořadí).V definici relace uspořádání ≤ se přitom bere ohled pouze na klíče příslušných hodnot. V některých programovacích jazycích (Perl, Tcl, Java) je k dispozici knihovní funkce realizující třídění, které lze předat funkci pro porovnání záznamů. Porovnávací funkce má dva parametry – odkazy na dva záznamy – a vrací hodnotu -1, pokud první záznam má být před druhým; 1 pokud první záznam má být za druhým; 0 pokud na pořadí záznamů nezáleží (u stabilního algoritmu se musí relativní pořadí záznamů zachovat).
