[C++] 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

• 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨.
• 병합 알고리즘은 다음과 같은 과정으로 정렬을 수행함.
  • ① 많은 원소로 구성된 전체 집합을 작은 크기의 부분 집합 으로 나눔.
    • ② 각각의 부분 집합을 정렬함.
    • ③ 정렬된 부분 집합을 오름차순 또는 내림차순 순서를 유지함.
  • ④ 각각의 부분 집합을 합침.

• 그림) 병합 정렬을 사용하여 정수 배열을 정렬하는 예
  • 전체 배열을 여러 개의 부분 배열로 나누는 작업을 반복함.
    • 각 부분 배열이 하나의 원소를 가질 때 멈춤. (1단계 ~ 4단계)
  • 이후에는 다시 배열을 합치는 작업을 반복함.
    • 합쳐진 배열의 원소 순서가 오름차순을 유지하도록 조정함.

 

코드

• 템플릿을 사용하여 정렬할 데이터 타입에 의존적이지 않도록 함.
• 오직 컨테이너에서 지원하는 함수만을 사용함.

#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;
}

 

결과

정렬되지 않은 입력 벡터:
45 1 3 1 2 3 45 5 1 2 44 5 7
45.6 1 3.8 1.01 2.2 3.9 45.3 5.5 1 2 44 5 7 
45.6 1 3.8 1.01 2.2 3.9 45.3 5.5 1 2 44 5 7 
b z a e f t q u y

병합 정렬에 의해 정렬된 벡터:
1 1 1 2 2 3 3 5 5 7 44 45 45
1 1 1.01 2 2.2 3.8 3.9 5 5.5 7 44 45.3 45.6 
1 1 1.01 2 2.2 3.8 3.9 5 5.5 7 44 45.3 45.6 
a b e f q t u y z