使用多執行緒在C++中實現歸併排序

我們得到一個未排序的整數陣列。任務是使用透過多執行緒實現的合併排序技術對數組進行排序

合併排序

#合併排序是一種基於分而治之技術的排序技術，我們將數組分成相等的兩半，然後以排序的方式將它們組合起來。

實作歸併排序的演算法是

• 檢查是否有一個元素

• 否則，將資料遞歸地分成兩半，直到無法再分為止。

• 最後，將較小的列表合併為排序順序合併為新列表。

多執行緒

在作業系統中，執行緒是負責執行部分任務的輕量級進程。線程共享公共資源來並發執行任務。

多執行緒是多工處理的一種實現，我們可以在單一處理器上執行多個執行緒來並發執行任務。它將單一應用程式中的特定操作細分為單獨的執行緒。每個執行緒都可以並行運行。

例如：

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

輸出−排序後的陣列為：1, 2, 3, 4, 5, 7, 8, 9, 10

解釋-我們得到一個帶有整數值的未排序數組。現在我們將使用多線程合併排序對數組進行排序。

In −int arr[] = {5, 3, 1, 45, 32, 21, 50} p>

輸出−排序後的陣列為：1, 3, 5, 21, 32, 45, 50

解釋−我們給出具有整數值的未排序數組。現在我們將使用多線程合併排序對數組進行排序。

下面程式中使用的方法如下 -

• 我們將開始透過使用 C STL 中的 rand() 方法產生隨機數。

• 建立 pthread_t 類型的數組，即 P_TH[thread_size]。

開始從 i 到 0 的 FOR 循環，直到 i 小於執行緒的大小。在循環內部，呼叫 pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) 方法來建立具有給定陣列值的執行緒。

• 將函數當作組合陣列呼叫(0、(大小/ 2 - 1) / 2、大小/ 2 - 1)、combine_array(大小/ 2、大小/2 (大小- 1-大小/2)/2、大小- 1) 和merge_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 first 小於end then調用Sorting_Threading(first,

  #檢查IF first 小於end then調用Sorting_Threading(first, mid_val)、Sorting_Threading(mid_val 1, end)與combine_array(first, mid_val, end);

• 裡面function void Sorting_Threading(int first, int end)##裡面function void Sorting_Threading(int first, int end)##, intend)

  • #將變數宣告為mid_val to first (end - first) / 2

  • 檢查IF 首先小於end，然後呼叫Sorting_Threading(first, mid_val )、Sorting_Threading(mid_val 1, end) 和merge_array(first, mid_val, end)

• ##函數內部void merge_array(int first, int mid_val, int #函數內部void merge_array(int first, int mid_val, int end)
  • 將變數宣告為int* start 到new int[mid_val - first 1]、int* last 到new int[end - mid_val]、temp_1 到mid_val - first 1、temp_2 到end - mid_val、i、j、k 到first。
    li>
  • 開始從 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。在此期間，檢查 IF start[i] 是否小於 last[j]，然後將 arr[k ] 設定為 start[i ]。否則，設定 arr[k ] = last[j ]

  • 當 i 小於 temp_1 時開始，然後設定 arr[k ] = start[i ]。當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++中實現歸併排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！