сортировка с использованием двух идентификаторов потоков - PullRequest
Новая
       7

сортировка с использованием двух идентификаторов потоков

0 голосов
/ 31 мая 2018

привет, я хочу использовать сортировку слиянием с массивом, используя потоки, мне нужно использовать два идентификатора потока, чтобы выполнить рекурсивную сортировку. Вот мой код 

void Recursive_Divition(int a[], int l, int h,int Degree_of_parallelism,int count)//this function divdis recursivly the array 
 {//and sends it to merge sort
struct thread_data thread_data_array[Degree_of_parallelism];
int i, len=(h-l+1);

// Using insertion sort for small sized array
if (len==2*Degree_of_parallelism)//a stoping condition if the array size is equal to the degree of parallisim then send the array to be sortrd
{


    pthread_t * thread = (pthread_t *)malloc(Degree_of_parallelism*sizeof(pthread_t ));//creating a pointer to thread array

    thread_data_array[count].low=l;//the arguments for the merge sort
    thread_data_array[count].high=h/2;



    pthread_create(&thread[count],NULL,threaded_merge_sort,(void *) &thread_data_array[count]);//create a thread and send it to the function
    count++;
    thread_data_array[count].low=h/2+1;//the argument for the other thread
    thread_data_array[count].high=h;

    pthread_create(&thread[count],NULL,threaded_merge_sort,(void *) &thread_data_array[count]);
    pthread_join(thread[count-1],NULL);
     pthread_join(thread[count],NULL);
    free(thread);

    }

if(len>Degree_of_parallelism){

    Recursive_Divition(a,l,l+len/2-1,Degree_of_parallelism,count);//for the first half

    Recursive_Divition(a,l+len/2,h,Degree_of_parallelism,count);//for the secound half
    merge(a, l, l+len/2-1, h);
}

}, а вот сортировка с многопоточным слиянием 

void *threaded_merge_sort(void *param) 
 {
   printf("Create a thread %u\n", (unsigned int)pthread_self());//this           function calls the merge sort function
   struct thread_data *my_data;

   my_data = (struct thread_data *) param;
   int l=my_data->low;
  int h=my_data->high;
  printf("low is : %d high is : %d\n",l,h);
  mergeSort(array,l,h);
   pthread_exit(NULL);

, и я получил следующий вывод, что проблема в индексе, и я не знал, как ее исправить 

Amount of numbers that sort: 16
Degree of parallelism: 8
Array Before Sort: 1,5,6,33,77,12,90,87,0,10,34,2,741,453,19,132
Create a thread 3158492928
low is : 0 high is : 1
Create a thread 3150100224
low is : 2 high is : 3
Create a thread 3141707520
low is : 4 high is : 3
Create a thread 3133314816
low is : 4 high is : 7
Create a thread 3122734848
low is : 8 high is : 5
Create a thread 3114342144
low is : 6 high is : 11
Create a thread 3105949440
Create a thread 3097556736
low is : 8 high is : 15
low is : 12 high is : 7
Array After Sort: 1,5,6,10,19,33,12,34,0,2,77,87,90,132,453,741

1 Ответ

0 голосов
/ 31 мая 2018

Здесь проблема с индексацией: 

    thread_data_array[count].low=l;//the arguments for the merge sort
    thread_data_array[count].high=h/2;

[...] 

    thread_data_array[count].low=h/2+1;//the argument for the other thread
    thread_data_array[count].high=h;

, которая неправильно разделяет массив (под) на две частиесли l не равно 0. Например, если h равно 16, то разрыв вашего массива всегда равен 8, даже если это меньше чем l.

Вместо этого вы, похоже, хотите 

    thread_data_array[count].low = l;
    thread_data_array[count].high= (l + h) / 2;

и 

    thread_data_array[count].low = (l + h) / 2 + 1;
    thread_data_array[count].high=h;

Кроме того, я подозреваю, что вы хотите else перед вторым if в Recursive_Divition(), и вам также может понадобиться добавить заключительный блок else.

...