我尝试使用OpenMP在分区部分和quicksort部分中并行进行quicksort.我的C代码如下:
I try to use OpenMP to parallel quicksort in partition part and quicksort part. My C code is as follows:
#include "stdlib.h" #include "stdio.h" #include "omp.h" // parallel partition int ParPartition(int *a, int p, int r) { int b[r-p]; int key = *(a+r); // use the last element in the array as the pivot int lt[r-p]; // mark 1 at the position where its element is smaller than the key, else 0 int gt[r-p]; // mark 1 at the position where its element is bigger than the key, else 0 int cnt_lt = 0; // count 1 in the lt array int cnt_gt = 0; // count 1 in the gt array int j=p; int k = 0; // the position of the pivot // deal with gt and lt array #pragma omp parallel for for ( j=p; j<r; ++j) { b[j-p] = *(a+j); if (*(a+j) < key) { lt[j-p] = 1; gt[j-p] = 0; } else { lt[j-p] = 0; gt[j-p] = 1; } } // calculate the new position of the elements for ( j=0; j<(r-p); ++j) { if (lt[j]) { ++cnt_lt; lt[j] = cnt_lt; } else lt[j] = cnt_lt; if (gt[j]) { ++cnt_gt; gt[j] = cnt_gt; } else gt[j] = cnt_gt; } // move the pivot k = lt[r-p-1]; *(a+p+k) = key; // move elements to their new positon #pragma omp parallel for for ( j=p; j<r; ++j) { if (b[j-p] < key) *(a+p+lt[j-p]-1) = b[j-p]; else if (b[j-p] > key) *(a+k+gt[j-p]) = b[j-p]; } return (k+p); } void ParQuickSort(int *a, int p, int r) { int q; if (p<r) { q = ParPartition(a, p, r); #pragma omp parallel sections { #pragma omp section ParQuickSort(a, p, q-1); #pragma omp section ParQuickSort(a, q+1, r); } } } int main() { int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6}; ParQuickSort(a, 0, 9); int i=0; for (; i!=10; ++i) printf("%d\t", a[i]); printf("\n"); return 0; }我是OpenMG和并行编程的新手.对于main函数中的示例，排序结果为:
I'm new to OpenMG and parallel programming. For the example in the main function, the sorting result is:
0 9 9 2 2 2 6 7 7 7我使用gdb进行调试.在早期的递归中，一切进展顺利.但是在某些递归中，它突然变得混乱起来，开始重复元素.然后生成上面的结果.
I used gdb to debug. In the early recursion, all went well. But in some recursions, it suddenly messed up to begin duplicate elements. Then generate the above result.
有人可以帮我弄清楚问题出在哪里吗?非常感谢你！
Can someone help me figure out where the problem is? Thank you very much!
推荐答案我对我的第一条评论感到抱歉.这与您的问题无关.我还没有找到您问题的真正问题(也许您的move元素具有问题).根据您的意见，我编写了一个类似的程序，它的工作原理 很好.(我也是OpenMP的新手.)
I feel sorry for my first comment.It does not matter with your problem.I have not found the true problem of your question(Maybe your move element has the problem).According to your opinion, I wrote a similar program, it works fine.(I am also new on OpenMP).
#include <stdio.h> #include <stdlib.h> int partition(int * a, int p, int r) { int lt[r-p]; int gt[r-p]; int i; int j; int key = a[r]; int lt_n = 0; int gt_n = 0; #pragma omp parallel for for(i = p; i < r; i++){ if(a[i] < a[r]){ lt[lt_n++] = a[i]; }else{ gt[gt_n++] = a[i]; } } for(i = 0; i < lt_n; i++){ a[p + i] = lt[i]; } a[p + lt_n] = key; for(j = 0; j < gt_n; j++){ a[p + lt_n + j + 1] = gt[j]; } return p + lt_n; } void quicksort(int * a, int p, int r) { int div; if(p < r){ div = partition(a, p, r); #pragma omp parallel sections { #pragma omp section quicksort(a, p, div - 1); #pragma omp section quicksort(a, div + 1, r); } } } int main(void) { int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6}; int i; quicksort(a, 0, 9); for(i = 0;i < 10; i++){ printf("%d\t", a[i]); } printf("\n"); return 0; }