Řadicí algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
Třídicí versus řadicí algoritmus - doplnění zdrojů, více viz Třídění |
|||
Řádek 1:
'''Třídicí algoritmus'''<ref name="Kristoufek_Encyklopedie">{{Citace monografie
'''Řadicí algoritmus''' (též nepřesně '''třídicí algoritmus''')<ref>http://ksp.mff.cuni.cz/tasks/16/cook2.html</ref> je [[algoritmus]] zajišťující seřazení daného souboru dat do specifikovaného pořadí. Nejčastěji se řadí podle numerické velikosti čísel, případně [[abecední řazení|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í.▼
| příjmení = Krištoufek
| jméno = Karel
| odkaz na autora =
| titul = Výpočetní a řídicí technika
| datum vydání = 1982-01-01
| datum aktualizace =
| datum přístupu = 2012-12-27
| edice = Oborové encyklopedie SNTL
| vydavatel = SNTL
| místo = Praha
| rok = 1982
| jazyk = český
| počet stran = 372
| strany = 309
}}</ref><ref name="Kucera_Kombinatoricke_algoritmy">{{Citace monografie
| příjmení = Kučera
| jméno = Luděk
| odkaz na autora =
| titul = Kombinatorické algoritmy
| datum vydání = 1989
| vydání = 2
| datum aktualizace =
| edice = Matematický seminář SNTL
| vydavatel = SNTL
| místo = Praha
| rok = 1989
| jazyk = český
| počet stran = 287
| strany = 89-103
}}</ref><ref name="AC_slovnik_VT">{{Citace monografie
| příjmení = Minihofer
| jméno = Oldřich
| příjmení2 = Kratochvílová
| jméno2 = Jindra
| odkaz na autora =
| titul = Anglicko-český slovník výpočetní techniky
| datum vydání = 1986
| vydání = 1
| vydavatel = SNTL
| místo = Praha
| rok = 1986
| jazyk = český
| počet stran = 287
| strany = 494
}}</ref><ref name="Topfer_Algoritmy">{{Citace monografie
| příjmení = Töpfer
| jméno = Pavel
| titul = Algoritmy a programovací techniky
| datum vydání = 1995
| vydání = 1
| vydavatel = Prometheus, s.r.o.
| místo = Praha
| rok = 1995
| jazyk = český
| počet stran = 299
| strany = 190 (178-213)
}}</ref><ref>{{Citace elektronické monografie | titul = Recepty z programátorské kuchařky – Třídění | url = http://ksp.mff.cuni.cz/tasks/16/cook2.html | datum = 2011 | jméno1 = Tomáš | příjmení1 = Valla | jméno2 = Martin | příjmení2 = Mareš | jméno3 = Dan | příjmení3 = Kráľ}}</ref> (podle některých autorů '''řadicí algoritmus'''<ref name="Satrapa_Perl">{{Citace monografie
| příjmení = Satrapa
| jméno = Pavel
| titul = Perl pro zelenáče
| datum vydání = 1995
| vydání = 1
| vydavatel = Neokortex, spol. s r.o.
| místo = Praha
| rok = 2000
| jazyk = český
| počet stran = 224
| strany = 66
▲
Z hlediska řazení se vstupní data chápou jako soubor dvojic klíč–hodnota, přičemž po seřazení je posloupnost klíčů [[monotonicita|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. Při existenci několika položek se stejným klíčem se však podle pořadí odpovídajících hodnot rozlišují [[stabilní řazení|stabilní]] a nestabilní algoritmy.
Řádek 12 ⟶ 81:
== Název ==
{{Podrobně|Třídění}}
Pro uspořádávání prvků do posloupnosti byl v informatice zaveden český termín '''třídění''', který byl také definován v (již zrušené) názvoslovné normě ČSN 36 9001. Mnoho autorů se domnívá, že pro tuto činnost by byl vhodnější termín '''řazení''', přičemž '''třídění''' by se mělo používat pro rozdělování sady záznamů do několika skupin podle zadaného kritéria, bez potřeby určení jejich vzájemného pořadí. Pouze někteří autoři však pro uspořádávání prvků do posloupnosti název '''řazení''' skutečně používají. Pro rozdělování záznamů do skupin lze používat jednoznačnější název '''klasifikace'''.
Některé algoritmy uspořádávání záznamů do posloupnosti využívají při své práci jejich rozdělování do několika skupin.
== Složitost ==
Řádek 24 ⟶ 96:
Kromě samotných řazených dat také algoritmus zpravidla potřebuje nějakou dodatečnou pracovní paměť. Pokud je velikost této paměti konstantní (nezávislá na množství řazených dat, označováno jako <math>O(1)</math>), algoritmus se označuje jako řazení na původním místě (''in situ'' nebo ''[[in-place algoritmus]]''), jiné algoritmy však potřebují dodatečnou paměť, například místo o velikosti původních dat (tedy <math>O(N)</math> v asymptotickém vyjádření), ve kterém generují seřazený výsledek.
Vstupní data mohou obsahovat několik prvků se shodným klíčem. Podle vzájemné polohy těchto prvků před a po seřazení (kterou lze detekovat podle přidružených dat, která nejsou součástí klíče) se rozlišují tzv. ''stabilní'' a ''nestabilní''
Podle chování na částečně seřazených souborech dat se rozlišují algoritmy ''přirozené'' a ''nepřirozené'': přirozený algoritmus rychleji zpracuje seřazenou množinu než neseřazenou.
Řádek 57 ⟶ 129:
: Vstupní soubor se rozdělí na části, které se (typicky [[rekurze|rekurzivně]]) seřadí; výsledné seřazené části se poté sloučí takovým způsobem, aby i výsledek byl seřazený.
Neexistuje žádný „dokonalý“
=== Běžné algoritmy ===
| |||