多线程快速排序留下最后 1/6 未排序

Question

我的目标是创建一个程序，该程序采用大量未排序的整数（1-1000 万）并将其分为 6 个部分，并由一个线程对其进行并发排序。排序后，我将它合并到一个排序数组中，这样我可以更快地找到中位数和众数。

输入文件将是这样的：

# 后面的数字表示列表中的整数个数。

目前，我可以在不使用线程的情况下完美快速地进行排序，但是当我开始使用线程时，我运行遇到了问题。对于 1,000,000 个数据集，它仅对前 833,333 个整数进行排序，而最后 166,666 (1/6) 个整数未排序。

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <time.h>
#define BUF_SIZE 1024

int sum; /* this data will be shared by the thread(s) */
int * bigArr;
int size;
int findMedian(int array[], int size)
{
    if (size % 2 != 0)
        return array[size / 2];

    return (array[(size - 1) / 2] + array[size / 2]) / 2;
}
/*compare function for quicksort*/
int _comp(const void* a, const void* b) {
    return ( *(int*)a - *(int*)b);
}

/*This function is the problem method*/
/*indicate range of array to be processed with the index(params)*/
void *threadFct(int param)
{
    int x= size/6;
    if(param==0)x= size/6;
    if(param>0&&param<5)x= (size/6)*param;
    if(param==5)x= (size/6)*param+ (size%size/6);/*pass remainder into last thread*/
    qsort((void*)bigArr, x, sizeof(bigArr[param]), _comp);
    pthread_exit(0);
}

int main(int argc, char *argv[])
{
    FILE *source;
    int i =0;

    char buffer[BUF_SIZE];

    if(argc!=2){
        printf("Error. please enter ./a followed by the file name");
        return -1;}

    source= fopen(argv[1], "r");
    if (source == NULL) { /*reading error msg*/
        printf("Error. File not found.");
        return 1;
    }
    int count= 0;
    while (!feof (source)) {
        if (fgets(buffer, sizeof (buffer), source)) {
            if(count==0){  /*Convert string to int using atoi*/
                char str[1];
                sprintf(str, "%c%c%c%c%c%c%c%c%c",buffer[2],buffer[3],buffer[4],buffer[5],buffer[6],buffer[7],buffer[8],buffer[9],buffer[10]);/*get string of first */
                size= atoi(str); /* read the size of file--> FIRST LINE of file*/
                printf("SIZE: %d\n",size);
                bigArr= malloc(size*sizeof(int));
            }
            else{
                //printf("[%d]= %s\n",count-1, buffer); /*reads in the rest of the file*/
                bigArr[count-1]= atoi(buffer);
            }
            count++;
        }
    }

/*thread the unsorted array*/
    pthread_t tid[6]; /* the thread identifier */
    pthread_attr_t attr; /* set of thread attributes */

// qsort((void*)bigArr, size, sizeof(bigArr[0]), _comp);  <---- sorts array without threading
    for(i=0; i<6;i++){
        pthread_create(&tid[i], NULL, &threadFct, i);
        pthread_join(tid[i], NULL);
    }

    printf("Sorted array:\n");

    for(i=0; i<size;i++){
        printf("%i \n",bigArr[i]);
    }

    fclose(source);
}

所以要澄清问题的函数在我的 threadFct() 中。为了解释该函数的作用，参数（线程号）标识要快速排序的数组块。我将大小分成 6 个部分，因为它是偶数，所以剩余的数字进入最后一个块。因此，例如，对于 1,000,000 个整数，我会将前 5/6 个整数排序为 166,666，最后 1/6 将对余数 (166670) 进行排序。

我知道

即使是 1000 万个整数，多线程也不会加速很多
这不是查找 median/mode

感谢阅读本文，如有任何帮助，我们将不胜感激。

Answer 1

您在每次调用 qsort 时都对数组的开头进行排序。您只是通过设置 x 来更改每个线程排序的元素数量。您还在线程 0 和 1.

中将 x 设置为相同的值

您需要为每个线程计算数组中的偏移量，即size/6 * param。元素的数量将是 size/6 除了最后一个块，它使用模数来获得余数。

如评论中所述，线程函数的参数应该是一个指针，而不是int。您可以在指针中隐藏一个整数，但您需要使用显式转换。

void *threadFct(void* param_ptr)
{
    int param = (int)param_ptr;
    int start = size/6 * param;
    int length;
    if (param < 5) {
        length = size/6;
    } else {
        length = size - 5 * (size/6);
    }
    qsort((void*)(bigArr+start), length, sizeof(*bigArr), _comp);
    pthread_exit(0);
}

以后

pthread_create(&tid[i], NULL, &threadFct, (void*)i);

多线程快速排序留下最后 1/6 未排序

Quick-sorting with multiple threads leaves last 1/6 unsorted

c

multithreading

quicksort