text: # Řadicí algoritmus
  Ř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ů {\displaystyle S=(S_{1},S_{2},\ldots ,S_{n})}; cílem je najít takovou posloupnost {\displaystyle S'=(S_{1}',S_{2}',\ldots ,S_{n}')}, pro kterou platí dvě základní kritéria:
  1. Tato posloupnost je seřazená:
  {\displaystyle S_{1}'\leq S_{2}'\leq \cdots \leq S_{n}'}.
  2. Posloupnost {\displaystyle S'} je permutací původní posloupnosti {\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). Tento přístup umožňuje nejen třídění podle klíčů, ale obecněji podle libovolné ohodnocovací funkce.
  
  ## Název
  Pro uspořádávání prvků do posloupnosti podle určitého kritéria se v češtině používá slovo řazení; v informatice byl zaveden termín třídění odpovídající anglickému sort, sorting, který byl takto definován v (již zrušené) názvoslovné normě ČSN 36 9001. Někteří autoři se domnívají, že pro uspořádávání je vhodnější termín řazení, přičemž třídění by se mělo používat pro rozdělování sady prvků do několika skupin podle zadaného kritéria, a to bez potřeby určení vzájemného pořadí tříděných prvků. Pouze někteří autoři však pro uspořádávání prvků do posloupnosti termín řazení skutečně používají.
  Pro rozdělování prvků do skupin lze používat jednoznačný název kategorizace, případně 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
  Pro seřazení množiny {\displaystyle n} prvků existuje očividná dolní mez časové asymptotické složitosti {\displaystyle O(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 {\displaystyle O(n\log n)}.
  Pro délku pole v násobcích dvou platí:
  {\displaystyle O(n\log n)=(\ln(n)/\ln(2)-1)*n+1}
  Pro představu, jaký je rozdíl mezi řazením 1 000 prvků a 1 000 000 prvků:
  {\displaystyle n=2^{4}=16,O(n\log n)=49(3*16+1)}
  {\displaystyle n=2^{8}=256,O(n\log n)=1.793(7*256+1)}
  {\displaystyle n=2^{10}=1.024,O(n\log n)=9.217(9*1024+1)}
  {\displaystyle n=2^{20}=1.048.576,O(n\log n)=19.922.945(19*1048576+1)}
  
  ## Klasifikace algoritmů
  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 {\displaystyle O(1)}), 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 {\displaystyle 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í třídicí 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.
  | Výběr   | Vkládaní | Záměna |
  | 614532  | 614532   | 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ý“ třídicí 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
  | Název                  | Název              | Časová složitost                                | Časová složitost | Časová složitost | Dodatečná paměť | Stabilní  | Přirozená | Metoda        |
  | Název                  | Znám jako          | Minimum                                         | Průměrně         | Maximum          | Dodatečná paměť | Stabilní  | Přirozená | Metoda        |
  | ---------------------- | ------------------ | ----------------------------------------------- | ---------------- | ---------------- | --------------- | --------- | --------- | ------------- |
  | bublinkové řazení      | bubble sort        | O(n)                                            | O(n²)            | O(n²)            | O(1)            | ano       | ano       | záměna        |
  | řazení haldou          | heapsort           | O(n log n)                                      | O(n log n)       | O(n log n)       | O(1)            | ne        | ne        | halda, záměna |
  | řazení vkládáním       | insertion sort     | O(n)                                            | O(n²)            | O(n²)            | O(1)            | ano       | ano       | vkládání      |
  | řazení slučováním      | merge sort         | O(n log n)                                      | O(n log n)       | O(n log n)       | O(log n)        | ano       | ano       | slučování     |
  | rychlé řazení          | quick sort         | O(n log n)                                      | O(n log n)       | O(n²)            | O(log n)        | ne        | ne        | záměna        |
  | řazení výběrem         | selection sort     | O(n²)                                           | O(n²)            | O(n²)            | O(1)            | zprav. ne | ne        | výběr         |
  | Shellovo řazení        | shell sort         | {\displaystyle O(n^{1+{\frac {c}{\sqrt {m}}}})} |                  | O(n log² n)      | O(1)            | ne        | ano       | vkládání      |
  | comb sort              | (hřebenové řazení) | O(n)                                            | O(n log n)       | O(n²)            | O(1)            | ne        | ano       | záměna        |
  | introspektivní třídění | Introsort          | O(n log n)                                      | O(n log n)       | O(n log n)       | O(log n)        | ne        | ?         | záměna, výběr |
  
  | Název              | Název                     | Časová složitost | Dodatečná paměť | Stabilní | Stručný popis metody                                                                      |
  | Název              | Znám jako                 | Časová složitost | Dodatečná paměť | Stabilní | Stručný popis metody                                                                      |
  | ------------------ | ------------------------- | ---------------- | --------------- | -------- | ----------------------------------------------------------------------------------------- |
  | přihrádkové řazení | bucket sort               | 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 |
  | číslicové řazení   | radix sort                | 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 hodnot                    |
  
  
title: Řadicí algoritmus
wikitext: '''Řadicí'''<ref name="Rychlík_Techniky" /><ref name="Satrapa_Perl" /><ref name="Java_bohatstvi_knihoven" /> nebo '''třídicí'''<ref name="Kristoufek_Encyklopedie" /><ref name="Kucera_Kombinatoricke_algoritmy" /><ref name="AC_slovnik_VT" /><ref name="Topfer_Algoritmy" /><ref name="Recepty" /><ref name="Struktura_pocitacu" /><ref name="PLA" /> '''algoritmus''' je [[algoritmus]] zajišťující uspořádání dané sady ([[Pole (datová struktura)|pole]], [[Lineární seznam|seznamu]], [[soubor]]u) [[Záznam (informatika)|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í|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íčů [[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. Podle toho, zda se zachovává pořadí položek se stejným klíčem, rozlišuje algoritmy řazení na [[stabilní řazení|stabilní]] a nestabilní.
  
  == Definice problému ==
  Na vstupu je posloupnost záznamů <math>S = (S_1, S_2, \ldots, S_n)</math>; cílem je najít takovou posloupnost <math>S' = (S_1', S_2', \ldots, S_n')</math>, pro kterou platí dvě základní kritéria:
  # Tato posloupnost je seřazená:
  #: <math>S_1' \le S_2' \le \cdots \le S_n'</math>.
  # Posloupnost <math>S'</math> je [[permutace|permutací]] původní posloupnosti <math>S</math> (obsahuje tedy stejná data, jen v jiném pořadí).
  
  V definici relace [[Částečně uspořádaná množina|uspořádání]] ≤ se přitom bere ohled pouze na klíče příslušných hodnot. V některých [[Programovací jazyk|programovacích jazycích]] ([[Perl]], [[Tcl]], [[Java (programovací jazyk)|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). Tento přístup umožňuje nejen třídění podle klíčů, ale obecněji podle libovolné ohodnocovací funkce.
  
  == Název ==
  {{Podrobně|Třídění}}
  Pro uspořádávání prvků do [[posloupnost]]i podle určitého kritéria se v češtině používá slovo '''řazení'''; v [[Informatika|informatice]] byl zaveden termín '''třídění''' odpovídající anglickému {{Cizojazyčně|en|''sort''}}, {{Cizojazyčně|en|''sorting''}}, který byl takto definován v (již zrušené) názvoslovné normě ČSN&nbsp;36&nbsp;9001. Někteří autoři se domnívají, že pro uspořádávání je vhodnější termín '''řazení''', přičemž '''třídění''' by se mělo používat pro rozdělování sady prvků do několika skupin podle zadaného kritéria, a to bez potřeby určení vzájemného pořadí tříděných prvků. Pouze někteří autoři však pro uspořádávání prvků do posloupnosti termín '''řazení''' skutečně používají.
  
  Pro rozdělování prvků do skupin lze používat jednoznačný název ''[[kategorizace]]'', případně ''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 ==
  Pro seřazení množiny <math>n</math> prvků existuje očividná dolní mez časové [[asymptotická složitost|asymptotické složitosti]] <math>O(n)</math> (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 (matematika)|interval]] v [[přirozené číslo|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 <math>O(n \log n)</math>.
  
  Pro délku pole v násobcích dvou platí:
  
  :<math>O(n \log n) = (\ln(n) / \ln(2) - 1) * n + 1</math>
  
  Pro představu, jaký je rozdíl mezi řazením 1 000 prvků a 1 000 000 prvků:
  
  :<math>n = 2^4 = 16, O(n \log n) = 49 (3*16+1)</math>
  :<math>n = 2^8 = 256, O(n \log n) = 1.793 (7*256+1)</math>
  :<math>n = 2^{10} = 1.024, O(n \log n) = 9.217 (9*1024+1)</math>
  :<math>n = 2^{20} = 1.048.576, O(n \log n) = 19.922.945 (19*1048576+1)</math>
  
  == Klasifikace algoritmů ==
  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ěť|vnější paměti]], např. na [[pevný disk|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á 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í'' třídicí 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.
  
  {| align="right" class="wikitable" style="font-family: monospace"
  |+ style="font-family: sans-serif"| Ukázka řazení
  |- style="font-family: sans-serif"
  ! Výběr !! Vkládaní !! Záměna
  |-
  !colspan="3" align="center"| 614532
  |-
  | 1•64532 || 6•14532 || '''145326'''
  |-
  | 12•6453 || 16•4532 || 14'''325'''6
  |-
  | 123•645 || 146•532 || 1'''324'''56
  |-
  | 1234•65 || 1456•32 || 1'''23'''456
  |-
  | 12345•6 || 13456•2 ||
  |-
  !colspan="3"| 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 [[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ý“ třídicí 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 ===
  {| class="wikitable"
  |+ Přehled běžných univerzálních algoritmů řazení
  !colspan="2"| Název !! colspan="3"| Časová složitost !! rowspan="2"| Dodatečná paměť !! rowspan="2"| Stabilní !! rowspan="2"| Přirozená !! rowspan="2"| Metoda
  |-
  ! Název !! Znám jako !! Minimum !! Průměrně !! Maximum
  |-
  | [[bublinkové řazení]]
  | bubble sort
  | style="background: #dfd" | ''O(n)''
  | style="background: #fdd" | ''O(n²)''
  | style="background: #fdd" | ''O(n²)''
  | style="background: #dfd" | ''O''(1)
  | style="background: #dfd" | ano
  | style="background: #dfd" | ano
  | záměna
  |-
  | [[řazení haldou]]
  | heapsort
  | ''O(n'' log ''n'')
  | style="background: #dfd" | ''O(n'' log ''n'')
  | style="background: #dfd" | ''O(n'' log ''n'')
  | style="background: #dfd" | ''O''(1)
  | ne
  | ne
  | halda, záměna
  |-
  | [[řazení vkládáním]]
  | insertion sort
  | style="background: #dfd" | ''O(n)''
  | style="background: #fdd" | ''O(n²)''
  | style="background: #fdd" | ''O(n²)''
  | style="background: #dfd" | ''O''(1)
  | style="background: #dfd" | ano
  | style="background: #dfd" | ano
  | vkládání
  |-
  | [[řazení slučováním]]
  | merge sort
  | ''O(n'' log ''n'')
  | style="background: #dfd" | ''O(n'' log ''n'')
  | style="background: #dfd" | ''O(n'' log ''n'')
  | ''O''(log n)
  | style="background: #dfd" | ano
  | style="background: #dfd" | ano
  | slučování
  |-
  | [[rychlé řazení]]
  | quick sort
  | ''O(n'' log ''n'')
  | style="background: #dfd" | ''O(n'' log ''n'')
  | style="background: #fdd" | ''O(n²)''
  | ''O''(log ''n'')
  | ne
  | ne
  | záměna
  |-
  | [[řazení výběrem]]
  | selection sort
  | style="background: #fdd" | ''O(n²)''
  | style="background: #fdd" | ''O(n²)''
  | style="background: #fdd" | ''O(n²)''
  | style="background: #dfd" | ''O''(1)
  | zprav. ne
  | ne
  | výběr
  |-
  | [[Shellovo řazení]]
  | shell sort
  | <math>O(n^{1 + \frac{c}{\sqrt m}})</math><ref name="sedgewick96">[[Robert Sedgewick]]: [http://www.cs.princeton.edu/~rs/shell/ ''Analysis of Shellsort and Related Algorithms''], Fourth Annual European Symposium on Algorithms, Barcelona, září 1996</ref>
  |
  | ''O(n'' log² ''n)''<ref name="sedgewick96" />
  | style="background: #dfd" | ''O''(1)
  | ne
  | style="background: #dfd" | ano
  | vkládání
  |-
  | [[comb sort]]
  | (hřebenové řazení)
  | style="background: #dfd" | ''O(n)''
  | style="background: #dfd" | ''O(n'' log ''n'')
  | style="background: #fdd" | ''O(n²)''
  | style="background: #dfd" | ''O''(1)
  | ne
  | style="background: #dfd" | ano
  | záměna
  |-
  |[[Introsort|introspektivní třídění]]
  |Introsort
  |''O(n'' log ''n'')
  |style="background: #dfd" | ''O(n'' log ''n'')
  |style="background: #dfd" | ''O(n'' log ''n'')
  |''O''(log ''n'')
  |ne
  |?
  |záměna, výběr
  |}
  
  {| class="wikitable"
  |+ Běžné algoritmy řazení založené na jiném principu
  !colspan="2"| Název !! rowspan="2"| Časová složitost !! rowspan="2"| Dodatečná paměť !! rowspan="2"| Stabilní !! rowspan="2"| Stručný popis metody
  |-
  ! Název !! Znám jako
  |-
  | [[přihrádkové řazení]]
  | bucket sort
  | ''O(n'' · ''k'')
  | ''O''(2<sup>''k''</sup>)
  | style="background: #dfd" | ano
  | podle hodnoty klíče se data roztřídí do připravených přihrádek seřazených podle velikosti
  |-
  | [[číslicové řazení]]
  | radix sort
  | ''O(n'' · 2<sup>''k''</sup>)
  | ''O(n)''
  | style="background: #dfd" | 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)''
  | style="background: #dfd" | ano
  | umístění do správného pořadí po spočítání četností jednotlivých hodnot
  |}
  
  == Reference ==
  <references>
  <ref name="Rychlík_Techniky">{{Citace monografie
   | příjmení = Rychlík
   | jméno = Jan
   | titul = Programovací techniky
   | vydavatel = KOPP
   | místo = České Budějovice
   | rok = 1995
   | vydání = 2
   | typ vydání = upravené
   | počet stran = 188
   | isbn = 80-85828-05-7
   | kapitola = 6 – Řazení
  }}</ref>
  <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
   | počet stran = 224
   | strany = 66
  }}</ref>
  <ref name="Kristoufek_Encyklopedie">{{Citace monografie
   | 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
   | 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
   | 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
   | 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
   | počet stran = 299
   | strany = 190 (178–213)
  }}</ref>
  <ref name="Recepty">{{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><ref name="Struktura_pocitacu">{{Citace monografie
   | příjmení = Hořejš
   | jméno = Jiří
   | příjmení2 = Brodský
   | jméno2 = Jan
   | příjmení3 = Staudek
   | jméno3 = Jan
   | titul = Struktura počítačů a jejich programového vybavení
   | vydavatel = SNTL, Alfa
   | místo = Praha, Bratislava
   | rok = 1982
   | jazyk = cs
   | počet stran = 446
   | strany = 139–140
  }}</ref><ref name="Java_bohatstvi_knihoven">{{Citace monografie
   | příjmení = Herout
   | jméno = Pavel
   | titul = Java – Bohatství knihoven
   | vydavatel = Kopp
   | místo = České Budějovice
   | rok = 2003
   | jazyk = cs
   | počet stran = 242
   | strany = 65, 101
  }}</ref>
  <ref name="PLA">Martin Mareš, Tomáš Valla, Průvodce labyrintem algoritmů, [http://pruvodce.ucw.cz/ http://pruvodce.ucw.cz/] [http://pruvodce.ucw.cz/static/pruvodce.pdf pdf]
  </ref>
  </references>
  
  == Literatura ==
  * {{en}} [[Donald E. Knuth]]: ''[[The Art of Computer Programming]], Volume 3: Sorting and Searching.'' Second Edition. Reading, Massachusetts: Addison-Wesley, 1998. {{ISBN|0-201-89685-0}}
  
  == Externí odkazy ==
  * {{Commonscat}}
  * {{en}} [http://www.nist.gov/dads/HTML/sort.html Algoritmy řazení ve slovníku algoritmů a datových struktur NIST]
  * [http://tjn.fjfi.cvut.cz/~virius/jera/binary/trideni.htm ''Třídění'' ve výukových materiálech k předmětu Základy algoritmizace]
  * [http://mifeet.alpaka.cz/algo/algorithms.swf Animace některých algoritmů a datových struktur]
  * {{en}} [https://imgur.com/gallery/voutF Sorting Algorithms Visualized]
  {{Autoritní data}}
  
  [[Kategorie:Řadicí algoritmy| ]]
infoboxes: []