Laboratorul 3 - Algoritmi paraleli de sortare și de căutare

Introducere

În acest laborator, vom discuta despre câteva exemple de algoritmi paraleli de sortare.

📄️ Odd-even transposition sort (OETS)

Unul din cei mai cunoscuți (chiar dacă nu neapărat eficienți) algoritmi de sortare este bubble sort. Acesta funcționează pe baza următorului pseudocod:

📄️ Shear sort

Un alt exemplu de algoritm de sortare care a fost conceput pentru sisteme multi-procesor unde un procesor este conectat doar la o parte din celelalte procesoare este shear sort (cunoscut de asemenea ca row-column sort sau snake-order sort), care presupune că lucrăm pe procesoare conectate într-o formă de matrice. Astfel, un procesor poate să comunice cu vecinii din stânga, din dreapta, de sus și de jos. Dacă ne imaginăm deci că procesoarele sunt așezate într-o matrice, cele două faze ale algoritmului shear sort sunt următoarele:

📄️ Merge sort

Merge sort (sau sortarea prin interclasare) este un algoritm de sortare de tip divide et impera care presupune următorii pași generali:

📄️ Căutarea binară paralelă

Algoritmul de căutare binară paralelă se bazează pe împărțirea secvenței în care se face căutarea în P subsecvențe de aceeași lungime. La fiecare pas, fiecare din cele P procesoare verifică dacă o valoare x se află în subsecvența atribuită procesorului respectiv, prin compararea valorii lui x cu valorile aflate pe pozițiile start și end, care marchează capetele subsecvenței unui procesor.

📄️ Exerciții

1. Pornind de la implementarea secvențială a algoritmului bubble sort aflată în fișierul oets.c din scheletul de laborator, implementați și paralelizați algoritmul odd-event transposition sort.