Řadicí algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
m rv, odkazy do cizojazyčné Wiki jsou zbytečné |
→Klasifikace algoritmů: wiki na in-place |
||
Řádek 22:
Největší část algoritmů řazení je založena na porovnávání dvojic prvků; jedná se o univerzální metodu, kterou lze seřadit libovolná data v libovolné reprezentaci (stačí příslušná relace uspořádání). Pro některé konkrétní reprezentace nějak vymezené množiny dat lze sestrojit algoritmy, které fungují na jiném principu, např. na základě reprezentace řazených čísel v [[poziční číselná soustava|poziční číselné soustavě]].
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í'' řadicí algoritmy: stabilní algoritmus zachovává vzájemné pořadí položek se stejným klíčem, u nestabilního není vzájemné pořadí prvků se stejným klíčem zaručeno. (Ale z libovolného nestabilního algoritmu lze učinit stabilní tím, že se klíč každé položky vstupních dat rozšíří o pozici položky v původním souboru.)
| |||