Heap sort

Průběh cvičení

Zopakovali jsme si, co to je max-halda a jak jejích vlastností využívá heap sort k rychlejšímu třídění.

Ukázali jsme si, jak opravit haldu se špatným vrcholem, když je zbytek struktury v pořádku (max-heapify). Poté jsme se podívali, jak tohoto postupu lze využít pro vybudování haldy z libovolného pole (build-max-heap) a nakonec jakým způsobem tyto myšlenky kombinuje heapsort při třídění polí.

Zamysleli jsme se i nad složitostí všech těchto procedur i celého heap-sortu. Vše jsme si ukázali na příkladech.

Úterní skupina

Probrali jsme i counting sort a tím dohnali ztracené cvičení.

Úkol

1. (Všichni) Implementujte heap sort v jazyce C.
2. (Úterý) Implementujte counting sort v jazyce C.