Counting sort a Radix sort

Průběh cvičení

Podívali jsme se na první dva třídící algoritmy využívající jiné znalosti než porovnávání hodnot v poli.

Radix sort

Řekli jsme si, co je to stabilní třídící algoritmus, proč nás tato vlastnost zajímá a které z nám známých algoritmů ji splňují. Zopakovali jsme si myšlenku Radix sortu a zkusili si jej na příkladě. Nakonec jsme krátce bavili o jeho složitosti.

Counting sort

Ukázali jsme si Counting sort pro třídění pole přirozených čísel omezených shora. Rozebrali jsme si jednotlivé kroky v jeho pseudokódu a ukázali si příklad. Nakonec jsme krátce bavili o jeho složitosti.

Zápočtová úloha

Zadání je na webu.

Úkoly na hodině

1. Implementujte Radix sort v jazyce C.
2. Implementujte Counting sort v jazyce C.