Odd-even transposition sort

Cílem projektu bylo implementovat paralelní algoritmus Odd-even transposition sort pro seřazení posloupnosti čísel.

Popis algoritmu

Odd-even transposition sort je řadicí algoritmus podobný bubble sortu. Díky své konstrukci je vhodný k paralelnímu běhu. Vstupem algoritmu je vektor hodnot, výstupem seřazený vektor hodnot. Nejdříve všem procesorům přiřadíme postupně n řazených hodnot vi (i = 1, …, n). Algoritmus probíhá cyklicky ve dvou krocích. V prvním kroku se pracuje s lichými procesory, ve druhém kroku se sudými procesory.

V každém kroku procesor porovná svoji hodnotu vi s hodnotou procesoru vpravo od sebe vi+1 (např. svého následovníka při použití jednosměrně vázaného seznamu) a v případě, že je vi > vi+1, dojde k prohození obou hodnot. Stejným způsobem se postupuje i ve druhém kroku se sudými procesory. Tento postup nám zaručí, že nikdy k jednomu procesoru nepřistupuje více jiných současně. Maximálně po n krocích je posloupnost seřazena.

Časová složitost

Při každém ze dvou kroků se paralelně provádí jedno porovnání a dva přenosy. Tyto operace jsou nezávislé na počtu prvků, jejich provedení má konstantní časovou složitost. Celkem se provede maximálně n kroků, takže složitost algoritmu je lineární.

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.