Algorithm/알고리즘_개념

[Merge Sort] 병합 정렬

레에몽 2021. 3. 22. 15:10

 Merge Sort는 분할해서 정렬하는 대표적인 알고리즘 중 하나이다. Quick Sort는 최악의 경우 시간 복잡도 O(N^2)이 되는 반면, Merge Sort는 최악의 경우에도 시간복잡도가 O(N * logN)을 유지한다. 하지만, 실제로 O(N * logN)인 상황에서는 Quick Sort가 제일 빨라서 최악의 경우를 만나지 않게끔 코드를 짠다. 이는 다른 게시글에 업데이트 하겠다.

 

 Merge Sort의 아이디어는 "반으로 먼저 쪼개고, 정렬한다." 반으로 쪼개는 것은 어렵지 않다. 다음과 같이 수행해보자.

기존에 {35, 13, 2, 7, 11, 44, 12} 배열이 있으면 반으로 계속해서 쪼개 나가는 것이다.

 

3단계에 걸쳐 모든 부분집합의 크기를 1로 만들었다. 그렇다면 반대로 부분집합들을 모두 병합하는데 필요한 단계는 몇일까? 나누어 준걸 반대로 순차적으로 병합한다고 생각해보면 역시 3단계이다.

 

그러면 병합할 때는 어떻게 병합을 하면 될까? 답은 간단하다. 

"데이터를 비교해주면서 병합을 해주면 된다. 그러면 부분집합은 항상 정렬되어있다." 정렬된 부분집합을 합치기에, 데이터를 비교하는데는 N번의 계산과정이 필요하다.

 

집합을 합치는 과정은 아래와 같다.

A 부분집합 {35} 의 index가 0인 애랑, B 부분집합 {13} 의 index가 0인애 중에서 더 작은 애를 먼저 다른 배열에 넣는다. 13이 더작기 때문에 B를 가리키고 있는 index를 증가시킨다. B에서는 더 비교할 대상이 없고, A의 index가 가리키는 애들을 넣어준다. 그렇게 {13, 35}라는 배열이 생긴다. 코드로 살펴보자.

 

1
2
3
4
5
6
7
8
9
void mergeSort(int arr[], int left, int right){
    // left < right인 경우는 부분집합의 크기가 1인 경우.
    if(left < right){
        int mid = (left + right) / 2// 반으로 쪼갠다.
        mergeSort(arr, left, mid);  // arr을 left ~ mid로 나눈다.
        mergeSort(arr, mid + 1, right); // arr을 mid +1 ~ right로 나눈다.
       merge(arr, left, mid, right); // 병합
    }
}
cs
 
 먼저 mergeSort는 반으로 나누어서 계속해서 쪼갠 다음에 하나씩 merge해준다.
merge를 후위에 놔둠으로써 최대한 쪼개고 더이상 쪼갤 수 없을 때부터 차례로 merge를 해준다.

 

merge함수의 일부분이다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(int arr[], int left, int mid, int right){
    int a_idx = left; // a를 가리키는 index : left ~ mid
    int b_idx = mid + 1// b를 가리키는 index : mid + 1 ~ right 
    int s_idx = mid; // sort에 넣는 index    
 
    while(a_idx <= mid && b_idx <= right){
        if(arr[a_idx] <= arr[b_idx]){
            sortArr[s_idx++= arr[a_idx++]; // A의 원소가 더 작을 때
        }else{
            sortArr[s_idx++= arr[b_idx++]; // B의 원소가 더 작을 
        }
    }
}
cs

merge에서는 위에서 얘기했듯이 A 부분집합과 B부분집합을 비교해서 sortArr에 넣어준다. 이때 sortArr을 새롭게 넣어주어야 한다는 점에서 MergeSort는 정렬을 하고자 하는 배열의 크기만큼이 추가로 필요하다. 위의 코드에서는 한 부분집합의 idx가 일정 범위를 넘어가면 다른 집합의 원소를 다 넣지 못하게 된다. 그래서 아래와 같은 코드가 필요하다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int arr[], int left, int mid, int right){
       
...
    
    // A집합을 다 사용했을 때
    if(left > mid){
        for(int idx = b_idx; idx<=right; idx++){
            sortArr[s_idx++= arr[idx++];
        } 
    }
    // B집합을 다 사용했을 때
    else{
        for(int idx = a_idx; idx<=mid; idx++){
            sortArr[s_idx++= arr[idx++];
        }
    }
}
cs

위와 같이 코드를 짜서 부분집합의 원소가 모두 사용되게끔 정렬을 해준다. 마지막으로는 정렬된 배열을 기존 배열로 값을 복사해주어서 정렬해주면 된다.

1
2
3
4
5
6
7
8
void merge(int arr[], int left, int mid, int right){
        
...
    
    //기존 배열로 저장
    for(int idx=left; idx<=right; idx++){
        arr[idx] = sortArr[idx];
    }
}
cs

다음과 같이 코드를 짜면 Merge Sort가 마무리 된다.

 

Merge Sort는 정렬의 대표적인 알고리즘으로 공부를 해두는 것이 좋다. 안되면 외우자.