Parallel qsort using openMP

Question

I'm trying to parallelize qsort() function in c++ with openMP, but I have some problems. For of all, for a high number of element to sort (ex: V=1000) qsort doesn't work at all, I never exit this function (infinite loop). Then, I notice that my parallel version of qsort is much slower then the serial one. Anyone could help me? Here the code: https://dpaste.de/EaH0.

here the average of time elapsed where kruscalP is the parallel version: thanks

Answer 1

You have multiple race conditions in your code when you write to A, exch0, and exch1 which are all shared. Not only can this hurt performance it likely will give the wrong result. Unfortunately, you have to use a critical section to fix this which will also likely hurt performance but at least it will give the right result.

#pragma omp for    
for (i = 0; i < N-1; i += 2) {
    #pragma critical
    {
        if (A[i].weight > A[i+1].weight) {
            temp = A[i];
            A[i] = A[i+1];
            A[i+1] = temp;
            exch0 = 1;
        }
    }
}

The same applies to the next for loop. If you want to do this efficiently you have to change your algorithm. Maybe consider merge sort.