平行冒泡排序使用OpenMP

我寫冒泡排序算法的C++代碼，我不知道如何使它並行使用OpenMP所以請幫助我..... 這是代碼：平行冒泡排序使用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); 
}

現在需要大約13秒，我試圖把 ## pragma omp並行爲之前，「在sortArray方法中的statment」，它沒有任何區別，它也需要約13秒..... 所以請儘快幫我你可以

來源

2010-01-08 FarOoOosa

由於每次迭代都取決於前一次迭代的結果，因此您將無法並行循環。如果你想加快速度，那麼就使用除Bubblesort之外的任何算法。或者，更好的是，使用'std :: sort'。 – 2010-01-08 14:03:32

我認爲你錯過了一些東西：你不能要求幾個處理器每次運行在他們自己的迭代上，但是你可以並行迭代。基本上，如果你有6個元素[0,1,2,3,4,5]，那麼你可以在[0,1]上使用一個處理器，在[2,3]上使用一個處理器，在[4,5]上使用一個處理器。在下一次迭代中，你有一個[2,3]和一個[4,5]，然後你回到原點。 – 2010-01-08 17:26:45

試試這個Parallel Bubble Sort算法：

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之前立即停止該例程。
當然，如果沒有數百個物理處理器，不要期望速度有很大提高:)

來源

2010-01-08 14:36:48

平行冒泡排序使用OpenMP

回答

相關問題