Minimum extraction sort

Cílem projektu bylo implementovat paralelní algoritmus Minimum extraction sort pro získání seřazené posloupnosti.

Popis algoritmu

Algoritmus pracuje nad binárním stromem, v jehož listech jsou na počátku uloženy řazené hodnoty. Všechny nelistové uzly obsahují procesor, který je schopen porovnat hodnoty potomků a menší z nich uložit do svého uzlu. Hodnota menšího z potomků se tedy posunuje stromem vzhůru, až dosáhne kořene – po (log n) + 1 krocích. Následně do kořenového uzlu postupují další nejnižší hodnoty – vždy ve dvou krocích – nejprve se hodnota dostane do kořene, a pak je z ní odstraněna do pole s výsledkem. Jde o binární strom, tzn. počet listů je vždy mocninou dvojky. Abychom mohli řadit i hodnoty, jejichž počet není mocninou dvojky, musíme si u zbývajících listů poznamenat, že jsou prázdné. U každého uzlu si tedy pamatujeme hodnotu, kterou obsahuje, a také proměnnou, ve které uchováváme (ne)prázdnost uzlu.

Časová složitost

Nejmenší hodnota dosáhne kořene stromu po (log n) + 1 kroku. Následně je zbývajících n – 1 hodnot ze stromu „odstraněno“ v pořadí od nejmenší vždy po dvou krocích – prvním je doručení hodnoty do kořene, druhým je odstranění hodnoty z kořene a uložení do výsledného pole.

Celkový počet kroků je tedy 2 * (n – 1) + (log n) + 1 = 2 * n + log n – 1. Dominantní složkou složitosti je n, jde tedy o algoritmus s lineární časovou složitostí.

Implementace

Program je vytvořen v programovacím jazyce PM2, který je určen pro realizaci paralelních výpočtů na jednoprocesorových systémech.

Ke stažení

Projekt je zveřejněn tak, jak je, bez jakýchkoliv záruk. Projekt byl vypracován při studiu na Fakultě informačních technologií VUT v rámci předmětu Paralelní a distribuované algoritmy.