정렬된 두 배열을 병합하기

정렬된 두 배열을 병합하기

문제

• 정렬된 두 배열을 한 배열에 병합하는 알고리즘을 구현해보자.

• arr1은 arr2를 포함할 충분한 공간이 있음.

예시

Input : arr1[20] = {1, 5, 9, 10, 15, 20};
        arr2[10] = {2, 3, 8, 13};
Output : arr1[20] = {1, 2, 3, 5, 8, 9, 10, 13, 15, 20};

null값을 제외한 배열의 길이 구하기

int arrlen(int arr[], int left, int right) {
    int mid = (left + right) / 2;
    if (arr[mid] == NULL) {
        if (mid == 0) {
            return 0;
        }else if (mid && arr[mid - 1] != NULL) {
            return mid;
        }
​
        return arrlen(arr, left, mid - 1);
    }
    else {
        return arrlen(arr, mid + 1, right);
    }
}

메인 함수

int main() {
    int arr1[20] = { 1, 5, 9, 10, 15, 20 };
    int arr2[10] = { 2, 3, 8, 13 };
​
    int len1 = arrlen(arr1, 0, sizeof(arr1) / sizeof(arr1[0]));
    int len2 = arrlen(arr2, 0, sizeof(arr2) / sizeof(arr2[0]));
    
    merge(arr1, arr2, len1, len2);
​
    for (int item : arr1) {
        if(item)
            printf("%d ", item);
    }
​
    return 0;
}

방법 1 : O(n1 + n2) 시간복잡도와 O(n1 + n2)의 추가적인 공간이 필요한 경우

1) 크기가 n1 + n2인 배열 arr3을 생성한다.

2) arr1과 arr2를 순회하면서 작은 수를 arr3에 순차적으로 대입한다.

3) arr1과 arr2에 남은 element가 있다면 arr3에 순차적으로 복사한다.

4) arr3을 arr1로 복사하고 메모리 해제.

void merge(int arr1[], int arr2[], int n1, int n2) {
    int* arr3 = new int[n1 + n2];
​
    int i = 0, j = 0, k = 0;
​
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j])
            arr3[k++] = arr1[i++];
        else
            arr3[k++] = arr2[j++];
    }
​
    while (i < n1) {
        arr3[k++] = arr1[i++];
    }
​
    while (j < n2) {
        arr3[k++] = arr2[i++];
    }
​
    for (int a = 0; a < k; a++) {
        arr1[a] = arr3[a];
    }
​
    delete[] arr3;
    arr3 = NULL;
} 

방법 2 : O(n1 * n2) 시간복잡도와 O(1)의 추가적인 공간이 필요한 경우

1) 기본적으로 삽입 정렬(Insertion Sort)과 같은 방식.

2) 작은 배열은 arr1로, 큰 배열은 arr2로 옮긴 뒤 합친다.

void merge(int arr1[], int arr2[], int n1, int n2) {
    //arr2의 마지막 원소부터 이터레이션

    for (int j = n2 - 1; j >= 0; j--) {
        //arr2[j]보다 크면서 가장 작은 수를 찾는다.
        //찾기 전까지 arr1의 원소들을 한 칸씩 이동.
        int i;
        int last = arr1[n1 - 1];
​
        for (i = n1 - 2; i >= 0 && arr1[i] > arr2[j]; i--) {
            arr1[i + 1] = arr1[i];
        }
​
        //찾은 경우
        if (i != n1 - 2 || last > arr2[j]) {
            arr1[i + 1] = arr2[j];
            arr2[j] = last;
        }
​
        //arr2를 arr1로 복사
        for (int a = n1, b = 0; a < n1 + n2; a++, b++) {
            arr1[a] = arr2[b];
        }
    }
}

참조

• https://www.geeksforgeeks.org/merge-two-sorted-arrays/