Skip to content

Latest commit

 

History

History
158 lines (101 loc) · 8.19 KB

06_problematika_razeni.md

File metadata and controls

158 lines (101 loc) · 8.19 KB
Raw

6. Problematika řazení

Problematika řazení – základní algoritmy a jejich složitost.

Formální definice

A ... abeceda, nad kterou je dáno řazení

a_{i_1}, a_{i_2}, \ldots , a_{i_n} ... posloupnost (slovo) nad abecedou A

Cílem je nalézt permutaci \pi \in S_n takovou, že posloupnost a_{\pi(i_1)} a_{\pi(i_2)} \ldots a_{\pi(i_n)} je setříděná, tj. a_{\pi(i_j)} \leq a_{\pi(i_{j+1})}

Vlastnosti

  • na místě - pro řazení se nepoužívá žádná další datová struktura (např. další pole)
  • stabilní - v seřazené posloupnosti je zachováno pořadí rovnocenných prvků
  • přirozený - rychleji zpracuje (částečně) seřazenou množinu, u nepřirozeného to nehraje roli
  • interní - všechna data jsou k dispozici v paměti
  • externí - další prvky přichází v průběhu řazení
  • složitost
  • časová složitost (dále jako f(n)) viz okruh 7 - Časová náročnost algoritmů
  • paměťová složitost

Rozlišujeme

a. Postupné rozšřování setříděné části

  • Selection sort f(n) \in \mathcal{O}(n^2)
  • Insertion sort f(n) \in \mathcal{O}(n^2)

b. Záměnu dvojic po sobě jsdoucích prvků

  • Bubble sort f(n) \in \mathcal{O}(n^2)
  • Sinking sort f(n) \in \mathcal{O}(n^2)
  • Shaker f(n) \in \mathcal{O}(n^2)

c. Divide and Conquer

  • Merge sort f(n) \in \mathcal{O}(n \cdot \log_2 n)
  • Quick sort f(n) \in \mathcal{O}(n \cdot \log_2 n)

d. Sorting by distribution

  • Radix sort
  • Bucket sort
Anglicky Česky Nejlepší Průměrně Nejhorší Dodatečná pamět Stabilní Přirozené Metoda
Selection sort Řazení výběrem O(n²) O(n²) O(n²) O(1) zprav. ne ne výběr
Insertion sort Řazení vkládáním O(n) O(n²) O(n²) O(1) ano ano vkládání
Bubble sort Bublinkové řazení O(n) O(n²) O(n²) O(1) ano ano záměna
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

Sorting Algorhitm Animations

Rozbor mnoha algoritmu

a) Rozšřování setříděné části

Selection Sort

V každém kroku vybere z nesetříděné části nejmenší prvek a vloží nakonec setříděné části.

Příklad:

  • 6, 5, 2, 4, 8
  • 2, 5, 6, 4, 8
  • 2, 4, 6, 5, 8
  • 2, 4, 5, 6, 8
  • 2, 4, 5, 6, 8
  • 2, 4, 5, 6, 8

f(n) \in \mathcal{O}(n^2)

f(n) = f(n - 1) + (n - 1)

Insertion Sort

Vyberu první prvek z nesetříděné části a zařadím ho na správné místo v setříděné části.

Příklad:

  • 6, 5, 2, 4, 8
  • 6, 5, 2, 4, 8
  • 5, 6, 2, 4, 8
  • 2, 5, 6, 4, 8
  • 2, 4, 5, 6, 8
  • 2, 4, 5, 6, 8

v nejhorším případě ... f(n) \in \mathcal{O}(n^2)

pro téměř seřazenou posloupnost ... f(n) \in \mathcal{O}(n)

b) Záměna dvojic mimo pořadí

Bubble Sort

Nesetříděnou posloupnost procházím shora dolů a porovnávám dvojice po sobě jdoucích prvků; dvojice mimo pořadí zaměním. Tím se na přední pozici dostane vždy nejmenší prvek.

Příklad:

  • 6, 5, 2, 4, 8
  • 2, 6, 5, 4, 8
  • 2, 4, 6, 5, 8
  • 2, 4, 5, 6, 8
  • 2, 4, 5, 6, 8
  • 2, 4, 5, 6, 8

f(n) \in \mathcal{O}(n^2)

Sinking Sort

Stejné jako bubble sort, akorát procházím od zdola nahoru.

Shaker Sort

Kombinace Bubble Sort a Sinking Sort. Střídá se procházecí pořadí.

c) Divide and conquer

Merge sort

Vstupní posloupnost se rekurzivně dělí na dvě poloviny až jsou poslopnosti délky jedna. Následuje zpětný chod, tj. sestavení setříděné posloupnosti. Při zpětném chodu se sloučí dvě fronty do jedné (nejmenší prvek je vždy na začátku jedné ze dvou front).

Ukázka merge sort

Ukázka algoritmu merge sort

f(n) = 2f(\frac{n}{2}) + n

f(n) \in \mathcal{O}(n \cdot \log_2 n)

Quick sort

Zvolíme tzv. pivota a posloupnost rozdělíme na dvě části. Jedna z nich obsahuje prvky menší nebo rovny pivotu a druhá obsahuje prvky větší než pivot. Na tyto dvě posloupnosti se rekurzivně aplikuje stejná operace.

Ukázka algoritmu quick sort

Ukázka algoritmu quick sort

složitost v nejhorším případě ... f(n) \in \mathcal{O}(n^2)

průměrná složitost ... f(n) \in \mathcal{O}(n \cdot \log_2 n)