• Předloha: pdv-05sort.zip
• Do BRUTE odevzdávejte zip archiv obsahující soubor sort.cpp.

S řadícími algoritmy jste se již setkali nejenom na cvičení z PDV a ALG, ale jistě i ve své vlastní praxi. Úloha řazení se totiž velice často objevuje jako podúloha v různých algoritmech. Pro efektivní řazení je důležité vybrat správný řadící algoritmus. Na cvičení jste měli možnost zrychlit pomocí paralelizace několik algoritmů, které jsou dobré především pro numerické řazení. V rámci této domácí úlohy si zkusíte naimplementovat paralelní verzi řadícího algoritmu Radix sort, který použijete na lexikografické seřazení řetězců stejné délky.

Vaším úkolem je co nejrychleji lexikograficky seřadit vektor řetězců. Řetězce mají stejnou délku, jsou velmi krátké a obsahují náhodné znaky z omezené abecedy. Pro takovouto datovou sadu je vhodné použít algoritmus Radix sort. Tento řadící algoritmus již také znáte z předmětu ALG.

Jelikož jsou všechny řetězce stejně dlouhé, nemusíte v tomto případě ošetřovat speciální případy, kdy řetězce nemají stejnou velikost. Než se pustíte do samotné implementace, zkuste se nejdříve zamyslet nad tím, která z verzí Radix sortu (popsaných například zde) je pro daná data (krátké řetězce) na paralelizaci nejvhodnější.

Vaším úkolem je doimplementovat tělo metody radix_par v souboru sort.cpp. Tato metoda má za úkol správně seřadit vektor pointerů na řetězce podle lexikografického pořadí řetězců. Doporučujeme si před samotnou implementací projít sort.h a main.cpp, kde najdete další nápovědu a vysvětlení dílčích částí kódu.