C++로 정렬되지 않은 두 배열을 정렬된 순서로 병합하는 방법

문제 설명

정렬되지 않은 두 개의 배열을 입력받아, 모든 요소를 하나의 새로운 배열에 담고 오름차순으로 정렬하는 함수를 작성하는 것이 목표입니다.

arr1[] = {10, 5, 7, 2}
arr2[] = {4, 17, 9, 3}
result[] = {2, 3, 4, 5, 7, 9, 10, 17}

알고리즘

접근 방법은 다음과 같습니다.
1. 정렬되지 않은 두 배열을 하나의 새로운 배열로 병합합니다.
2. 새로 만든 배열을 오름차순으로 정렬합니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

// 두 배열을 하나로 합친 뒤 정렬하는 함수
void mergeAndSort(int *arr1, int n1, int *arr2, int n2, int *result) {
   // 두 배열의 요소를 result에 차례대로 복사
   copy(arr1, arr1 + n1, result);
   copy(arr2, arr2 + n2, result + n1);
   // 병합된 배열을 오름차순으로 정렬
   sort(result, result + n1 + n2);
}

// 배열의 요소를 출력하는 함수
void displayArray(int *arr, int n) {
   for (int i = 0; i < n; ++i) {
      cout << arr[i] << " ";
   }
   cout << endl;
}

int main() {
   int arr1[] = {10, 5, 7, 2};
   int arr2[] = {4, 17, 9, 3};
   int result[SIZE(arr1) + SIZE(arr2)];

   cout << "첫 번째 배열:" << endl;
   displayArray(arr1, SIZE(arr1));

   cout << "두 번째 배열:" << endl;
   displayArray(arr2, SIZE(arr2));

   mergeAndSort(arr1, SIZE(arr1), arr2, SIZE(arr2), result);

   cout << "병합 후 정렬된 배열:" << endl;
   displayArray(result, SIZE(arr1) + SIZE(arr2));

   return 0;
}

코드 설명

입력 배열이 정렬되어 있지 않기 때문에, 두 배열의 요소를 std::copy로 result 배열에 그대로 이어 붙인 뒤 std::sort로 한 번에 정렬하는 방식을 사용했습니다. SIZE 매크로는 배열 전체 크기를 요소 하나의 크기로 나누어 요소 개수를 계산해 주며, displayArray 함수는 배열의 내용을 공백으로 구분해 출력합니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

첫 번째 배열:
10 5 7 2
두 번째 배열:
4 17 9 3
병합 후 정렬된 배열:
2 3 4 5 7 9 10 17

시간 복잡도

배열 복사에 O(n1 + n2), 정렬에 O(N log N)(N = n1 + n2)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다.