Parallelize selection sort using OpenMP

Question

I need to implement an algorithm for parallel selection sort using OpenMP, although I couldn't find much information either on SO or on the Internet in general.

Here's my serial code:

void selectionsort(int* arr, int size)
{
    for (int i = size - 1; i > 0; --i)
    {
        int max = i;
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] > arr[max])
            {
                max = j;
            }
        }
        swap(arr[i], arr[max]);
    }
}

---

Does anybody know how to implement this type of sorting algorithm in parallel? At least in theory?

Answer 1

Since the outer for can't be parallelized due to the constant changes in the array, we need to parallelize the inner for.

So we need to use the max reduction, but since we just don't need the maximum value we also need the index of this maximum value, we need to declare a new reduction (Only available in OpenMP 4.0) that receives a struct, here it is fully functional:

#include <stdio.h>
#include <omp.h>

struct Compare { int val; int index; };
#pragma omp declare reduction(maximum : struct Compare : omp_out = omp_in.val > omp_out.val ? omp_in : omp_out)

void selectionsort(int* arr, int size)
{
    for (int i = size - 1; i > 0; --i)
    {
        struct Compare max;
        max.val = arr[i];
        max.index = i;
        #pragma omp parallel for reduction(maximum:max)
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] > max.val)
            {
                max.val = arr[j];
                max.index = j;
            }
        }
        int tmp = arr[i];
        arr[i] = max.val;
        arr[max.index] = tmp;
    }
}

int main()
{
        int x[10] = {8,7,9,1,2,5,4,3,0,6};
        selectionsort(x, 10);

        for (int i = 0; i < 10; i++)
                printf("%d\n", x[i]);
        return 0;
}