정렬 - 합병정렬(Merge Sort)

합병정렬(Merge Sort)

오늘은 마지막으로 알아볼 정렬인 합병정렬입니다. 합병정렬 또한 이전에 살펴 본 퀵정렬과 같은 분할 정복 방식을 채택한 알고리즘으로 결과적으로는 퀵정렬과 동일한 O(nlogn)의 시간복잡도를 가집니다. 하지만 여러 상황에 따라 퀵정렬과는 차이점이 존재하니 자세히 살펴봐야 합니다.

#include <iostream>
using namespace std;

// 두 개의 정렬된 부분 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int* leftArr = new int[n1];
    int* rightArr = new int[n2];
    
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = leftArr[i];
        i++; k++;
    }
    
    while (j < n2) {
        arr[k] = rightArr[j];
        j++; k++;
    }
    
    delete[] leftArr;
    delete[] rightArr;
}

// 합병 정렬 구현
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        merge(arr, left, mid, right);
    }
}

// 배열 출력 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    
    cout << "정렬 전 배열: ";
    printArray(arr, arrSize);
    
    mergeSort(arr, 0, arrSize - 1);
    
    cout << "정렬 후 배열: ";
    printArray(arr, arrSize);
    
    return 0;
}

 

소스코드만 보면 상당히 길고 복잡해 보입니다. 하지만 개념만 놓고 보면 그리 복잡하지 않습니다. 합병정렬과 퀵정렬의 가장 큰 차이점은 퀵정렬은 피벗 값에 따라 편향된 분할을 진행할 가능성이 있기 때문에 최악의 경우 성능이 O(n^2)까지 갈 수 있는 반면, 합병정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(nlogn)을 보장합니다.

 

이제 합병정렬의 동작과정을 살펴보겠습니다.

 

1. 분할(Divide) : 리스트의 길이가 1이 될 때까지 리스트를 절반으로 나눕니다.

2. 정복(Conquer) : 리스트의 길이가 1이 되면, 이를 정렬된 상태로 간주합니다.

3. 병합(Merge) : 나뉘어진 두 리스트를 정렬된 상태로 병합합니다.

 

동작 예시를 보여드리겠습니다. 리스트 [38, 27, 43, 3, 9, 82, 10] 가 있을 때, 1단계 분할을 통해 리스트를 절반으로 나눕니다. [38, 27, 43]과 [3, 9, 82, 10]으로 나뉩니다. 각 리스트를 다시 나눠서 전부 나눠지도록 합니다. 그 다음 2단계 정복을 시작합니다. 각 리스트는 개별 원소로 나뉘었으므로 정렬된 상태로 간주합니다. 마지막 3단계 병합을 통해 정렬된 리스트를 병합합니다. [27]과 [43]을 병합하면 [27, 43]이 되고 [82]와 [10]을 병합하면 [10, 82]가 됩니다. [27, 43]과 [38]을 병합하면 [27, 38, 43]이 되고, [3, 9]와 [10, 82]를 합치면 [3, 9, 10, 82]가 됩니다. 이런 식으로 전부 합치면 최종적으로 정렬된 [3, 9, 10, 27, 38, 43, 82]가 됩니다.

 

합병정렬의 특징

시간복잡도 : O(nlogn)
=> 합병정렬은 항상 O(nlogn)의 시간복잡도를 가집니다.
 
공간복잡도 : O(n)
=> 합병정렬은 추가적인 메모리 공간이 필요한 알고리즘입니다. 리스트를 나눌 때 새로운 리스트를 만들어 병합하는 과정을 거치기 때문에, 리스트 크기만큼의 추가 메모리가 필요합니다.

안정성 : 안정정렬
=> 동일한 값을 가진 원소들이 정렬 후에도 원래의 상대적인 순서가 유지됩니다. (같은 값의 데이터를 처리할 때 중요한 경우에 유용)

장단점
장점
- 일정한 시간복잡도
- 안정정렬
- 대규모 데이터 정렬에 적합

- 외부 정렬에 적합 : 추가 메모리를 사용할 수 있는 환경에서 유용

단점
- 추가 메모리 사용
- 작은 데이터에 비효율적

 

합병정렬의 활용

1. 큰 데이터 세트 : 합병정렬은 큰 데이터 세트에서 일관된 성능을 제공하므로 데이터 양이 많을 때 적합합니다.

2. 외부 정렬 : 메모리가 한정된 환경에서 외부 장치(ex : 디스크)에 있는 데이터를 정렬해야 하는 경우, 합병정렬은 데이터를 부분적으로 읽어 병합하기 때문에 효율적입니다.

3. 안정정렬이 필요한 경우 : 정렬 후에도 같은 값의 데이터가 기존 순서를 유지해야 할 때 합병 정렬이 유리합니다.

 

결론적으로 합병정렬은 시간 복잡도가 O(nlogn)으로 일정하고, 안정적인 정렬을 보장하는 강력한 알고리즘입니다. 다만 추가적인 메모리 공간을 필요로 한다는 단점이 있으며, 데이터 크기가 작을 경우에는 다른 알고리즘(ex : 삽입정렬)이 더 효율적일 수 있습니다. 그러나 대규모 데이터나 외부 메모리를 사용하는 경우에는 매우 유용한 알고리즘입니다.

 

NEXT

이렇게 정렬에 대한 부분은 끝내려고 합니다. 사실 깊게 파고들면 더 많은 정렬 알고리즘이 존재하지만, 일반적으로 많이 사용되고 알려진 알고리즘을 정리해 보았습니다. 다음부터는 코딩테스트나 가벼운 수학 문제에서 등장하는 알고리즘들을 살펴보도록 하겠습니다. 감사합니다.