使用OpenMP实现并行冒泡排序

Question

我写了一个C++代码实现冒泡排序算法，但不知道如何使用OpenMP并行化它。请帮助我……以下是代码：

#include "stdafx.h"    
#include <iostream>
#include <time.h>
#include <omp.h>
using namespace std;

int a[40001];
void sortArray(int [], int);
int q=0;

int _tmain(int argc, _TCHAR* argv[])
{   
int x=40000;
int values[40000];
for (int i=0;i<x;i++)
{
    values[i]=rand();
}
cout << "Sorting Array .......\n";
clock_t start = clock();
sortArray(values, x);
 cout << "The Array Now Sorted\n";
printf("Elapsed Time : %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
cout << "\n";
}
 void sortArray(int array[], int size)  
{
  bool swap;
   int temp;
  do
  {
   swap = false;
  for (int count = 0; count < (size - 1); count++)
   {
   if (array[count] > array[count + 1])
  {
    temp = array[count];
    array[count] = array[count + 1];
    array[count + 1] = temp;
    swap = true;
  }
  }
  }while (swap);
}

我尝试在sortArray方法的"for语句"之前加入##pragma omp parallel for，但是运行时间仍然约为13秒，没有任何改善......所以请尽快帮助我。

- FarOoOosa

---

由于每次循环迭代都依赖于前一次迭代的结果，因此您将无法对该循环进行并行化处理。如果想提高速度，请使用除Bubblesort以外的任何算法。或者更好的方法是使用 std::sort。 - Mike Seymour

我认为你漏掉了一些东西：你不能要求几个处理器各自运行它们自己的迭代，但是你可以并行化一个迭代。基本上，如果你有6个元素[0,1,2,3,4,5]，那么你可以让一个处理器处理[0,1]，一个处理[2,3]，另一个处理[4,5]。在下一次迭代中，你可以让一个处理[2,3]，一个处理[4,5]，然后你回到原点。 - Matthieu M.

Answer 1

尝试使用这个并行冒泡排序算法：

1.  For k = 0 to n-2
2.  If k is even then
3.     for i = 0 to (n/2)-1 do in parallel
4.         If A[2i] > A[2i+1] then
5.             Exchange A[2i] ↔ A[2i+1]
6.  Else
7.     for i = 0 to (n/2)-2 do in parallel
8.         If A[2i+1] > A[2i+2] then
9.             Exchange A[2i+1] ↔ A[2i+2]
10. Next k

并行分析

步骤1-10是一个大循环，需要重复n-1次。因此，并行时间复杂度为O(n)。如果算法中，奇数步需要（n/2）-2个处理器，偶数步需要（n/2）-1个处理器。因此，这需要O(n)个处理器。

您仍然可以使用swap标志检查，在Next k之前停止程序。
当然，不要指望在没有数百个物理处理器的情况下获得很大的速度提升 :)

- Nick Dandoulakis