c++ - 快速排序(使用 pthreads)仅对数组的一半进行排序
问题描述
我正在使用 pthreads 并行进行快速排序。问题是仅对数组的后半部分进行了排序。
我怀疑分区函数可能有问题,但我不知道如何调试这个问题。我已经添加了我的完整代码。
有人可以指出我正确的方向吗?
#include <pthread.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstdlib>
#include <stdlib.h>
#include <time.h>
using namespace std::chrono;
using namespace std;
#define SIZE 10
#define MAXTHREAD 8
#define swap(A, a, b) {unsigned tmp; tmp=A[a]; A[a]=A[b]; A[b]=tmp;}
#define THRESHOLD SIZE/MAXTHREAD
static int A[SIZE];
static int partition(int *A, int low, int high, int pivot_idx);
void read();
void *qsort(void *arg);
static void quick_sort(int *A, int low, int high);
void print();
pthread_t pt[MAXTHREAD];
int main(int argc, char* argv[])
{
// double begin,end;
int i,rc;
rc = 0;
i = 0;
pthread_mutex_t lok1;
pthread_cond_t cond1;
void *exit_status;
printf("CALLING THE READ FUNCTION\n");
read();
printf("CALLING THE PRINT FUNCTION\n");
print();
printf("CALLING THE SORT FUNCTION\n");
pthread_mutex_init(&lok1, NULL);
pthread_cond_init(&cond1,NULL);
auto start = high_resolution_clock::now();
pthread_create(&pt[i],NULL, qsort,(void*)i);
if(rc = pthread_create(&pt[i],NULL, qsort,(void*)i))
{
printf("%THREAD FAILED\n", i);
}
pthread_join(pt[i], &exit_status);
printf("\n");
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout <<"\n" << "Duration: " << duration.count() << " microseconds" << endl;
printf("THREAD %d EXITED \n", 1);
pthread_mutex_destroy(&lok1);
pthread_cond_destroy(&cond1);
print();
return 0;
}
void *qsort(void *arg)
{
int i, pivot_idx, rc, start, end;
i = *((int*)(&arg));
start = 0;
end=SIZE;
void *exit_status;
printf("%d THREAD CREATED WITH I: %d\n,i");
if (start >= end)
{
return NULL;
}
else
{
pivot_idx = (start+end/2);
pivot_idx = partition(A, start, end, pivot_idx);
if((pivot_idx - start)<= THRESHOLD || (i == MAXTHREAD-1))
{
quick_sort(A, start, pivot_idx);
}
else if(((end-pivot_idx) <= THRESHOLD) || (i == MAXTHREAD-1))
{
quick_sort(A,pivot_idx,end);
}
else if(i <MAXTHREAD)
{
++i;
if(rc = pthread_create(&pt[i], NULL, qsort, (void *)i))
{
printf("%d THREAD FAILED\n",i);
}
pthread_join(pt[i],&exit_status);
}
}
return NULL;
}
static int partition(int *A, int low, int high, int pivot_idx)
{
if (pivot_idx != low)
{
swap(A,low, pivot_idx);
}
pivot_idx = low;
low++;
while (low < high)
{
if(A[low] <= A[pivot_idx])
{
low++;
}
else if(A[high] > A[pivot_idx])
{
high--;
}
else
{
swap(A, low, high);
}
}
if(high != pivot_idx)
{
swap(A, pivot_idx, high);
}
return pivot_idx;
}
static void quick_sort(int *A, int low, int high)
{
int pivot_idx;
if(low >= high)
{
return;
}
else
{
pivot_idx = (low+high/2);
pivot_idx = partition(A, low, high, pivot_idx);
if(low < pivot_idx)
{
quick_sort(A, low, pivot_idx-1);
}
if(pivot_idx < high)
{
quick_sort(A, pivot_idx+1, high);
}
}
}
void read()
{
int i;
for(i=0; i<SIZE; i++)
{
A[i] = rand()%10 +1;
}
}
void print()
{
int i, chunk;
chunk = SIZE/MAXTHREAD;
for(i=0; i<SIZE; i++)
{
if(i%chunk == 0)
{
printf("|");
}
printf(" %d ", A[i]);
}
printf("\n\n");
}
解决方案
好的,所以据我所知,
#1 是您设置 end = SIZE,然后您将其称为分区。这设置 high = 10,然后您访问数组外部的 A[high]。
#2,除非我遗漏了某些东西,否则分区总是返回低的初始值,这使得 pivot_idx - start = 0,进而调用 quicksort(A, start, pivot_idx),它返回而不做任何事情,因为低 = 高。也许您打算在交换它时将 pivot_idx 设置为等于高?
推荐阅读
- next.js - Next.js 快速刷新自定义动画
- bitcoin - 在远程节点或本地节点上运行 getblocktemplate 而不同步
- docker - docker-compose build 找不到模块'./src'
- python - 使用 BERT 和 Keras 的神经网络进行文本分类
- c# - 是否可以使用 ASP.NET MVC 在其他模型的详细信息视图中链接模型的创建视图?
- javascript - 谷歌自动完成放置搜索错误不是 HTMLInputElement 的实例
- python - 在python中无法从索引中找到数据
- c - 使用 qsort 函数对结构进行排序
- arangodb - ArangoDB 通配符搜索很慢
- node.js - 如果加载 Typeorm 后满足条件,则返回空对象