用c编写并行快速排序

Question

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

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <pthread.h>
    #include <unistd.h>  // sleep()
    #include <stdio.h>
    #include <stdlib.h>  // EXIT_SUCCESS
    #include <string.h>  // strerror()
    #include <errno.h>

    #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 < SIZE_OF_DATASET; ++i)
               printf(" %d ", info->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 < r )
       {

           j = partition( info->data_set, l, r);
           info->start_index=l;
           info->end_index=j-1;
           if(info->end_index<0)info->end_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 <= r );
        do --j; while( a[j] > 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;
    }

但是在快速排序函数中只调用第一个线程。无法理解这里发生了什么。

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

更新：

这是基于 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 < SIZE_OF_DATASET; ++i)
           printf(" %d ", info->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 < r )
   {

       j = partition( info->data_set, l, r);
       info1->start_index=j+1;
       info1->end_index=r;
       info1->data_set = info->data_set;
       if(info1->end_index<0)info1->end_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 < 0) info->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);

    /* ... */
}

请注意，这并不能确保任何特定的线程对运行并发，无论是在多核意义上还是在时间片意义上。这取决于 OS。但是，当然，多核并行意义仅适用于 OS 愿意安排您的进程的主机上实际上有多个可用内核的情况。

用c编写并行快速排序

Writing a parallel quick sort in c

c

pthreads

quicksort

data-structures