[JAVA] 합병정렬(merge sort)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

 merge sort는 분할 정복법(divide and conquer)이라는 방법을 사용하는 알고리즘입니다. 분할 정복법이란 예전에 로마 제국이 주변 나라들을 정복할 때, 통째로 정복하기보다는 분할을 해서 각각을 정했다는 것에서 착안한 이름이라고 합니다.

즉,

1) 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할해서 

2) 각각의 작은 문제를 순환적으로 해결하고

3) 작은 문제의 해를 합하여(merge) 원래 문제의 해를 구하는 방법입니다.

 

여기서 핵임은 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다는 것인데,

이를 통해 합병정렬이 기본적으로 재귀(recursive)의 아이디어를 사용한다는 걸 알 수 있습니다.

---

이 그림을 봐도 알 수 있듯이,

주어진 ALGORITHMS라는 단어가 있으면, 이 단어들을 나눈 다음, 이 과정을 recursive로 호출한 다음 다시 분류를 통해 마지막에 그 결과들을 merge 한다는 걸 알 수 있습니다.

 

때문에 합병 정렬에서 실제로 정렬이 일어나는 과정은 바로 divide되어 sort 된 결과들을 merge 하는 과정이라고 할 수 있습니다.

위의 그림들을 보게되면, ALGORITHMS라는 단어를 둘로 나눈 뒤 나눠진 두 단어의 알파벳을 크기순으로 정렬했습니다. 그다음 정렬된 두 개의 단어들을 다시 합치는 과정이 이어집니다.

 

두 개로 나뉜 단어에 각각 i와 j라는 인덱스를, 그리고 ALGORITHMS 라는 단어를 새롭게 배열할 추가 배열에는 k의 인덱스 값을 설정해줍니다.

 

우선 나눠진 두 단어에서 가장 앞에 위치한 두 단어를 비교해줍니다. 나눠진 두 부분에서 가장 앞에 위치한 단

어 중 한 단어가 전체 단어에서도 가장 앞에 위치할 것이기 때문입니다. 그 다음에는 왼쪽 단어에서 두 번째로 작은 단어와 오른쪽 단어에서 가장 작은 단어를 비교해서 둘 중 더 작은 단어를 추가 배열에 위치시킵니다. 이러한 방식으로 나눠진 두 단어의 인덱스를 이용하여 둘 중 더 작은 단어는 추가 배열에 위치시키고 그 단어가 속했던 쪽의 인덱스를 1 높여주고 다음 비교를 진행하는 방식으로 나눠진 단어를 하나의 단어로 다시 merge 해줍니다.

 

public class MergeSort {
    static char[] word = { 'A', 'L', 'G', 'O', 'R', 'I', 'T', 'H', 'M', 'S'};

    static void mergeSort(char[] A, int p, int r){
        if(p < r){
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    static void merge(char[] data, int p, int q, int r) {
        int i = p, j = q + 1, k = p;
        char[] tmp = new char[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 m = p; m <= r; m++)
            data[m] = tmp[m];
    }

    public static void main(String[] args){
        mergeSort(word, 0, 9);
        for(int i=0; i<word.length; i++)
            System.out.print(word[i]);
    }
}

---

시간복잡도