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

이번 시간에는 합병정렬에 대해 공부해보겠습니다. 합병정렬은 앞서 설명한 퀵정렬화 함께 무척 빠른 정렬속도(O(nlogn))을 자랑하기 때문에, 반드시 알고 있어야 합니다 !

 

합병정렬은 분할정복 기법을 사용하여 문제를 해결하는 방법입니다.  

분할정복은 해결할 수 없는 큰 문제를 해결할 수 있는 작은 단위의 문제로 나누고(분할) 해결한 후, 다시 합치는 합치는(정복)하는 과정입니다. 이 과정을 계속 반복하면서 정렬해 나가는 방법이 합병정렬 입니다.

일단 글보다는 실제로 정렬을 하면서 설명을 해보겠습니다 !!

여기서 l은 왼쪽부분, r은 오른쪽 부분입니다.

 

[3 8 12 6 22 15 30 1]

l                r

[ 3 8 12 6 ]  [ 22 15 30 1 ] 

              l            r              l          r                    

[ 3 8 ]   [ 12 6 ]   [ 22 15 ]   [ 30 1 ] 

                       l         r       l          r        l         r         l         r                           

[ 3 ]  [ 8 ]  [ 12 ]  [ 6 ]  [ 22 ]  [ 15 ]  [ 30 ]  [ 1 ]     

 l            r              l          r    

[ 3 8 ]  [ 6 12 ]  [  15 22 ]  [ 1 30 ]

l                r

[ 3 6 8 12 ]  [ 1 15 22 30]

 

[1 3 6 8 12 15 22 30]

 

네 뭐 어떻게 하다가 정렬이 되었습니다.  일단 보시면, 처음 배열을 계속 반으로 나눕니다.

근데 언제까지 나눌까요? 그 전에 왜 계속 큰 배열을 잘게 쪼개는지 먼저 생각을 해보셔야 합니다. 

 

저희의 목표는 [3 8 12 6 22 15 30 1]를 정렬하는 것입니다. 그것 뿐입니다. 하지만 한번에 정렬을 못합니다. 그렇기 때문에 정렬할 수 있는 작은 단위까지 계속 나누어 줘야합니다(분할). 계속 나누다 보면, 배열의 길이가 1인 친구가 등장합니다.

 

이 경우에는 숫자가 1개 밖에 없으니 정렬되었다고 생각해도 되겠죠? 아, 그러면 해결할 수 있는(정렬할 수 있는)단위까지 왔으니 다시 합쳐줍니다. 근데 두 배열을 합치면서 중요한 점은, 숫자를 비교해서 더 작은값을 앞에 놓게 합쳐줍니다. 여기서 정렬이 되는군요 !!

 

마지막으로 다시 정렬해보면, 합병정렬은 분할정복기법을 사용하여 정렬을 합니다. 즉, 큰 문제를 해결할 수 있는 작은 단위의 문제로 나누어 큰 문제를 해결하는 방법입니다. 처음 숫자는 한번에 정렬할 수 없습니다. 그렇기 때문에 해결할 수 있을 때까지(정렬할 수있을 때까지) 계속 쪼개어 줍니다.

 그러다 숫자 1개가 되면(정렬되었다고 생각해도 되겠죠 ?) 다시 합쳐줍니다. 여기서 합칠 때, 숫자의 크기를 비교하여 합칩니다.

 

public class Main {
    public static void main(String[] args) {

        int[] arr = { 7, 3, 5, 9, 12, 8, 4, 0, 2, 22 };

        mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        } else {

            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merging(arr, start, mid, mid + 1, end);
        }
    }

    static void merging(int[] arr, int s1, int e1, int s2, int e2) {
        int p = s1;
        int q = s2;
        int[] result = new int[100];
        int index = 0;

        while (p <= e1 && q <= e2) {
            if (arr[p] > arr[q]) {
                result[index++] = arr[q];
                q++;
            } else {
                result[index++] = arr[p];
                p++;
            }
        }

        if (q > e2) {
            for (int i = p; i <= e1; i++) {
                result[index++] = arr[i];
            }
        } else if (p > e1) {
            for (int i = q; i <= e2; i++) {
                result[index++] = arr[i];
            }
        }
        for (int i = s1; i <= e2; i++) {
            arr[i] = result[i - s1];
        }
    }
}

여기서 함수는 총 2개가 나옵니다.

mergeSort(arr[], start, end) : 배열 arr의 start에서부터 end까지 반으로 나누는 역할하고 merging함수를 호출합니다. 재귀함수입니다.

merging(arr[], s1, e1, s2, e2) : 왼쪽부분과 오른쪽 부분을 합치는 역할을 합니다, 1,e2은 왼쪽부분의 범위, s2,e2는 오른쪽 부분의 범위

 

먼저 mergeSort함수의 기저조건은 start>=end입니다. 이 말은 arr배열의 start~end사이에 숫자가 하나만 있다는 말을 의미합니다.

그렇지 않으면 이제 계속 나누어야 겠죠 ?

 

mergeSort내부에서 2개의 mergeSort함수가 있는데, 첫번째는 왼쪽부분을 나누고 두번째는 오른쪽 부분을 나눕니다.

먼저 왼쪽을 start와 end사이에 숫자가 하나만 있을 때까지 계속 나눕니다. 재귀적으로요.

 그러다 왼쪽부분을 모두 나누면, 이제 두번째 mergeSort를 실행합니다. 오른쪽 부분을 계속 나누다가 오른쪽 부분도 start와 end사이에 숫자가 하나만 있게 되면 탈출하게 됩니다. 그러면 이제, merging()함수를 실행해야겠죠 ?

  ※여기서 mergeSort함수는 재귀적으로 동작합니다. 각각의 영역에서 start와 end를 계속 저장하고 있기 때문에 계속 나누는 범위는 바뀌게 됩니다.

 

merging함수에서는 왼쪽부분 오른쪽 부분을 합치는 일을 합니다. 근데 어디서부터 어디까지를 합치는 것일까요 ? 이 부분은 merging함수의 인자로 넘어온 값에서 알 수 있습니다.

    s1 : 왼쪽부분 시작

   e1 : 왼쪽부분 마지막

   s2 : 오른쪽부분 시작

   e2 : 오른쪽부분 마지막

 

쉽게 생각해서 s1~e2, s2~e2사이에 있는 값들 중에서 더 작은 값을 앞에 넣겠다는 의미입니다. 정렬을 해야 하기 때문이죠. 그러다가 왼쪽/오른쪽 둘 중 한부분이 먼저 다 들어가게 되면 나머지 부분을 모두 채워주면 됩니다. 

 만약 왼쪽[2 4 6], 오른쪽[5 7 9]를 합병한다고 하면, [2 4 5 6]로 채우면 왼쪽부분은 더이상 채울 값이 없습니다. 그럴땐 오른쪽을 모두 넣어버리면 되겠죠 ?

 

이제 위의 과정을 계~속 반복합니다. 언제까지요 ? 스택에 쌓여있는 mergeSort함수가 모두 제거될 때 까지요 !