使用 OpenMP 并行化选择排序 [英] Parallelize selection sort using OpenMP

问题描述

我需要使用 OpenMP 实现并行选择排序算法，尽管我在 SO 或 Internet 上找不到太多信息.

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.

这是我的序列号:

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?

推荐答案

由于数组不断变化，外部for无法并行化，需要对内部for进行并行化.

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

所以我们需要使用最大归约，但由于我们不需要最大值，因此我们还需要这个最大值的索引，我们需要声明一个新的归约(仅在 OpenMP 4.0 中可用)，它接收一个struct，这里功能齐全:

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;
}

这篇关于使用 OpenMP 并行化选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！