C++에서 멀티스레딩을 사용한 병합 정렬

<시간/>

정렬되지 않은 정수 배열이 제공됩니다. 작업은 멀티스레딩을 통해 구현된 병합 정렬 기술을 사용하여 배열을 정렬하는 것입니다.

병합 정렬

병합 정렬은 배열을 같은 반으로 나눈 다음 정렬된 방식으로 결합하는 분할 정복 기술을 기반으로 하는 정렬 기술입니다.

병합 정렬을 구현하는 알고리즘은

목록에 하나의 요소가 있는지 확인한 다음 요소를 반환합니다.
그렇지 않으면 데이터를 더 이상 나눌 수 없을 때까지 재귀적으로 두 부분으로 나눕니다.
마지막으로 작은 목록을 정렬된 순서로 새 목록으로 병합합니다.

멀티 스레딩

운영 체제에서 스레드 작업의 일부를 실행하는 책임이 있는 경량 프로세스입니다. 스레드는 작업을 동시에 실행하기 위해 공통 리소스를 공유합니다.

멀티 스레딩 단일 프로세서에서 여러 스레드를 실행하여 작업을 동시에 실행할 수 있는 멀티태스킹 구현입니다. 단일 애플리케이션 내의 특정 작업을 개별 스레드로 세분화합니다. 각 스레드는 병렬로 실행될 수 있습니다.

예:

에서 -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, (크기 - 1)/2, 크기 - 1)
정수형의 arr[]에 저장된 정렬된 배열을 출력합니다.
void* Sorting_Threading(void* arg)
함수 내부
- 변수를 temp_val++에 set_val로 선언하고, 먼저 set_val * (크기 / 4)로, 끝을 (set_val + 1) * (크기 / 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);
  를 호출합니다.
함수 내부 void Sorting_Threading(int first, int end)
- 변수를 mid_val to 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로 선언 .
- temp_1보다 작아질 때까지 루프 FOR를 i에서 0으로 시작합니다. 루프 내에서 start[i]를 arr[i + first]로 설정합니다.
- i에서 0까지 루프 FOR를 시작하여 i가 temp_2보다 작아집니다. 루프 내에서 last[i]를 arr[i + mid_val + 1]
  으로 설정합니다.
- i를 j로 0으로 설정합니다. 루프를 시작합니다. while i는 temp_1보다 작고 j는 temp_2보다 작습니다. while 내부에서 IF start[i]가 last[j]보다 작은지 확인한 다음 arr[k++]를 start[i++]로 설정합니다. 그렇지 않으면 arr[k++] =마지막[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