멀티스레딩을 사용하여 C++에서 병합 정렬 구현

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

Merge sort

병합 정렬은 배열을 두 개의 동일한 반으로 나눈 다음 이를 하나의 분할 정복 기술에 기반한 정렬 기술입니다. 정렬 방식 결합.

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

• 요소가 있는지 확인하세요.

• 그렇지 않으면 더 이상 분할할 수 없을 때까지 데이터를 재귀적으로 반으로 분할합니다.

• 마지막으로 작은 목록을 정렬된 순서로 새 목록으로 병합합니다.

멀티스레딩

운영 체제에서 스레드는 일부 작업을 수행하는 경량 프로세스입니다. 스레드는 공통 리소스를 공유하여 작업을 동시에 수행합니다.

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

예:

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

Output−정렬된 배열은 1, 2, 3, 4, 5, 7, 8, 9, 10

설명- 정수 값이 포함된 정렬되지 않은 배열을 얻습니다. 이제 다중 스레드 병합 정렬을 사용하여 배열을 정렬하겠습니다.

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

Output−정렬된 배열은 1, 3, 5, 21, 32, 45, 50입니다.

Explanation− 정수 값을 갖는 정렬되지 않은 배열이 제공됩니다. 이제 다중 스레드 병합 정렬을 사용하여 배열을 정렬하겠습니다.

아래 프로그램에서 사용된 메소드는 다음과 같습니다. -

• 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), Combine_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로 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 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 .

    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]

  • 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++]

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!