Algoritmy triedenia: Rozdiel medzi revíziami

Z Kiwiki
Skočit na navigaci Skočit na vyhledávání
Riadok 19: Riadok 19:
 
;Stabilita: Stabilné triediace algoritmy - súvis s triedením dvojíc kľúč-hodnota, pričom existujú 2 také záznamy, že kľúče sú rovnaké. Stabilný algoritmus nezmení poradie týchto dvojíc vo výsledku.
 
;Stabilita: Stabilné triediace algoritmy - súvis s triedením dvojíc kľúč-hodnota, pričom existujú 2 také záznamy, že kľúče sú rovnaké. Stabilný algoritmus nezmení poradie týchto dvojíc vo výsledku.
 
;Metóda triedenia: vkladanie, výmena, výber, zlúčenie, a pod.
 
;Metóda triedenia: vkladanie, výmena, výber, zlúčenie, a pod.
 +
 +
==Typy triediacich algoritmov==
 +
===Vnútorné triedenie===
 +
===Vonkajšie triedenie===
  
 
==Porovnanie algoritmov==
 
==Porovnanie algoritmov==
Riadok 27: Riadok 31:
 
|-
 
|-
 
! Názov
 
! Názov
 +
! Najlepšie
 
! Priemerne
 
! Priemerne
 
! Najhoršie
 
! Najhoršie
Riadok 33: Riadok 38:
 
|-
 
|-
 
| Bubble sort  
 
| Bubble sort  
−
| <math>n^2</math>
+
| <math>\mathcal{O} (n)</math>
−
| <math>n^2</math>
+
| <math>\mathcal{O} (n^2)</math>
 +
| <math>\mathcal{O} (n^2)</math>
 
| 1
 
| 1
 
| Výmena
 
| Výmena
Riadok 40: Riadok 46:
 
| Gnome sort  
 
| Gnome sort  
 
| ---
 
| ---
−
| <math>n^2</math>
+
| ---
 +
| <math>\mathcal{O} (n^2)</math>
 
| 1
 
| 1
 
| Výmena
 
| Výmena
Riadok 46: Riadok 53:
 
| Shake sort  
 
| Shake sort  
 
| ---
 
| ---
−
| <math>n^2</math>
+
| ---
 +
| <math>\mathcal{O}(n^2)</math>
 
| 1
 
| 1
 
| Výmena
 
| Výmena
 
|-
 
|-
 
| Selection sort  
 
| Selection sort  
−
| <math>n^2</math>
+
| <math>\mathcal{O}(n^2)</math>
−
| <math>n^2</math>
+
| <math>\mathcal{O}(n^2)</math>
 +
| <math>\mathcal{O}(n^2)</math>
 
| 1
 
| 1
 
| Výber
 
| Výber
 
|-
 
|-
 
| Shell sort  
 
| 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, 1996</ref>
 
| ---
 
| ---
−
| <math>n \cdot \log^2 n</math>
+
| <math>\mathcal{O}(n \cdot \log^2 n)</math>
 
| 1
 
| 1
 
| Vkladanie
 
| Vkladanie
 
|-
 
|-
 
| Merge sort  
 
| Merge sort  
−
| <math>n \cdot \log n</math>
+
| <math>\mathcal{O} (n \cdot \log n)</math>
−
| <math>n \cdot \log n</math>
+
| <math>\mathcal{O} (n \cdot \log n)</math>
 +
| <math>\mathcal{O} (n \cdot \log n)</math>
 
| n
 
| n
 
| Zlučovanie
 
| Zlučovanie
 
|-
 
|-
 
| Heap sort  
 
| Heap sort  
−
| <math>n \cdot \log n</math>
+
| <math>\mathcal{O} (n \cdot \log n)</math>
−
| <math>n \cdot \log n</math>
+
| <math>\mathcal{O} (n \cdot \log n)</math>
 +
| <math>\mathcal{O} (n \cdot \log n)</math>
 
| 1
 
| 1
 
| Výber
 
| Výber
 
|-
 
|-
 
| Quick sort  
 
| Quick sort  
 +
| <math>\mathcal{O}(n \cdot \log n)</math>
 
| <math>\mathcal{O}(n \cdot \log n)</math>
 
| <math>\mathcal{O}(n \cdot \log n)</math>
 
| <math>\mathcal{O}(n^2)</math>
 
| <math>\mathcal{O}(n^2)</math>
Riadok 80: Riadok 93:
 
| Delenie
 
| Delenie
 
|}
 
|}
 +
 +
===Popis metód tiedenia===
 +
Existuje niekoľko základných druhov algoritmov univerzálneho vnútorného triedenia. Niektoré z pokročilejšách algoritmov využívajú viacero postupov.
 +
 +
;Triedenie výberom:V súbore sa vždy nájde najmenší zo zostávajúcich položiek a uloží na koniec postupne vytváraného utriedeného súboru.
 +
;Triedenie vkladaním:Zo súboru neusporiadaných dát sa postupne berie položka po položke a vkladá sa na správne miesto v usporiadanom súbore (na začiatku je prázdny).
 +
;Triedenie výmenou:V súbore sa vždy nájde (nejakou metódou závislou na konkrétnom algoritme) nejaká dvojica prvkov, ktorá je v zlom poradí, a tieto prvky sa navzájom zamenia.
 +
;Triedenie zlučovaním:Vstupný súbor sa rozdelí na časti, ktoré sa (typicky rekurzívne) zoradia. Výsledné časti sa potom zlúčia takým spôsobom, aby aj výsledok bol zoradený.
 +
 +
Neexistuje žiaden "dokonalý" triediaci algoritmus, ktorý by bol ideálny pre všetky použitia. Rôzne algoritmy majú rôzne vlastnosti čo sa týka ich očakávané časovej a pamäťovej zložitosti, náročnosti implementácie a ďalších vlastností. Pre konkrétne podmienky sa tak často navrhujú špecifické varianty.
  
 
==Princíp známych triediacich algoritmov==
 
==Princíp známych triediacich algoritmov==
Riadok 90: Riadok 113:
 
===Heap sort===
 
===Heap sort===
 
===Quick sort===
 
===Quick sort===
 +
 +
==Odkazy==
 +
* 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
 +
* [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]
 +
<references />

Verzia zo dňa a času 14:50, 1. február 2010

Imbox draft.png
 Toto je projekt, na ktorom sa ešte stále pracuje!!

Aj keď sú v tomto dokumente použiteľné informácie, ešte nie je dokončený. Svoje návrhy môžete vyjadriť v diskusii o tejto stránke.

Algoritmy a programovanie

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia
 ::Triedenie výmenou
 ::Triedenie vkladaním
 ::Triedenie zlučovaním
 ::Triedenie delením
 ::Triedenie výberom
 ::Triedenie - ostatné princípy

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Triedenie

Triedaci algoritmus je v informatike algoritmus, ktorý zoraďuje prvky zoznamu v určenom poradí. Najpoužívanejšie sú numerické a lexikografické poradie. Efektívne triedenie je dôležité pre optimalizáciu použitia iných algoritmov (ako je napr. vyhľadávanie), ktoré vyžadujú pre svoju správnu funkčnosť utriedené zoznamy. Formálne povedané, výstupné utriedené údaje musia spĺňať dve podmienky:

  1. Prvky vo výstupnom zozname majú neklesajúci trend (každý prvok je väčší alebo rovný ako predchádzajúci prvok)
  2. Výstupom je permutácia vstupných resp. preusporiadanie týchto údajov.

Klasifikácia

Triediace algoritmy môžeme klasifikovať podľa:

Výpočtová zložitosť
(najhoršia, priemerná a najlepšia) pre zoznam s veľkosťou n položiek. Pre typické triediace algoritmy je prijateľná výpočtová zložitosť aspoň O(n.log n) a zlá O(n2). Ideálna zložitosť je O(n). Triediace algoritmy, ktoré používajú iba abstraktnú operáciu porovnania vždy majú priemernú zložitosť aspoň O(n.log n) porovnaní.
Využitie pamäte
(a využívanie ďalších počítačových zdrojov). Niektoré triediace algoritmy sú typu "in-place". To znamená, že im stačí O(1) alebo O(log n) pamäte na triedené položky.
Rekurzia
Niektoré algoritmy sú buď rekurzívne alebo nerekurzívne, niektoré môžu byť implementovateľné oboma spôsobmi (napr. Merge sort).
Stabilita
Stabilné triediace algoritmy - súvis s triedením dvojíc kľúč-hodnota, pričom existujú 2 také záznamy, že kľúče sú rovnaké. Stabilný algoritmus nezmení poradie týchto dvojíc vo výsledku.
Metóda triedenia
vkladanie, výmena, výber, zlúčenie, a pod.

Typy triediacich algoritmov

Vnútorné triedenie

Vonkajšie triedenie

Porovnanie algoritmov

V nasledujúcej tabuľke je n počet záznamov, ktoré majú byť utriedené. Stĺpce "Priemerne" a "najhoršie" hovoria o časovej zložitosti, za predpokladu, že dĺžka všetkých kľúčov je konštantná, a preto všetky porovnania, výmeny a ďalšie potrebné operácie môže vykonať v konštantnom čase. "Pamäť" označuje množstvo pomocnej potrebnej okrem tej, ktorá je potrebná na samotné uloženie poľa ktoré sa bude triediť.

table name
Názov Najlepšie Priemerne Najhoršie Pamäť Metóda tiedenia
Bubble sort [math]\mathcal{O} (n)[/math] [math]\mathcal{O} (n^2)[/math] [math]\mathcal{O} (n^2)[/math] 1 Výmena
Gnome sort --- --- [math]\mathcal{O} (n^2)[/math] 1 Výmena
Shake sort --- --- [math]\mathcal{O}(n^2)[/math] 1 Výmena
Selection sort [math]\mathcal{O}(n^2)[/math] [math]\mathcal{O}(n^2)[/math] [math]\mathcal{O}(n^2)[/math] 1 Výber
Shell sort [math]O(n^{1 + \frac{c}{\sqrt m}})[/math][1] --- [math]\mathcal{O}(n \cdot \log^2 n)[/math] 1 Vkladanie
Merge sort [math]\mathcal{O} (n \cdot \log n)[/math] [math]\mathcal{O} (n \cdot \log n)[/math] [math]\mathcal{O} (n \cdot \log n)[/math] n Zlučovanie
Heap sort [math]\mathcal{O} (n \cdot \log n)[/math] [math]\mathcal{O} (n \cdot \log n)[/math] [math]\mathcal{O} (n \cdot \log n)[/math] 1 Výber
Quick sort [math]\mathcal{O}(n \cdot \log n)[/math] [math]\mathcal{O}(n \cdot \log n)[/math] [math]\mathcal{O}(n^2)[/math] [math]\mathcal{O}\log n[/math] Delenie

Popis metód tiedenia

Existuje niekoľko základných druhov algoritmov univerzálneho vnútorného triedenia. Niektoré z pokročilejšách algoritmov využívajú viacero postupov.

Triedenie výberom
V súbore sa vždy nájde najmenší zo zostávajúcich položiek a uloží na koniec postupne vytváraného utriedeného súboru.
Triedenie vkladaním
Zo súboru neusporiadaných dát sa postupne berie položka po položke a vkladá sa na správne miesto v usporiadanom súbore (na začiatku je prázdny).
Triedenie výmenou
V súbore sa vždy nájde (nejakou metódou závislou na konkrétnom algoritme) nejaká dvojica prvkov, ktorá je v zlom poradí, a tieto prvky sa navzájom zamenia.
Triedenie zlučovaním
Vstupný súbor sa rozdelí na časti, ktoré sa (typicky rekurzívne) zoradia. Výsledné časti sa potom zlúčia takým spôsobom, aby aj výsledok bol zoradený.

Neexistuje žiaden "dokonalý" triediaci algoritmus, ktorý by bol ideálny pre všetky použitia. Rôzne algoritmy majú rôzne vlastnosti čo sa týka ich očakávané časovej a pamäťovej zložitosti, náročnosti implementácie a ďalších vlastností. Pre konkrétne podmienky sa tak často navrhujú špecifické varianty.

Princíp známych triediacich algoritmov

Bubble sort

Selection sort

Shake sort

Shell sort

Merge sort

Heap sort

Quick sort

Odkazy

  1. ↑ Robert Sedgewick: Analysis of Shellsort and Related Algorithms, Fourth Annual European Symposium on Algorithms, Barcelona, 1996
Zdroj: „http://www.kiwiki.info/index.php?title=Algoritmy_triedenia&oldid=1736“