0

我尝试多线程快速排序,如下面的代码。我使用函数 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);

}
4

0 回答 0