Row-Column Sort

Row Column Sort este o metoda de sortare in paralel, cu o complexitate aproape de complexitatea medie pentru o sortare: n*log(n).
Ideea este ca vectorul de elemente pentru sortat trebuie pus intr-o matrice (completata cu elemente fara valoare la nevoie), dupa care se aplica un numar de 2*log2(n) pasi dupa cum urmeaza:
Pasul impar: se sorteaza liniile (in mod independent), liniile impare se sorteaza crescator, cele pare descrescator
Pasul par: se sorteaza coloanele (independent), toate crescator de sus in jos
In final, matricea se parcurge de la coltul stanga sus in mod serpuit pana la coltul dreapta jos.

=======

#include "stdio.h"
#include "omp.h"
#include "math.h"
#include "stdlib.h"

int n, a[9] = {2,7,1,0,8,5,10,17,2};
int dim;
int mat[3][3];

void sort_linii (int i, int mod) {

int ok=0, k,aux;
if(mod == 1) {
while (!ok) {
for(k=0; k<=dim-2; k++) {
ok = 1;
if(mat[i][k]=>mat[i][k+1]+1) {
//printf("1)schimb %d cu %d \n", mat[i][k], mat[i][k+1]);
ok = 0;
aux = mat[i][k];
mat[i][k] = mat[i][k+1];
mat[i][k+1] = aux;
}
}
}
}
else {
while (!ok) {
for(k=0; k<=dim-2; k++) {
ok = 1;
if(mat[i][k]<=mat[i][k+1]-1) {
//printf("2)schimb %d cu %d \n", mat[i][k], mat[i][k+1]);
ok = 0;
aux = mat[i][k];
mat[i][k] = mat[i][k+1];
mat[i][k+1] = aux;
}
}
}
}
}

void sort_coloane (int j) {

int k, ok = 0;
while (!ok) {
for(k=0; k<=dim-2; k++) {
ok = 1;
if(mat[k][j]=>mat[k+1][j]+1) {
//printf("!!schimb %d cu %d \n", mat[k][j], mat[k+1][j]);
ok = 0;
int aux = mat[k][j];
mat[k][j] = mat[k+1][j];
mat[k+1][j] = aux;
}
}
}
}

void afisare() {
int i,j;
printf("\n");
for(i=0;i<=dim-1;i++) {
for(j=0;j<=dim-1;j++)
printf("%d ", mat[i][j]);
printf("\n");
}
}

int main () {

n = 9 ;
dim = 3;
int pas, i,j,aux;
i=0; j=0,pas=0;
do {
mat[i][j] = a[pas];
j++;
if(j==dim) {
j = 0; i++;
}
pas++;
} while(pas<=n-1);

afisare();

int final = log(n);
final = final/log(2)*2;
//printf("final=%d\n",final);
#pragma omp parallel shared(mat,dim,final) private(pas)
for(pas=0; pas<=n-1; pas++) {

if(pas%2==1) { //impar, sortez liniile
#pragma omp for private(i)
for(i=0; i<=dim-1; i++) //pt fiecare linie
if(i%2==1) {
sort_linii(i,1); //crescator
//afisare();
}
else {
sort_linii(i,0); //descrescator
//afisare();
}
}
else { //par, sortez coloane
#pragma omp for private(j)
for(j=0;j<=dim-1;j++) {
sort_coloane(j); //toate de sus in jos crescator
//afisare();
}
}
#pragma omp single
afisare();
}

printf("\nSIR SORTAT:\n");
i=0;
do {
if(i<=dim-1)
for(j=dim-1; j>=0; j--)
printf("%d ", mat[i][j]);
i++;
if(i<=dim-1)
for(j=0;j<=dim-1; j++)
printf("%d ", mat[i][j]);
i++;
} while(i<=dim-1);

printf("\n");
return 0;
}