Třídící algoritmy

Bubblesort

  • Algoritmus opakovaně prochází seznam, přičemž porovnává každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků běží do té doby, dokud není seznam seřazený.
  • Pro praktické účely je neefektivní, využívá se hlavně pro výukové účely či v nenáročných aplikacích.
  • Algoritmus pracuje lokálně (nevyžaduje pomocnou paměť), je stabilní (prvkům se stejným klíčem nemění vzájemnou polohu) a patří mezi přirozené řadicí algoritmy (částečně seřazený seznam zpracuje rychleji než neseřazený).
  • Časová složitost je n2.

Selectsort

  • Algoritmus nejprve vyhledá mezi daty prvek s nejmenší hodnotou. Tento prvek zamění s prvkem na první pozici.
  • Na první pozici se nyní nachází správný prvek, zbytek dat se uspořádá opakováním těchto kroků pro zbylých n-1 prvků, dokud je n > 1.
  • Časová složitost je n2.

Insertsort

  • Algoritmus rozdělí množinu prvků na setříděnou část (1 prvek) a nesetříděnou část (zbytek). Z nesetříděné části pak zařazuje prvky do setříděné tak, aby zůstala setříděná.
  • Algoritmus postupuje následovně:
  • První prvek ponechá na místě.
  • Vezme druhý prvek a porovná ho s prvním. Je-li menší, zařadíme ho na první místo a první prvek posuneme, jinak je ponecháme na místě.
  • Vezmeme třetí prvek a porovnáme jej s prvními dvěma prvky. Je-li menší než některý z nich, zařadíme jej na odpovídající pozici a následující prvky podle potřeby posuneme. Jinak je ponecháme na původních místech.
  • Obdobně postupujeme i s ostatními prvky.
  • Časová složitost je n2.

Quicksort

  • Princip algoritmu:
  • Zvolme v zadaném poli prvek a říkejme mu pivot. Nyní můžeme pole přeházet tak, aby na jedné straně byly prvky menší než pivot, na druhé větší než pivot a pivot samotný byl umístěn přesně mezi těmito částmi.
  • Tento postup můžeme zopakovat pro obě rozdělené části (bez pivota, ten je již umístěn na správném místě).
  • Proceduru opakujeme tak dlouho, dokud nedojde k seřazení pole (nenarazíme na podproblémy jednotkové velikosti, které jsou vyřešeny triviálně).
  • Časová složitost je průměrně n log2⁡ 2 v nejhorším případě však až n2.

Heapsort

  • Vlastnosti haldy: každý potomek je v haldě menší než jeho otec. (V minimální haldě naopak větší.)
  • Princip spočívá v opakovaném odebírání vrcholu haldy a jejímu následnému znovuvytvoření.
  • Z pole vytvoříme haldu.
  • Odtrhneme vrchol (největší či nejnižší prvek dle způsobu řazení).
  • Vrchol prohodíme s posledním prvkem haldy a haldu zmenšíme o 1.
  • Opravíme haldu, aby znovu splňovala požadované vlastnosti.
  • Tyto kroky opakujeme, dokud má halda prvky.
  • Časová složitost je n log⁡2, je ovšem o něco pomalejší než Quicksort.

Hodnocení referátu Třídící algoritmy

Líbila se ti práce?

Podrobnosti

  20. listopad 2017
  124×
  395 slov

Komentáře k referátu Třídící algoritmy