Problém řazení je považován za nejdůležitější problém při studiu algoritmů. Úkolem je uspořádat množinu prvků obsahujících klíč podle definovaného kriteria. Například podle číselných hodnot nebo abecedně, v závislosti na charakteru klíče. Velice často je požadavek řazení přímo vyžadován aplikací, často však algoritmy používají řazení jako svoji součást.
Mějme zjistit zda v posloupnosti prvků, například celých čísel, jsou duplicitní hodnoty. Porovnáváme-li postupně každý prvek s následujícími, získáme algoritmus na obr.. Čas jeho výpočtu je zřejmě O( n2). Kdybychom pole a nejprve uspořádali a potom v lineárním čase porovnali sousedy, dostaneme algoritmus, kterého časová náročnost je dána časovou náročností řazení a již víme, že řazení haldou je v nejhorším případě nejvíce n log2 n.
Grafické objekty uložené na sobě může program, jenž je zobrazuje, napřed uspořádat, aby rozhodl v jakém pořadí se zakrývají.
Jsou-li prvky, které máme seřadit uloženy v hlavní paměti, tj. máme-li pro ně a pro řadící algoritmus dostatečný paměťový prostor, mluvíme o vnitřním řazení, kdy je každý z prvků přímo přístupný. Řazení prvků uložených v souborech, např. na discích se nazývá vnější řazení, kdy k nim můžeme přistupovat sekvenčně, nejčastěji v skupinách uložených v blocích souboru. Dále se budeme zabývat algoritmy pro vnitřní řazení.
Již v případě obecného algoritmu řazení prioritní frontou jsme viděli, že algoritmus řazení může, kromě paměti, v níž jsou uložené řazené prvky, mít další nároky na paměť. Ukázali jsme také, že zmíněný obecný algoritmus, jsme mohli upravit tak, aby až na pomocnou proměnnou pro výměnu prvků, nepotřeboval další paměť. Algoritmus řazení, který potřebuje kromě paměti pro řazené prvky další paměť pro konstantní počet řazených prvků, budeme označovat jako algoritmus řadící na místě.
Někdy můžou řazené prvky obsahovat několik klíčů a klíč pro řazení určujeme podle aktuální potřeby. V takovém případě může být důležitá následující vlastnost řadícího algoritmu.
Řadící algoritmus se nazývá stabilní, jestliže zachovává relativní pořadí prvků se stejným klíčem.
Uvažujme množinu prvků obsahujících jako klíče křestní jméno a příjmení seřazenou podle křestních jmen na obr.. Seřadíme-li je dále podle příjmení stabilním algoritmem, zůstanou prvky se stejným příjmením ve stejném pořadí, tedy prvky se stejným příjmením budou seřazeny podle křestního jména. Nestabilní algoritmus původní pořadí nezachová (obr.
).
Dosud zmíněné řadící algoritmy určovaly výsledné pořadí prvků na základě porovnávání jejich klíčů a takové řadící algoritmy budeme nazývat porovnávací. Pokud, kromě možnosti porovnání, máme další informace o klíčích, někdy můžeme určit jejich pozici, adresu, v seřazené posloupnosti a takové algoritmy nazýváme adresní.
Pro ilustraci si uvedeme počítací algoritmus, který umožňuje řazení bez porovnávání klíčů. Předpokladem je, že klíče mají hodnoty z množiny {0, 1, ..., k}. Spočítáme-li počet výskytů jednotlivých klíčů, potom pozice prvku je určena počtem klíčů menších než je jeho klíč.
Ať je úkolem seřadit do prvků b[1]až b[n] pole b n různých klíčů uložených v poli a v prvcích a[1] až a[n]. Spočteme počet výskytů klíče i a uložíme ho do prvku c[i] pro i = 0, 1,..., k. Dále spočteme počet klíčů menších nebo rovných klíči i sčítáním s počtem výskytů menších klíčů, pro i = 1, 2, ..., k. Pro zjednodušení předpokládejme, že všechny klíče jsou různé. Potom c[a[j]] je správná pozice prvku a[j], pro j =1, 2, ..., n v poli b. Algoritmus řazení počítaním je na obr.. Činnost algoritmu je demonstrována na obr.
pro k=7 a n=5. Klíče jsme seřadili bez toho, abychom porovnávali jejich hodnoty, pouhým počítáním jejich výskytů. Dále se budeme zabývat porovnávacími algoritmy řazení.
Řazení obecně vyžaduje přesuny řazených prvků. V našich dosavadních příkladech jsme myšlenku jednotlivých algoritmů demonstrovali na řazení celočíselných klíčů a tyto jsme také přesouvali bylo-li to potřeba. Tento přístup nazýváme přímé řazení. Pokud je však klíč položkou velkých prvků, je vhodné zabránit jejich přesouvání a namísto toho seřadit ukazatele případně indexy řazených prvků tak, aby první ukazoval na nejmenší prvek, atd. Tento přístup se nazývá nepřímé řazení.
V Javě je přirozené v praktických případech používat právě nepřímé řazení s využitím referenčních proměnných. Pro obecný porovnávací algoritmus je vhodné, aby třída řazených prvků obsahovala metodu, která definuje jejich uspořádaní, například jeMensi(Prvek).