티스토리 뷰

정렬 ( Sort )

병합 정렬 ( Merge sort )

RiKang 2017. 12. 12. 21:31
반응형

Table of Contents


개요

병합

병합 정렬

문제

STL sort

시간복잡도 계산




1. 개요


 병합 정렬은 원소들을 번호순, 사전순과 같이 정해진 순서대로 열거하는 정렬 알고리즘 중 하나입니다. 정렬된 두 집합을 하나의 정렬된 집합으로 합치는(병합하는)데에 필요한 시간복잡도가 O ( 두 집합의 원소의 갯수 ) 라는 점, 그리고 분할정복을 이용하여 병합 정렬을 구현하면 총 시간복잡도 O ( N log N ) 만에 정렬이 가능합니다.


 이 문서에서는 병합 정렬을 이용하여, 숫자들을 오름차순으로 정렬하는 방법을 소개합니다.




2. 병합


 병합 정렬을 구현하기 위해선, 정렬된 두 집합을 하나의 집합으로 합치는 함수를 구현해야 합니다.

 예시 ) A = {1, 3}, B = {2, 4}  -> {1, 2, 3, 4}


 이 병합은 아래와 같은 알고리즘으로 가능합니다.


정렬된 집합 A 와 B를 병합하여 정렬된 집합 C를 만드는 알고리즘



1.  A에서 가장 작은 원소와 B 에서 가장 작은 원소를 비교한다.

2. 둘 중 작은 원소를 집합 C 에 넣는다.

3. 해당 원소를 기존의 집합 ( A or B ) 에서 제외한다.

4. 집합 A 와 B 가 공집합이 될 때까지 위 1~3 과정을 반복한다.


 예시를 통해 위의 알고리즘을 따라가 보겠습니다. 우선 예시에서 쓸 A, B, C의 초기 상태는 다음과 같습니다.


A = { 1, 3 }, B = { 2, 4 }, C={ }


1.  A에서 가장 작은 원소와 B 에서 가장 작은 원소를 비교한다. -> 1 < 2


2. 둘 중 작은 원소를 집합 C 에 넣는다. -> A = { 1, 3 }, B = { 2, 4 },  C = { 1 }


3. 해당 원소를 기존의 집합 ( A or B ) 에서 제외한다. -> A = { 3 }, B = { 2, 4 },  C = { 1 }


4. 반복 -----------------------------------------------------------------------------------------------------------


1.  A에서 가장 작은 원소와 B 에서 가장 작은 원소를 비교한다. -> 3 > 2


2. 둘 중 작은 원소를 집합 C 에 넣는다. -> A = { 3 }, B = { 2, 4 },  C = { 1, 2 }


3. 해당 원소를 기존의 집합 ( A or B ) 에서 제외한다. -> A = { 3 }, B = { 4 },  C = { 1, 2 }


4. 반복 -----------------------------------------------------------------------------------------------------------


1.  A에서 가장 작은 원소와 B 에서 가장 작은 원소를 비교한다. -> 3 < 4


2. 둘 중 작은 원소를 집합 C 에 넣는다. -> A = { 3 }, B = { 4 },  C = { 1, 2, 3 }


3. 해당 원소를 기존의 집합 ( A or B ) 에서 제외한다. -> A = {  }, B = { 4 },  C = { 1, 2, 3 }


4. 반복 -----------------------------------------------------------------------------------------------------------


1.  A에서 가장 작은 원소와 B 에서 가장 작은 원소를 비교한다. -> A 는 공집합이므로 B를 선택한다.


2. 둘 중 작은 원소를 집합 C 에 넣는다. -> A = {  }, B = { 4 },  C = { 1, 2, 3, 4 }


3. 해당 원소를 기존의 집합 ( A or B ) 에서 제외한다. -> A = {  }, B = { },  C = { 1, 2, 3, 4 }


4. 반복 끝 -----------------------------------------------------------------------------------------------------------


집합 A의 원소의 개수가 N, B의 원소의 개수가 M 이라고 하면 C를 만드는 시간 복잡도는 O(N+M) 이 됩니다.


C++ STL 의 vector 를 이용하면 아래와 같이 구현할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//code by RiKang, weeklyps.com
 
// Line 11 : 정렬된 v1, v2 를 병합한 ret 를 반환한다.
// Line 13 : 구현의 편의성을 위해 v1[0] ~ v1[p1-1] 의 원소들은 v1에서 제외된 원소들이라고 하자.
// Line 13 : 자연스럽게 v1에서 남은 원소들은 v1[p1] ~ v1[v1.size()-1] 이 된다.
// Line 15 : v1 에 남은 원소 중 가장 작은 원소 v1[p1]과 v2에 남은 원소 중 가장 작은 원소 v1[p2] 를 비교한다.
// Line 15 : 둘 중 하나가 공집합인 경우에 유의해야 한다.
// Line 16 : v1[p1] 을 ret 에 넣고, v1[p1] 을 v1에서 제외하기 위해 p1++을 한다.
// Line 18 : v2[p2] 을 ret 에 넣고, v2[p2] 을 v2에서 제외하기 위해 p2++을 한다
 
vector<int> merge(vector<int>& v1, vector<int>& v2){
    vector<int> ret(v1.size()+v2.size());
    int p1 = 0, p2 = 0;
    for(int i=0; i<ret.size(); i++){
        if(p1!=v1.size() && (p2==v2.size() || v1[p1] < v2[p2]))
            ret[i] = v1[p1++];
        else
            ret[i] = v2[p2++];
    }
    return ret;
}
cs




3. 병합 정렬


 아래의 분할정복 알고리즘을 따라가면 시간복잡도 O ( N log N ) 만에 정렬을 할 수 있습니다.


1.  집합을 두 개의 집합으로 나눈다. ( 두 집합의 원소의 개수가 최대한 비슷하도록 나눈다. 즉, 반으로 나눈다.)


2.  나누어진 두 집합을 병합 정렬로 정렬한다.


3.  정렬된 두 집합을 병합한다.


{ 1, 4, 2, 6, 3, 7, 10, 5 } 를 분할정복을 통해 병합정렬로 정렬하는 과정을 나타내보면 아래와 같이 됩니다.





 간단한 분할정복이므로, 짧게 구현이 가능합니다. 구현시 merge() 함수는 병합 정렬에 맞도록 변형해주는 것이 효율적입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//code by RiKang, weeklyps.com
 
void merge(vector<int>& v, int st, int mid, int en){
    vector<int> ret(en-st);
    int p1 = st, p2 = mid;  // v[st] ~ v[mid-1] 구간과 v[mid] ~ v[en-1] 구간을 병합해야 하므로 p1=st, p2=mid 로 초기화.
    for(int i=0; i<ret.size(); i++){
        if(p1!=mid && (p2==en || v[p1] < v[p2]))
            ret[i] = v[p1++];
        else
            ret[i] = v[p2++];
    }
    for(int i=st; i<en; i++)
        v[i] = ret[i-st];
}
 
void merge_sort(vector<int>& v, int st, int en){ // [st,en), 즉, v[st] ~ v[en-1] 구간을 정렬한다.
    if(en-st<2return;     // 구간의 크기가 1 이하라면 정렬할 필요가 없다. 기저 사례 (base case).
    int mid = (st+en)/2;    // 구간을 [st,mid) 와 [mid, en) 으로 나눈다.
    merge_sort(v, st, mid); // 앞 구간을 정렬한다.
    merge_sort(v, mid, en); // 뒤 구간을 정렬한다.
    merge(v, st, mid, en);  // 두 구간을 병합한다.
}
cs




4. 문제






5. STL sort


 C++ STL 에는 sort 함수가 있으므로 위와 같은 병합정렬을 직접 구현하는 일은 적습니다. 이 함수를 사용한다면, 위의 기본문제를 아래와 같이 구현 가능합니다.



 다만, 굳이 정렬이 아니더라도 병합정렬의 아이디어는 다양한 상황에 응용할 수 있으며, 또한 그 자체로도 분할정복의 좋은 예시로 유명하기 때문에 알아두는 것이 좋습니다.




6. 시간복잡도 계산


 위의 병합정렬 코드에서, 많이 수행되는 연산은 Line 13 : v[i] = ret[i-st]; 이며 이 연산이 M 번 수행되었다고 할 때 전체 수행 연산이 (임의의 상수)C * M 이하임을 증명하는 건 어렵지 않습니다.


 따라서 v[i] = ret[i-st]; 연산의 수행 횟수가 C * N * log N 이하라면, 총 시간복잡도도 O(NlogN) 임을 보일 수 있습니다.


 그런데 각각의 v[i] 들은 이 연산을 최대 log N 번 수행합니다. 집합이 최대 log N 번 분할 되기 때문이지요.


 i = 0 ~ N-1 까지 가능하므로 결국,  v[i] = ret[i-st]; 연산의 수행 횟수는 C * N * log N 이하입니다.


 더 간단하게 이해하고 싶다면, 아래의 그림을 통해 확인하는 방법이 있습니다.




 각각의 깊이에 있는 merge 함수들의 시간복잡도의 합은 O(N) 이고, 깊이는 log N 까지 있으므로  단하게 곱해서 O( N log N ) 이라고 생각할 수 있습니다.


 반대로 엄밀하게 시간복잡도를 증명하고 싶다면,


F(1) = 1

F(N) = F(N/2) + F(N/2) + 상수 * N


 위의 식에서 F(N) < C * N * log N 이 되는 C가 존재함을 증명해야 합니다.


※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com


반응형