在c中编写并行快速排序

我需要使用pthreads在c中编写并行快速排序。 这就是我到目前为止所做的。

#include  #include  #include  #include  #include  // sleep() #include  #include  // EXIT_SUCCESS #include  // strerror() #include  #define SIZE_OF_DATASET 6 void* quickSort( void* data); int partition( int* a, int, int); struct info { int start_index; int* data_set; int end_index; }; int main(int argc, char **argv) { int a[] = { 7, 12, 1, -2,8,2}; pthread_t thread_id; struct info *info = malloc(sizeof(struct info)); info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET); info->data_set=a; info->start_index=0; info->end_index=SIZE_OF_DATASET-1; if (pthread_create(&thread_id, NULL, quickSort, info)) { fprintf(stderr, "No threads for you.\n"); return 1; } pthread_join(thread_id, NULL); printf("\n\nSorted array is: "); int i; for(i = 0; i data_set[i]); return 0; } void* quickSort( void *data) { struct info *info = data; int j,l,r; l = info->start_index; r = info->end_index; pthread_attr_t attr; pthread_t thread_id1; pthread_t thread_id2; pthread_attr_init(&attr); if( l data_set, l, r); info->start_index=l; info->end_index=j-1; if(info->end_indexend_index=0; if (pthread_create(&thread_id1, NULL, quickSort, info)) { fprintf(stderr, "No threads for you.\n"); return NULL; } info->start_index=j+1; info->end_index=r; if (pthread_create(&thread_id2, NULL, quickSort, info)) { fprintf(stderr, "No threads for you.\n"); return NULL; } pthread_join(thread_id1, NULL); pthread_join(thread_id2, NULL); } return NULL; } int partition( int* a, int l, int r) { int pivot, i, j, t; pivot = a[l]; i = l; j = r+1; while( 1) { do ++i; while( a[i] <= pivot && i  pivot ); if( i >= j ) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[l]; a[l] = a[j]; a[j] = t; return j; } 

但内部快速排序function只能调用第一个线程。 不能理解这里发生的事情。

注意：已经测试了代码的串行版本。 没问题

更新：

这是基于John Bollinger解决方案的修改版本。 但是仍然对快速排序中新创建的线程所采用的数组的后半部分进行了排序。

  int main(int argc, char **argv) { int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9,5,3,24,5,23,3,1,56,8,4,34,23,51}; struct info *info = malloc(sizeof(struct info)); info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET); info->data_set=a; info->start_index=0; info->end_index=SIZE_OF_DATASET-1; quickSort(info); printf("\n\nSorted array is: "); int i; for(i = 0; i data_set[i]); return 0; } void* quickSort( void *data) { struct info *info = data; struct info *info1 = data; int j,l,r; l = info->start_index; r = info->end_index; pthread_attr_t attr; pthread_t thread_id1; pthread_attr_init(&attr); if( l data_set, l, r); info1->start_index=j+1; info1->end_index=r; info1->data_set = info->data_set; if(info1->end_indexend_index=0; if (pthread_create(&thread_id1, NULL, quickSort, info1)) { fprintf(stderr, "No threads for you.\n"); return NULL; } info->start_index=l; info->end_index=j-1; if(info->end_index end_index = 0; quickSort(info); /* don't care about the return value */ pthread_join(thread_id1, NULL); } return NULL; } 

Answer 1

该程序是不正确的，因为您的线程都共享相同的struct info结构，描述了它们应该处理的子问题。 它们同时运行（或者可能会运行）并且它们在进行时修改该结构，因此任何特定线程看到的值都是不确定的。

要解决这个问题，每个quickSort框架必须至少创建一个新的struct info ，这样它在不同线程中调用的两个quickSort()调用每个都有自己的。 作为效率问题，在每个quickSort()调用中仅产生一个额外的线程也会更好。 例如：

 void* quickSort( void *data) { struct info *info = data; struct info other_info; /* ... */ /* launch a new thread to handle one partition: */ other_info.start_index = j + 1; other_info.end_index = r; other_info.data_set = info->data_set; if (pthread_create(&thread_id1, NULL, quickSort, &other_info)) { fprintf(stderr, "No threads for you.\n"); return NULL; } /* handle the other partition in the current thread: */ info->start_index = l; info->end_index = j - 1; if(info->end_index < 0) info->end_index = 0; quickSort(info); /* don't care about the return value */ /* after this thread is done, wait for the other thread to finish, too */ pthread_join(thread_id1, NULL); /* ... */ } 

请注意，这并不能确保任何特定的线程对同时运行，无论是在多核意义上还是在时间切片意义上。 这取决于操作系统。 但是，当然，多核并行感仍然适用于主机上有多个可用操作系统愿意安排进程的内核。