Sortare OETS

OETS (odd even transposition sort) este o versiune paralela a metodei bulelor (Bubble Sort). Se utilizeaza n procesoare, unde n este numarul de elemente de sortat, fiecare numar fiind distribuit unui procesor. Algoritmul are n pasi si functioneaza astfel:
* in pasii impari, fiecare procesor cu numar de ordine impar comunica cu procesorul din dreapta; cele doua procesoare isi trimit unul altuia numerele si, daca este necesar, acestea sunt interschimbate
* in pasii pari, fiecare procesor cu numar de ordine par comunica cu procesorul din dreapta, executand operatii similare cu cele din pasii pari

Operatiile fiecarui pas se executa in paralel, insa pasii se desfasoara unul dupa altul (gen bariera). Numarul maxim de pasi este n, complexitatea finala fiind O(n), dat fiind ca avem n procesoare.

#include "stdio.h"

#include "omp.h"

int main () {

int n = 6, a[6] = {2,7,1,0,8,5};

int pas, i, aux;

#pragma omp parallel shared(a,n) private(pas)

for(pas=0; pas<=n-1; pas++) {

if(pas%2==1) { //impar

#pragma omp for private(i,aux)

for(i=0; i<=n-2; i+=2)

if(a[i]>a[i+1]) {

aux = a[i];

a[i] = a[i+1];

a[i+1] = aux;

}

}

else { //par

#pragma omp for private(i,aux)

for(i=1;i<=n-2;i+=2)

if(a[i]>a[i+1]) {

aux = a[i];

a[i] = a[i+1];

a[i+1] = aux;

}

}

}

for(i=0;i<=n-1;i++)

printf("%d ", a[i]);

printf("\n");

return 0;

}