07_razeni

• výhoda 

• extrémy velmi rychle přemístěny na odpovídající stranu 

pole 

• poslední iterace algoritmu  

přesouváme naprosté minimum prvků 

Shell sort 

Bucket sort 

• podle klíče se rozřadí do sekcí 

• například podle hodnoty v nejvyšším řádu 

• hodnoty v sekci se seřadí nějakým z řadících algoritmů 

• podle charakteru dat možno pro každou sekci jiný algoritmus 

• hodnoty se nakopírují do výsledného pole 
• musíme dále řadit? 

• každá sekce pokrývala určitý rozsah 
• rozsahy se nepřekrývaly 
• není nutné další zpracování 

• vhodné pro paralelní zpracování 

co bucket to vlákno 

• Složitost O(m*C(n/m)) 

• C(n) – složitost vnitřního třídícího algoritmu 

Counting sort 

• O(n+k) 

• n- počet prvků 
• k - počet různých prvků 

• vhodný pro velká pole s opakujícími se hodnotami 
• dají se řadit jen diskrétní hodnoty 
• algoritmus: 

• nejprve se zjistí četnost jednotlivých hodnot v poli 
• vytvoří se pole posledních indexů 

• tj. hodnota značí poslední index s danou hodnotou 

• pole četností a výskytů se použije pro vytvoření seřazeného 

pole 

Counting sort 

Vstupní pole 

9 

6 

6 

3 

2 

0 

4 

2 

9 

3 

Výčet prvků 

0 

1 

2 

3 

4 

5 

6 

7 

8 

9 

Pole četností 

1 

0 

2 

2 

1 

0 

2 

0 

0 

2 

Pole výskytů 

0 

0 

2 

4 

5 

5 

7 

7 

7 

9 

Seřazené pole 

0 

2 

2 

3 

3 

4 

6 

6 

9 

9 

Radix sort 

• řazení řetězců totožné délky 
• přímo z definice stabilního řazení 

• postupně jdeme znak po znaku a řadíme 

• algoritmus 

• vezmi první znaky všech řetězců 
• řetězce seřaď podle tohoto znaku 

• volá jiný stabilní algoritmus 
• často Counting sort 

• na řetězce se stejným prvním znakem zavolej tento