병합정렬 구현하기, C++

병합 정렬이란 잘 알려진 정렬 알고리즘 중 하나다.

 

분할 정복이라는 간단한 아이디어이다.

많은 원소를 가지고 있더라도 작은 크기로 쪼개서 각각을 정렬한 다음

정렬된 부분집합을 정렬상태를 유지하면서 합치는 방식이다.

 

코드로 구현해보자

 

#include <iostream>
#include <vector>


//벡터를 임의의 원소가 들어가도 괜찮게 템플릿 선언후
//벡터 2개의 참조변수를 이용한다.
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();
    
    //차례대로 원소를 비교해나간다. -> 2개의 벡터를 받아서 가장 첫번째 원소부터 비교한다.
    //결국 arr1과 arr2의 모든 원소를 비교해본다.
    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);

    }
    //즉, merged에는 2개의 벡터에 대해서 오름차순으로 정렬되어서 넣어진다.

    return merged;
    
}

//즉, merge 자체는 2개의 벡터를 받아서 차례대로 비교 후 집어넣는 것이라 할 수 있다.
//다만 while문을 나가서 저기 merged에 그냥 넣는 것은 정렬이 안된 채로 집어넣는 것이다.

//그래서 우리는 병합정렬의 크기를 최소로 만들어버린다.
//그렇게 되면 정렬된 채로 합쳐질 것이고 for문에서 그냥 나머지를 넣는 작업도
//정렬된 원소를 넣는 작업이 될 것이다.

//이제는 병합정렬에 쓰일 벡터를 최소로 만들기 위한 재귀작업을 해보자
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;

}

//merge는 실제로 2개의 벡터에 대해 정렬하는 작업이고
//merge_sort재귀 함수는 현재의 벡터를 2개로 쪼개서 각각을 merge에 적용시키는 작업을 한다.

 

즉, 쪼개는 작업과 정렬하는 작업이 따로 있고 합쳐지면 그게 병합정렬이 된다.

여기서 조금 더 발전된 것이 퀵정렬이라고 보면 되겠다.

하지만 퀵정렬이 꼭 더 나은 것을 보장하는 것은 아니다