在 C++ 中使用多线程进行合并排序
我们得到一个未排序的整数数组。任务是使用通过多线程实现的合并排序技术对数组进行排序
归并排序
归并排序是一种基于分治法的排序技术，我们将数组分成相等的两半，然后以排序的方式组合它们。
实现归并排序的算法是
检查列表中是否有一个元素，然后返回该元素。
否则，将数据递归地分成两半，直到无法进一步划分为止。
最后，按排序顺序将较小的列表合并到新列表中。
多线程
在操作系统中，线程是负责执行部分任务的轻量级进程。线程共享公共资源以并发执行任务。
多线程是多任务的一种实现，我们可以在单个处理器上运行多个线程来并发执行任务。它将单个应用程序中的特定操作细分为单独的线程。每个线程可以并行运行。
例如-：
在 -intarr[]={3,2,1,10,8,5,7,9,4}
Out -Sorted数组是：1,2,3,4,5,7,8,9,10
解释- 我们得到一个带有整数值的未排序数组。现在我们将使用多线程合并排序对数组进行排序。
在 -intarr[]={5,3,1,45,32,21,50}
Out -Sorted数组是：1,3,5,21,32,45,50
解释- 我们得到一个带有整数值的未排序数组。现在我们将使用多线程合并排序对数组进行排序。
以下程序中使用的方法如下-
我们将首先使用rand()C++STL中的方法生成随机数。
创建一个pthread_t类型的数组，即P_TH[thread_size]。
从i到0开始循环FOR，直到i小于线程的大小。在循环内，调用pthread_create(&P_TH[i],NULL,Sorting_Threading,(void*)NULL)方法以使用给定的数组值创建线程。
调用函数为combine_array(0,(size/2-1)/2,size/2-1),combine_array(size/2,size/2+(size-1-size/2)/2,size-1)和combine_array(0,(size-1)/2,size-1)
打印存储在整数类型的arr[]中的排序数组。
函数内部void*Sorting_Threading(void*arg)
将变量声明为set_val到temp_val++，首先到set_val*(size/4)，end到(set_val+1)*(size/4)-1和mid_val到first+(end-first)/2
首先检查IF小于end然后调用Sorting_Threading(first,mid_val)Sorting_Threading(mid_val+1,end)和combine_array(first,mid_val,end);
函数内部voidSorting_Threading(intfirst,intend)
将变量声明为mid_val到first+(end-first)/2
检查IF首先小于end然后调用Sorting_Threading(first,mid_val)Sorting_Threading(mid_val+1,end)和combine_array(first,mid_val,end)
函数内部voidcombine_array(intfirst,intmid_val,intend)
将变量声明为int*starttonewint[mid_val-first+1],int*lasttonewint[end-mid_val],temp_1tomid_val-first+1,temp_2toend-mid_val,i,j,ktofirst.
从i到0开始循环FOR，直到i小于temp_1。在循环内，将start[i]设置为arr[i+first]。
从i到0开始循环FOR，直到i小于temp_2。在循环内，将last[i]设置为arr[i+mid_val+1]
将i设置为j为0。开始循环当i小于temp_1且j小于temp_2。在while内，检查IFstart[i]小于last[j]然后将arr[k++]设置为start[i++]。否则，设置arr[k++]=last[j++]
在i小于temp_1时开始，然后设置arr[k++]=start[i++]。开始WHILEj小于temp_2然后将arr[k++]设置为last[j++]
示例
#include <iostream>
#include <pthread.h>
#include <time.h>
#define size 20
#define thread_size 4
using namespace std;
int arr[size];
int temp_val = 0;
void combine_array(int first, int mid_val, int end){
int* start = new int[mid_val - first + 1];
int* last = new int[end - mid_val];
int temp_1 = mid_val - first + 1;
int temp_2 = end - mid_val;
int i, j;
int k = first;
for(i = 0; i < temp_1; i++){
start[i] = arr[i + first];
}
for (i = 0; i < temp_2; i++){
last[i] = arr[i + mid_val + 1];
}
i = j = 0;
while(i < temp_1 && j < temp_2){
if(start[i] <= last[j]){
arr[k++] = start[i++];
}
else{
arr[k++] = last[j++];
}
}
while (i < temp_1){
arr[k++] = start[i++];
}
while (j < temp_2){
arr[k++] = last[j++];
}
}
void Sorting_Threading(int first, int end){
int mid_val = first + (end - first) / 2;
if(first < end){
Sorting_Threading(first, mid_val);
Sorting_Threading(mid_val + 1, end);
combine_array(first, mid_val, end);
}
}
void* Sorting_Threading(void* arg){
int set_val = temp_val++;
int first = set_val * (size / 4);
int end = (set_val + 1) * (size / 4) - 1;
int mid_val = first + (end - first) / 2;
if (first < end){
Sorting_Threading(first, mid_val);
Sorting_Threading(mid_val + 1, end);
combine_array(first, mid_val, end);
}
}
int main(){
for(int i = 0; i < size; i++){
arr[i] = rand() % 100;
}
pthread_t P_TH[thread_size];
for(int i = 0; i < thread_size; i++){
pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL);
}
for(int i = 0; i < 4; i++){
pthread_join(P_TH[i], NULL);
}
combine_array(0, (size / 2 - 1) / 2, size / 2 - 1);
combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1);
combine_array(0, (size - 1)/2, size - 1);
cout<<"Merge Sort using Multi-threading: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
Merge Sort using Multi-threading: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93