[Algorithm/Divide&Conquer] 03. Merge Sort(병합 정렬)

분할 정복을 이용한 정렬 알고리즘

유명한 알고리즘 문제 중의 하나인 정렬(sorting)을 분할 정복으로 구현하는 방법에 대해 알아보자

 

정렬 알고리즘 구현에 있어 필요한 요구사항

• 모든 데이터 타입에 대해 동작해야 한다. 심지어 C++ 구조체, 클래스에 대해서도 서로 다른 멤버를 기준으로 정렬할 수 있어야 한다
• 많은 양의 데이터를 처리할 수 있어야 한다.
• 점근적 시간 복잡도 측면이나 실제 동작 시에 빠르게 동작한다

현실적으로 두 번째와 세 번째 요구사항을 동시에 만족하기는 어렵다.

 

두 번째 요구사항은 외부 정렬(external sorting), 즉 컴퓨터의 메모리에 데이터가 상주하지 않은 상태에서 수행되는 정렬을 필요로 한다.

외부 정렬 알고리즘은 실행 중 임의 시점에서 전체 데이터의 일부만을 메모리에 올려놓고 동작할 수 있다.

과거에 컴퓨터는 불과 수백 바이트 정도밖에 안되는 메인 메모리를 가지고 있어서, 모든 데이터를 정렬하기 위해서는 외부 정렬 알고리즘을 사용할 수 있어야 했다.

 

먼저, 외부 정렬 알고리즘 중 하나인 병합 정렬에 대해서 알아보자.

 

병합 정렬(merge sort) (a.k.a 합병 정렬)

많은 원소로 구성된 전체 집합을 작은 크기의 부분 집합으로 나눠 각각을 정렬하고, 정렬된 부분집합을 오름차순 또는 내림차순 순서를 유지하면서 합치는 방식이다.

 

• 전체 배열을 여러 개의 부분 배열로 나누는 작업을 반복한다
  • 이 작업은 각 부분 배열이 하나의 원소만 가질 때 멈춘다(1~4단계)
• 이후 다시 배열을 합치는 작업을 반복하며, 이 때 합쳐진 배열의 원소 순서가 오름차순을 유지하도록 조정한다.

EX) 마지막 단계에서 (2, 5, 7, 8)과 (1, 3, 4, 6)을 합치는 과정

 

병합 정렬 구현(C++)

// conquer, combine 과정에 대한 함수
template <typename T>
std::vector<T> merge(std::vector<T>& arr1, std::vector<T>& arr2) {
    std::vector<T> merged;

    auto iter1 = arr1.begin();
    auto iter2 = arr1.end();

    while (iter1 != arr1.end() && iter2 != ar2.end()) {
        if (*iter1 < *iter2) {
            merged.emplace_back(*iter1);
            iter1++;
        }
        else {
            merged.emplace_back(*iter2);
            iter2++;
        }
    }
    // 오른쪽 vector만 끝에 도달한 경우
    if (iter1 != end()) {
        for (; iter1 != arr1.end(); iter1++) {
            merged.emplace_back(*iter1);
        }
    }
    // 왼쪽 vector만 끝에 도달한 경우
    else {
        for (; iter2 != arr2.end(); iter2++) {
            merged.emplace_back(*iter2);
        }
    }
    return merged;
}

// 재귀적으로 병합 정렬하는 함수(merge 함수를 call)
template <typename T>
std::vector<T> merge_sort(std::vector<T> arr) {
    if (arr.size() > 1) {
        // 배열의 크기가 1이 될 때 까지 쪼개기 (Divide)
        auto mid = size_t(arr.size() / 2);
        auto left_half = merge_sort<T>(std::vector<T>(arr.begin(), arr.begin() + mid));
        auto right_half = merge_sort<T>(std::vector<T>(arr.begin() + mid, arr.end()));

        // Conquer, Combine
        return merge<T>(left_half, right_half);
    }
}

 

 

테스트 프로그램

#include <iostream>
#include <vector>

template <typename T>
std::vector<T> merge(std::vector<T>& arr1, std::vector<T>& arr2)
{
    std::vector<T> merged;
    
    auto iter1 = arr1.begin();
    auto iter2 = arr2.begin();
    
    while(iter1 != arr1.end() && iter2 != arr2.end())
    {
        if(*iter1 < *iter2)
        {
            merged.emplace_back(*iter1);
            iter1++;
        }
        else
        {
            merged.emplace_back(*iter2);
            iter2++;
        }
    }
    
    if(iter1 != arr1.end())
    {
        for(; iter1 != arr1.end(); iter1++)
        {
            merged.emplace_back(*iter1);
        }
    }
    else 
    {
        for(; iter2 != arr2.end(); iter2++)
        {
            merged.emplace_back(*iter2);
        }
    }
    
    return merged;
}

template <typename T>
std::vector<T> merge_sort(std::vector<T> arr)
{
    if(arr.size() > 1)
    {
        auto mid = size_t(arr.size() / 2);
        
        auto left_half = merge_sort<T>(std::vector<T>(arr.begin(), arr.begin() + mid));
        auto right_half = merge_sort<T>(std::vector<T>(arr.begin() + mid, arr.end()));
    
        return merge<T>(left_half, right_half);
    }
    
    return arr;
}

template <typename T>
void print_vector(std::vector<T> arr)
{
    for(auto i : arr)
        std::cout << i << " ";
        
    std::cout << std::endl;
}

void run_merge_sort_test()
{
    std::vector<int> S1 { 45, 1, 3, 1, 2, 3, 45, 5, 1, 2, 44, 5, 7 };
    std::vector<float> S2 { 45.6f, 1.0f, 3.8f, 1.01f, 2.2f, 3.9f, 45.3f, 5.5f, 1.0f, 2.0f, 44.0f, 5.0f, 7.0f };
    std::vector<double> S3 { 45.6, 1.0, 3.8, 1.01, 2.2, 3.9, 45.3, 5.5, 1.0, 2.0, 44.0, 5.0, 7.0 };
    std::vector<char> C { 'b', 'z', 'a', 'e', 'f', 't', 'q', 'u', 'y' };
    
    std::cout << "정렬되지 않은 입력 벡터" << std::endl;
    
    print_vector<int>(S1);
    print_vector<float>(S2);
    print_vector<double>(S3);
    print_vector<char>(C);
    std::cout << std::endl;
    
    auto sorted_S1 = merge_sort<int>(S1);
    auto sorted_S2 = merge_sort<float>(S2);
    auto sorted_S3 = merge_sort<double>(S3);
    auto sorted_C = merge_sort<char>(C);
    
    std::cout << "병합 정렬에 의해 정렬된 벡터" << std::endl;
    
    print_vector<int>(sorted_S1);
    print_vector<float>(sorted_S2);
    print_vector<double>(sorted_S3);
    print_vector<char>(sorted_C);
    std::cout << std::endl;
}

int main()
{
    run_merge_sort_test();

    return 0;
}

 

병합 정렬의 시간 복잡도

• 각 층을 살펴보면 모든 숫자가 합병에 참여한다
• 합병은 입력 크기에 비례하므로, 각 층에서 수행된 비교 횟수는 O(n)이다.
• 입력을 1/2로 나누다가 더 이상 나눌 수 없는 크기인 1이 되면 분할이 중단되므로, log_2 (n) 층이 생긴다.
• 시간 복잡도
  • (층수) X (각 층수의 복잡도) = log_2 (n) X O(n)
  • O(nlogn)

병합 정렬의 단점

• 공간 복잡도 : O(n)
• 입력을 위한 메모리 공간 이외에 추가로 입려고가 같은 크기의 공간(임시 배열)이 별도로 필요
  • 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문

응용

• 외부 정렬
• 연결 리스트에 있는 데이터를 정렬할 때 퀵정렬이나 힙정렬보다 훨씬 효율적이다
• 멀티코어 CPU에서 정렬 알고리즘을 병렬화하는데 이용

 

Ref) 코딩 테스트를 위한 자료 구조와 알고리즘 with C++

Ref) 알기쉬운 알고리즘