C++でマルチスレッドを使用してソートをマージ

ソートされていない整数配列が与えられます。タスクは、マルチスレッドを介して実装されたマージソート手法を使用して配列をソートすることです

マージソート

マージソートは、分割統治法に基づくソート手法であり、配列を半分に分割してから、ソートされた方法でそれらを結合します。

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

• リストに要素が1つあるかどうかを確認してから、その要素を返します。

• それ以外の場合は、データをさらに分割できなくなるまで、データを2つに繰り返し分割します。

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

マルチスレッド

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

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

例-：

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

アウト -ソートされた配列は次のとおりです：1、2、3、4、5、7、8、9、10

説明 -整数値のソートされていない配列が与えられます。次に、マルチスレッドを使用したマージソートを使用して配列をソートします。

で −int arr [] ={5、3、1、45、32、21、50}

アウト -ソートされた配列は次のとおりです：1、3、5、21、32、45、50

説明 -整数値のソートされていない配列が与えられます。次に、マルチスレッドを使用したマージソートを使用して配列をソートします。

以下のプログラムで使用されるアプローチは次のとおりです-

• まず、C ++ STLのrand（）メソッドを使用して乱数を生成します。

• pthread_tタイプの配列、つまりP_TH[thread_size]を作成します。

• iがスレッドのサイズより小さくなるまで、ループFORをiから0まで開始します。ループ内で、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++、firstをset_val *（size / 4）、end to（set_val + 1）*（size / 4）-1、mid_valをfirst +（end --first）/ 2

    として宣言します。

  • 最初にend未満のIFをチェックしてから、Sorting_Threading（first、mid_val）、Sorting_Threading（mid_val + 1、end）およびcombine_array（first、mid_val、end）;

    を呼び出します。

• 関数内voidSorting_Threading（int first、int end）

  • 変数をmid_valからfirst+（end --first）/ 2

    として宣言します。

  • 最初にend未満のIFをチェックしてから、Sorting_Threading（first、mid_val）、Sorting_Threading（mid_val + 1、end）、combine_array（first、mid_val、end）を呼び出します

• 関数の内部voidcombine_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、ktofirstとして宣言します。 。

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

  • iからtemp_2未満になるまでループFORを開始します。ループ内で、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 ++]

    を設定します

  • WHILE 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