Algoritmy a dátové štruktúry prednáška 11

Zhrnutie prednášky

Prednáška nadväzuje na dolný odhad n log n pre triedenie porovnávaním z minulej prednášky a ukazuje, že countsort tento odhad dokáže prekonať, keď je rozsah hodnôt kľúča malý. Zavádza sa pojem stability triedenia a na príkladoch countsortu, mergesortu, heapsortu a quicksortu sa analyzuje, ktoré algoritmy sú stabilné, pričom sa ukazuje aj univerzálny spôsob, ako ľubovoľné triedenie spraviť stabilným priradením pôvodného indexu ku kľúču, vrátane implementácie treesortu pomocou asociatívnej mapy nad červeno-čiernym stromom. Ťažiskom prednášky je radix sort - najprv na desiatkových kľúčoch (rodné čísla), následne so zvolením optimálnej väčšej bázy, napríklad 2^16, pre efektívne triedenie 64-bitových celých čísel v prakticky lineárnom čase. Ukazuje sa, že rovnaký princíp funguje aj na reálne čísla typu float či double vďaka vhodnému binárnemu kódovaniu podľa štandardu IEEE 754. Na záver sa rieši triedenie reťazcov pomocou dátovej štruktúry trie (písmenkový strom), ktorá umožňuje vložiť aj vypísať usporiadané reťazce v čase lineárnom vzhľadom na celkovú dĺžku vstupu.

• Stabilita triedenia a jej definícia
• Stabilita countsortu, mergesortu, heapsortu a quicksortu
• Prevod ľubovoľného triedenia na stabilné pomocou pôvodných indexov
• Treesort pomocou asociatívnej mapy a červeno-čierneho stromu
• Radix sort na desiatkových kľúčoch a voľba optimálnej bázy 2^16 pre 64-bitové čísla
• Triedenie reálnych čísel float a double pomocou binárnej reprezentácie
• Trie (písmenkový strom) na lineárne triedenie reťazcov

Zhrnutie pripravené s pomocou AI z prepisu videa.