c-多线程快速排序会使最后1/6未排序

Question

我的目标是创建一个程序，该程序接受一大串未排序的整数(1-10百万(，并将其分为6个部分，由线程同时对其进行排序。排序后，我将其合并到一个排序数组中，以便更快地找到中值和模式。

输入文件如下所示：

# 1000000
314
267
213
934

其中#后面的数字标识列表中的整数数量。

目前，我可以在没有线程的情况下完美快速地排序，但当我开始线程时，我遇到了一个问题。对于1000000个数据集，它只对前833333个整数进行排序，留下最后166666(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: %dn",size);
bigArr= malloc(size*sizeof(int));
}
else{
//printf("[%d]= %sn",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()中。为了解释函数的作用，param(线程号(标识要快速排序的数组块。我把这个大小分成6部分，因为它是偶数，所以剩下的数字会进入最后一块。例如，1000000个整数，第一个5/6排序为166666，最后一个1/6排序为余数(166670(。

我知道

• 即使是1000万个整数，多线程处理也不会加快多少速度
• 这不是找到中值/模式的最有效方法

感谢您阅读本文，我们将感谢您提供的任何帮助。

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);