C++의 3방향 병합 정렬

병합 정렬은 배열을 재귀적으로 두 부분으로 나누고 정렬하고 마지막으로 병합하는 것을 포함합니다. 병합 정렬의 변형은 배열을 2부분으로 나누는 대신 3부분으로 나누는 3방향 병합 정렬로 처리됩니다.

병합 정렬은 재귀적 방식으로 배열을 절반 크기의 하위 배열로 나눕니다. 같은 방식으로 3방향 병합 정렬은 배열을 1/3 크기의 하위 배열로 나눕니다.

예시

Input : 46, -1, -44, 79, 31, -41, 11, 20 , 74, 94
Output : -44 -41 -1 11 20 31 46 74 79 94

Input : 24, -18
Output : -18 24

3방향 병합 정렬의 시간 복잡도는 nlog₃입니다. 명.

예시

// C++ Program for performing 3 way Merge Sort
#include <bits/stdc++.h>
usingnamespacestd;
voidmerge1(intgArray1[], intlow1, intmid1,
intmid2, inthigh1, intdestArray1[]){
   inti = low1, j = mid1, k = mid2, l = low1;
   // choose smaller of the smallest in the three ranges
   while((i < mid1) && (j < mid2) && (k < high1)){
      if(gArray1[i] < gArray1[j]){
         if(gArray1[i] < gArray1[k]){
            destArray1[l++] = gArray1[i++];
         }
         else{
               destArray1[l++] = gArray1[k++];
            }
      }
   else{
         if(gArray1[j] < gArray1[k]){
            destArray1[l++] = gArray1[j++];
         }
   else{
         destArray1[l++] = gArray1[k++];
      }
   }
}
while((i < mid1) && (j < mid2)){
   if(gArray1[i] < gArray1[j]){
      destArray1[l++] = gArray1[i++];
   }
   else{
      destArray1[l++] = gArray1[j++];
   }
}
while((j < mid2) && (k < high1)){
   if(gArray1[j] < gArray1[k]){
   destArray1[l++] = gArray1[j++];
}
else{
      destArray1[l++] = gArray1[k++];
   }
}
while((i < mid1) && (k < high1)){
         if(gArray1[i] < gArray1[k]){
            destArray1[l++] = gArray1[i++];
         }
   else{
         destArray1[l++] = gArray1[k++];
      }
   }
   while(i < mid1)
   destArray1[l++] = gArray1[i++];
   while(j < mid2)
   destArray1[l++] = gArray1[j++];
   while(k < high)
   destArray1[l++] = gArray1[k++];
}
voidmergeSort3WayRec(intgArray1[], intlow1,
inthigh1, intdestArray1[]){
   if(high1 - low1 < 2)
   return;
   intmid1 = low1 + ((high1 - low1) / 3);
   intmid2 = low1 + 2 * ((high1 - low1) / 3) + 1;
   mergeSort3WayRec(destArray1, low1, mid1, gArray1);
   mergeSort3WayRec(destArray1, mid1, mid2, gArray1);
   mergeSort3WayRec(destArray1, mid2, high1, gArray1);
   merge(destArray1, low1, mid1, mid2, high1, gArray1);
}
voidmergeSort3Way(intgArray1[], intn1){
   if(n1 == 0)
   return;
   intfArray1[n];
   for(inti = 0; i < n1; i++)
   fArray1[i] = gArray1[i];
   // sort function
   mergeSort3WayRec(fArray1, 0, n, gArray1);
   for(inti = 0; i < n1; i++)
   gArray1[i] = fArray1[i];
}
// Driver Code
intmain(){
   intdata1[] = {46, -1, -44, 79, 31,
   -41, 11, 20, 74, 94};
   mergeSort3Way(data1,10);
   cout<< "After 3 way merge sort: ";
   for(inti = 0; i < 10; i++){
         cout<< data1[i] << " ";
      }
   return0;
}

출력

After 3 way merge sort: -44 -41 -1 11 20 31 46 74 79 94