在 C++ 中使用多线程进行合并排序

  • Z时代
  • 2024-01-10
  • 分类：综合

我们得到一个未排序的整数数组。任务是使用通过多线程实现的合并排序技术对数组进行排序

归并排序

归并排序是一种基于分治法的排序技术，我们将数组分成相等的两半，然后以排序的方式组合它们。

实现归并排序的算法是

  • 检查列表中是否有一个元素，然后返回该元素。

  • 否则，将数据递归地分成两半，直到无法进一步划分为止。

  • 最后，按排序顺序将较小的列表合并到新列表中。

多线程

在操作系统中，线程是负责执行部分任务的轻量级进程。线程共享公共资源以并发执行任务。

多线程是多任务的一种实现，我们可以在单个处理器上运行多个线程来并发执行任务。它将单个应用程序中的特定操作细分为单独的线程。每个线程可以并行运行。

例如-：

在 -int arr[] = {3, 2, 1, 10, 8, 5, 7, 9, 4}

Out  -Sorted 数组是：1, 2, 3, 4, 5, 7, 8, 9, 10

解释 - 我们得到一个带有整数值的未排序数组。现在我们将使用多线程合并排序对数组进行排序。

在 -int arr[] = {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);

  • 函数内部 void Sorting_Threading(int first, int end)

    • 将变量声明为 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)

  • 函数内部 void combine_array(int first, int mid_val, int end)

    • 将变量声明为 int* start to new int[mid_val - first + 1], int* last to new int[end - mid_val], temp_1 to mid_val - first + 1, temp_2 to end - mid_val, i, j, k to first .

    • 从 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 内，检查 IF start[i] 小于 last[j] 然后将 arr[k++] 设置为 start[i++]。否则，设置 arr[k++] = last[j++]

    • 在 i 小于 temp_1 时开始，然后设置 arr[k++] = start[i++]。开始 WHILE j 小于 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

以上是 在 C++ 中使用多线程进行合并排序 的全部内容， 来源链接： utcz.com/z/356014.html

回到顶部