Řadicí algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Řadicí algoritmus (často nesprávně třídicí algoritmus)[1] 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í 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. 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í a nestabilní algoritmy.

Definice problému[editovat | editovat zdroj]

Na vstupu je posloupnost S = (S_1, S_2, \ldots, S_n); cílem je najít takovou posloupnost S' = (S_1', S_2', \ldots, S_n'), pro kterou platí dvě základní kritéria:

  1. Tato posloupnost je seřazená:
    S_1' \le S_2' \le \cdots \le S_n'.
  2. Posloupnost S' je permutací původní posloupnosti 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.

Název[editovat | editovat zdroj]

Kromě o něco přesnějšího označení úlohy jako řazení se velmi často používá také název třídění, což je nepřesné. Třídění v užším smyslu označuje jednodušší úlohu spočívající v rozdělení vstupní množiny do několika skupin podle zadaného kritéria, bez potřeby určení jejich vzájemného pořadí. Některé řadicí algoritmy však pracují na principu třídění.

Složitost[editovat | editovat zdroj]

Pro seřazení množiny n prvků existuje očividná dolní mez časové asymptotické složitosti \Omega(n) (každý prvek je potřeba alespoň jednou přečíst). Této dolní meze je ale možno dosáhnout jen při předem známé, omezené množině klíčů (např. interval v přirozených číslech). Lze dokázat, že u řazení, které je založeno na porovnávání dvojic klíčů (což je univerzální metoda použitelná pro libovolná data), je minimální časová složitost \Omega(n \log n).

Klasifikace algoritmů[editovat | editovat zdroj]

Podle různých kritérií se algoritmy řazení dají dělit do různých skupin. Dvě základní skupiny algoritmů jsou tzv. vnitřní a vnější řazení. Vnitřní řazení vyžaduje, aby všechna řazená data byla uložena v operační paměti, kde k nim má algoritmus možnost libovolně přistupovat. Pokud je dat tak velké množství, že v jednu chvíli může být v operační paměti jen nějaká část dat (a zbytek je ve vnější paměti, např. na pevném disku), je třeba použít vnější řazení.

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é 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 O(1)), algoritmus se označuje jako řazení na původním místě (in situ), jiné algoritmy však potřebují dodatečnou paměť, například místo o velikosti původních dat (tedy O(N) 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.)

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.

Ukázka řazení
Výběr Vkládaní Záměna
614532
1•64532 6•14532 145326
12•6453 16•4532 143256
123•645 146•532 132456
1234•65 1456•32 123456
12345•6 13456•2
123456

Dále lze algoritmy zhruba rozdělit podle základní myšlenky. Existuje několik základních druhů algoritmů univerzální vnitřního řazení, přičemž některé pokročilejší algoritmy kombinují více postupů.

Řazení výběrem
V souboru se vždy najde nejmenší ze zbývajících položek a uloží na konec postupně budovaného seřazeného souboru.
Řazení vkládáním
Ze souboru neseřazených dat se postupně bere položka po položce a vkládá se na správné místo v seřazeném souboru (zpočátku prázdném).
Řazení záměnou
V souboru se vždy nalezne (nějakou metodou závislou na konkrétním algoritmu) nějaká dvojice prvků, která je ve špatném pořadí, a tyto prvky se navzájem zamění.
Řazení slučováním
Vstupní soubor se rozdělí na části, které se (typicky 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ý“ řadicí algoritmus, který by byl ideální pro všechna použití. Různé algoritmy mají různé vlastnosti co se týká jejich očekávané časové a paměťové složitosti, náročnosti implementace a dalších vlastností. Pro konkrétní podmínky se tak často navrhují specifické varianty.

Běžné algoritmy[editovat | editovat zdroj]

Přehled běžných univerzálních algoritmů řazení
Název Časová složitost Dodatečná paměť Stabilní Přirozená Metoda
Anglicky Česky Minimum Průměrně Maximum
Bubble sort Bublinkové řazení O(n) O(n²) O(n²) O(1) ano ano záměna
Heapsort Řazení haldou O(n log n) O(n log n) O(n log n) O(1) ne ne halda, záměna
Insertion sort Řazení vkládáním O(n) O(n²) O(n²) O(1) ano ano vkládání
Merge sort Řazení slučováním O(n log n) O(n log n) O(n log n) O(log n) ano ano slučování
Quicksort Rychlé řazení O(n log n) O(n log n) O(n²) O(log n) ne ne záměna
Selection sort Řazení výběrem O(n²) O(n²) O(n²) O(1) zprav. ne ne výběr
Shell sort Shellovo řazení O(n^{1 + \frac{c}{\sqrt m}})[2] O(n log² n)[2] O(1) ne ano vkládání
Comb sort O(n) O(n log n) O(n²) O(1) ne ano záměna
Běžné algoritmy řazení založené na jiném principu
Název Časová složitost Dodatečná paměť Stabilní Stručný popis metody
Anglicky Česky
Bucket sort Přihrádkové řazení O(n · k) O(2k) ano Podle hodnoty klíče se data roztřídí do připravených přihrádek seřazených podle velikosti
Radix sort Řazení tříděním podle základu O(n · 2k) O(n) ano Postupné třídění po jednotlivých cifrách poziční číselné soustavy
Counting sort Řazení počítáním četností O(n + k) O(k) ano Umístění do správného pořadí po spočítání četností jednotlivých prvků

Reference[editovat | editovat zdroj]

  1. http://ksp.mff.cuni.cz/tasks/16/cook2.html
  2. a b Robert Sedgewick: Analysis of Shellsort and Related Algorithms, Fourth Annual European Symposium on Algorithms, Barcelona, září 1996

Externí odkazy[editovat | editovat zdroj]