Jednoduché a pokročilejší řadící techniky a jejich srovnání

Question 1

Typy řazení

Answer 1

Řazení výběrem: najde se vždy nejmenší ze zbývajících prvků a uloží se na konec už seřazených.

Řazení vkládáním: z neseřazené množiny se postupně bere prvek po prvku a vkládá se na správné místo přičemž začáteční množina už seřazených je prázdná.

Řazení záměnou: v množině najdeme vždy dvojici, která je ve špatném pořadí a přehodíme ji.

Řazení slučováním: vstupní množinu rozdělíme na části, které se seřadí. Tyto seřazené části se poté sloučí způsobem, který vede k seřazení.

Question 2

Stabilita řazení

Answer 2

Dělíme na stabilní a nestabilní.
Vstupní data můžou obsahovat několik prvků se stejnou hodnotou. Stabilní algoritmus při řazení zachovává vzájemné pořadí položek se stejnou hodnotou a u nestabilního jejich zachování není zaručeno. Stabilní je vhodné využívat při řazení dle dvou parametrů.

Když je řazen seznam osob dle křestního jména a poté příjmení, stabilní algoritmus vrátí výsledky v očekávaném pořadí (Adam Novák, Karel Novák, Václav Novák). Nestabilní může výsledky prvního řazení přeházet (Václav Novák, Adam Novák, Karel Novák).

Question 3

Bubble sort

Answer 3

Je jednoduchý stabilní řadící algoritmus se složitostí O(𝑛^2).
Porovnávají se dva sousední prvky, pokud je nižší číslo nalevo od vyššího, tak se prohodí. tak probublávají postupně dokud se neseřadí. Pokud jsou čísla v průběhu už správně seřazena, tak je neprohodí, ale postupuje dále.

Question 4

Insertion sort

Answer 4

Je jednoduchý stabilní řadící algoritmus se složitostí O(𝑛^2). Množina prvků je rozdělena na seřazenou (na počátku prázdnou) a neseřazenou část. Prvky se jeden po druhém přesouvají z neseřazené části a jsou umísťovány do seřazené na správné místo.

Question 5

Selection sort

Answer 5

Je jednoduchý nestabilní řadící algoritmus se složitostí O(𝑛^2 ). Množina prvků je rozdělena na seřazenou (na počátku prázdnou) a seřazenou část. V neseřazené části je nalezen prvek s nejvyšší hodnotou a je umístěn do seřazené části. Poté je nalezen druhý největší prvek a je umístěn do seřazené.

Question 6

Heap sort

Answer 6

Je nestabilní složitý řadící algoritmus se složitostí O(𝑛 log 𝑛). Je jeden z nejefektivnějších řadících algoritmů.

Funguje na principu prioritní fronty (stromová struktura). Nejprve je prvky naplněn binární strom. Z tohoto stromu je vytvořena binární halda průchodem BFS. Z binárního stromu je kořen umístěn do množiny seřazených prvků; kořen stromu je umístěn do seřazené části, na jeho místo je umístěn nejnižší list a strom je znovu seřazen. Nový kořen stromu je znovu umístěn do seřazené části a takto se algoritmus opakuje dokud ve stromu zbývají uzly.

Udělej z pole max-heap (největší prvek je nahoře).
Opakuj: vyměň první a poslední prvek, zmenši haldu, obnov max-heap.
Pokračuj, dokud není vše seřazené.

Question 7

Quick sort

Answer 7

Je nestabilní složitý řadící algoritmus se složitostí O(𝑛^2), resp. Θ(𝑛 log 𝑛).

1) Vyber prvek jako pivot (např. prostřední, první, poslední nebo náhodný prvek).
2) Rozděl pole na dvě části – vlevo budou prvky menší než pivot, vpravo větší.
3) Rekurzivně použij Quick Sort na obě části.