我尝试多线程快速排序,如下面的代码。我使用函数 median3 来查找枢轴,CUTOFF 定义如何通过 InsertionSort 对小数组进行排序。这个 QuickSort 可以使用数组有 1000 个元素,但是当我将数组增加到 10.000 个元素时,我在 pthread_join() 处得到“分段错误”。我在 Fedora 16 上编码,符合 gcc
void *q_sort( q_sort_input *input ) {
int *a; int left; int right;
a = input->a;
left = input->left;
right = input->right;
int i, j;
int pivot;
if (left + CUTOFF < right) {
pthread_t thread1, thread2;
pivot = median3( a, left, right );
i = left - 1;
j = right - 1;
#ifdef DEBUG
int k;
for (k = 0; k<lenght; k++) printf("%d ",a[k]);
printf("\n");
printf("left:%d right:%d pivot:%d \n",left,right,pivot);
#endif
for (;;) {
while (a[++i] < pivot );
while (a[--j] > pivot ) ;
if (i < j) {swap( &a[i], &a[j] );}
else break;
}
swap( &a[i], &a[right - 1] );
#ifdef DEBUG
for (k = 0; k<lenght; k++) printf("%d ",a[k]);
printf("\n \n");
#endif
q_sort_input*input1= malloc(sizeof(q_sort_input));
input1->a = a;
input1->left = left;
input1->right = i-1;
input1->n = input->n;
pthread_create(&thread1, NULL, q_sort, (void*)input1 );
q_sort_input*input2= malloc(sizeof(q_sort_input));
input2->a = a;
input2->left = i+1;
input2->right = right;
input2->n = input->n;
pthread_create(&thread2, NULL, q_sort, (void*)input2 );
void *end;
if (thread1 != NULL) pthread_join(thread1,&end);
if (thread2 != NULL) pthread_join(thread2,&end);
free(input1);
free(input2);
}
else InsertionSort(a, left,right);
}