[알고리즘] Sort - 합병정렬(Merge sort)

Sort - 합병정렬(Merge sort)​ 

앞서 비교적 간단하지만 효율적이지 않은 정렬 방법을 살펴보았다

그 다음으로 합병 정렬과 퀵, 힙 정렬에 대해 알아보자

그 중에 합병과 퀵 정렬은 분할정복법이라는 

동일한 정렬을 사용하는 알고리즘이다

분할정복법이라는것은

예를들어, 한 나라가 다른 나라를 정복할때 한꺼번에 침략하지않고

조금씩 영토를 쪼개어 각각을 하나씩 정복 하는것과 비슷한 것이다.

영어로는 divide and conquer라고 한다.

좀 더 간단하게 말하자면 주어진 문제를 3단계에 걸쳐서 해결하는것이다

그 순서는 다음과 같다.

1단계(분할)

해결하고자 하는 문제를 작은 크기의 동일한 문제로 분할한다.

2단계(정복)

각각의 작은 문제를 해결한다

3단계(합병)

작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

분할의 예로써, 입력으로 n개의 데이터가 주어지고 최대값을 찾을때

배열을 반으로 나누어서 앞쪽과 뒤쪽에서 최대값을 찾고 그 둘중에 최대값을 찾아

비교하는 절차를 거쳤다.

전체 문제를 해결하는 방법을 각각의 분할된 영역에 그대로 적용할 수 있으므로

별도의 알고리즘이 필요없다.

이것이 분할정복의 가장 간단한 예이다.

우리는 이와 같은 문제를 Recursion으로 해결했었다.

분할정복의 풀이는 본질적으로 Recursion의 풀이 방법이다. 

먼저 적당히 데이터를 자르는 분할을 하고

이렇게 분할된 데이터를 재귀로 정렬한다.

마지막으로 모두 정렬된 데이터를 병합 하며 알고리즘이 끝난다.

주의 해야할 점은,

n개의 데이터가 주어질때 분할하기 위해 특별한 알고리즘이 필요한건 아니다

쪼개진 데이터를 정렬하는것은 재귀를 사용하기때문에 

다시 함수를 호출해주기만 하면된다.

따라서 실제로 코딩을 해주어할것은 merge 부분이다.

분할을 반복하다보면 마지막은 길이가 하나인 리스트들로 나뉘어진다.

실제로 데이터들이 비교되고 자리를 바꾸는 것은 merge과정에서 일어난다.

왜냐하면 길이가 1이되면 그 자체로 정렬된 상태이기 때문이다.

위 그림은 길이가 1인 리스트 8개에서 길이가 2인 리스트 4개로,

마지막은 길이가 4인 리스트를 합쳐서 전체가 정렬된다.

따라서 합병 정렬에서 가장 중요한것은 합병(merge)하는 과정이다.

정렬된 2개의 리스트가 있을때

어떻게 하나의 정렬된 리스트로 합병할 것인지 생각해보면

길이가 n인 추가 배열을 만든 후에 길이가 n/2인 정렬된 2개의 리스트를

추가 배열에 합병하면 된다.

여기서 주의해야할점은

2개의 리스트가 각각 정렬되어있는 상태라는 것이다.

이미 정렬이 되어있기때문에 전체 10개의 값중에서 가장 작은 값은

앞에서 첫번째(오름 차순)거나 뒤쪽에서 첫번째(내림 차순)가 가장 작은 값이된다.

따라서 병합하며 정렬을 하기 위해서는

i 인덱스에 있는 값과, j 인덱스에 있는 값을 하나씩 비교한 후 추가배열 저장하면 된다!

​i와 j의 값을 비교하면서 작은 값을 추가배열에 하나씩 넣어주고 

만약 해당 배열에 값이 추가배열에 저장되었다면

i나 j의 값을 증가시켜 준다.

마지막까지 실행되면 추가배열에 정렬된 상태로 합병된다.

이렇게 해서 두개의 정렬된 배열을 merge해서 하나의 배열로 만들수 있다.

mergeSort(A[],p,r){
    if(p<r) then{
        q <- (p+r)/2;
        mergeSort(A,p,q);
        mergeSort(A,q+1,r);
        merge(A, p, q, r);
    }
}
 
merge(A[], p, q, r){
    정렬되어 있는 ㅜ 배열 A[p..q]와 A[q+1...r]을 합하여                                                             
    정렬된 하나의 배열 A[p...r]을 만든다.
}
 

merge sort는 기본적으로 재귀 함수이므로

매개변수를 명시적으로 생성한다.

위의 함수는 배열 A[] 인덱스 p에서 r까지를 정렬하는 알고리즘이다

따라서 모든 데이터를 정렬하기 위해서는 mergeSort(A[],1,n)으로 호출 하면 된다.

첫번째 base case는 p>=r인데, 이 때는 데이터의 개수가 1개거나 0개이므로

정렬알고리즘이 아무 것도 할 필요가 없다.

따라서 p<r일때만 알고리즘이 동작한다.

merge sort 알고리즘은 기본적으로 분할정복이므로

중간 위치인덱스를 q로 잡고 p와 r의 2분의 1 지점을 구한다.

이후에 앞쪽과 뒤쪽을 정렬하고 합치는데

합치는 과정은 merge라는 함수가 담당하게 된다.

void merge(int data[], int p, int q, int r){                                                               
    int i=p, j=q+1, k=p;
    int tmp[data.length()];
    while(i<=q && j<=r){
        if(data[i]<=data[j])
            tmp[k++] = data[i++];
        else
            tmp[k++] = data[j++];
    }
    while (i<=q)
        tmp[k++] = data[i++];
    while (j<=r)
        tmp[k++] = data[j++];
    for(int i = p; i <= r; i++){
        data[i] = tmp[i];
    }
}
 

좀더 구체적으로 merge 함수의 코드를 작성해보도록하자

시작인덱스가 p, 중간이 q, 마지막이 r일 때

p~q, q+1~r까지는 이미 정렬되어있다는 가정을 할 때

이 전체를 합쳐서 하나의 배열로 만들어 주는것이다.

추가 배열이 필요하기 때문에 tmp라는 배열을 만들어준다.

또한 i, j, k도 설정해주는데 위쪽 그림 예시에서 봤던 위치에 생성된다.

첫번째 while문은 데이터 i와 데이터 j를 비교해서 작은 값이 k로 내려오고

i나 j, 그리고 k를 증가시키는 연산이다.

이 연산은 한쪽의 배열 데이터가 없어질때까지 반복된다.

즉, i가 q보다 작거나 같고, j가 k보다 작거나 같아질때까지 반복된다는 것이다.

그리고 첫번째 while문을 나온 후

앞쪽의 배열에 데이터가 남아있는 경우와

뒤쪽의 배열에 데이터가 남아있는 경우를 각각 처리해준다.

마지막으로 추가 배열에 임시로 저장되어있는 값을

data 배열안에 넣어주면서 함수는 끝이난다.

다음으로 merge sort의 시간복잡도를 알아보자

기본적으로 재귀의 형태를 가지고 있으므로

반복문을 체크하며 시간복잡도를 계산하기 어렵다

그러나, 분할정복법의 시간복잡도 계산은 반복문으로 처리한 계산보다 훨씬 쉽다.

데이터가 n개일때 merge sort로 계산하는 시간을 T(n)이라고 할 때

정렬을 위해서 반으로 쪼개서 n/2개의 배열에 재귀함수를 호출한다.

반으로 쪼개진 배열 2개에 대한 정렬을 수행해야하므로

반으로 쪼개진 한 배열당 T([n/2])의 시간이 걸리므로 2개의 배열은

T([n/2])+T([n/2])의 시간이 걸린다.

두개의 정렬된 배열을 merge할 때 두 배열을 한번씩 비교하므로 

merge의 시간은 n이다.

따라서, merge sort의 시간복잡도는

T(n) = T([n/2])+T([n/2]) + n

이 된다.

이 순환식을 수학적으로 풀어보면

O(nlogn)이 되는데 증명은 위의 그림으로 대체한다

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘