マルチスレッドを使用した C++ でのマージ ソートの実装

ソートされていない整数の配列を取得します。タスクは、マルチスレッドによって実装されたマージ ソート手法を使用して配列をソートすることです。

マージ ソート

マージ ソートは、配列を 2 つに分割する分割統治手法に基づいたソート手法です。等しい半分 、そしてそれらを並べ替えられた方法で結合します。

マージソートを実装するアルゴリズムは

• 要素があるかどうかを確認します

• それ以外の場合はデータを半分に分割します分割できなくなるまで再帰的に。

• 最後に、小さいリストを並べ替えられた順序で新しいリストに結合します。

マルチスレッド

オペレーティング システムでは、スレッドはいくつかのタスクの実行を担当する軽量プロセスです。スレッドは共通のリソースを共有してタスクを同時に実行します。

マルチスレッドはマルチタスクの実装であり、単一のプロセッサ上で複数のスレッドを実行してタスクを同時に実行できます。単一のアプリケーション内の特定の操作を個別のスレッドに分割します。各スレッドは並行して実行できます。

例:

-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 がスレッドのサイズより小さくなるまで、i から 0 まで FOR ループを開始します。ループ内で、 pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) メソッドが呼び出され、指定された配列値を持つスレッドが作成されます。

• 関数をcombine_array(0, (size/2 - 1)/2, size/2 - 1), combin_array(size/2, size/2 (size - 1)として呼び出します。 -size/2)/2, size-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

• first が 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 to first (end - first) / 2

  • IF が end first より小さいかどうかを確認してから、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 end)

  • 変数を int* start から new int[mid_val - first 1]、int* last から new int[end - mid_val]、temp_1 からmid_val - first 1、として宣言します。 temp_2 から最後まで、mid_val、i、j、k から最初まで。

    li>

  • i が temp_1 未満になるまで、i から 0 まで FOR ループを開始します。ループ内で、start[i] を arr[i first] に設定します。

  • i が temp_2 未満になるまで、i から 0 まで FOR ループを開始します。ループ内で、last[i] を arr[i mid_val 1]

  • set i to 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 ] に設定します

#Example

#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;
}

Output

上記のコードを実行すると、次の出力が生成されます

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 中国語 Web サイトの他の関連記事を参照してください。