gpt4 book ai didi

c - OpenMP : Parallel QuickSort

转载 作者:行者123 更新时间:2023-12-02 00:09:48 25 4
gpt4 key购买 nike

我尝试使用 OpenMP 在分区部分和 QuickSort 部分并行化 QuickSort。我的C代码如下:

#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;
}
对于main函数中的例子,排序结果为:
0   9   9   2   2   2   6   7   7   7
我用gdb调试。在早期的递归中,一切顺利。但是在一些递归中,它突然搞砸了开始重复元素。然后生成上面的结果。
有人可以帮我找出问题所在吗?

最佳答案

我对我的第一条评论感到抱歉。与您的问题无关。我还没有找到您问题的真正问题(可能是您的移动元素有问题)。根据您的意见,我写了一个类似的程序,它有效
很好。(我也是 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;
}

关于c - OpenMP : Parallel QuickSort,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16007640/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com