[정렬] 합병 정렬 : 늦깎이 IT

[합병정렬]

합병정렬은 분할정복이라는 알고리즘에 근거하여 만들어진 정렬 방법이다.

분할정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 단순한 문제로 '분할(Divide)'하여 '정복(Conquer)'하는 방법이다.

1. 분할 (Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다.

2. 정복 (Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다.

3. 결합 (Combine) : 분할해서 해결한 결과를 결합하여 큰 문제를 해결한다.

우리가 8개의 데이터를 정렬한다고 가정해보자.

8개의 데이터를 정렬하는 것 보다는 4개의 데이터를 정렬하는 것이 더 쉽고, 또 4개보다는 2개의 데이터를, 2개보다는 1개의 데이터를 정렬하는 것이 더 쉽다는 것이다.

위의 아이디어를 근간으로, 합병정렬은 데이터가 1개가 남을 때까지 분할을 한다. 데이터가 1개가 남았을 경우는 그 자체로 정렬이 되어있다고 할 수 있기 때문이다.

[이미지 출처]

[의사 코드]

Merge-sort(A[], P, R)
    if(P < R) then {
        Q ← (P + R) / 2
        Merge-sort(A[], P, Q)
        Merge-sort(A[], Q+1, R)
        Merging(A[], P, Q, R)
    }
 
Merging(A[],P,Q,R)
    merge A[P....Q] and A[Q+1....R]
 
 

1)번 라인의 Merge-sort() 함수는 배열 A[P...R]를 분할하는 함수이다.

3)번 라인의 Q는 시작점 P와 끝점 Q의 중간지점이다.

4), 5)번 라인에서 Merge-sort()함수를 재귀적으로 호출하며, 원래 배열 A[P...R]를 A[P...Q]와 A[Q+1...R] 배열로 분할한다.

9)번 라인의 Merging() 함수는 4), 5)번 라인에서 Merge-sort() 함수를 호출함으로써 정렬된 두 개의 배열을 하나의 배열로 합치는 역할을 한다.

합병정렬의 시간 복잡도는 T(N) = NlogN 만큼의 시간이 소요된다.

1) N개의 데이터를 정렬하기 위해서는 N개의 데이터를 절반으로 각각 나누어야 한다.

이것은 T(N) = T(N/2) + T(N/2)으로 나타낼 수 있다.

2) 절반으로 나뉜 각각의 데이터에 대해서 정렬을 수행하는 데 걸리는 시간은 N이다. N개의 데이터를 정렬하기 위해서는 이미 정렬된 두 개의 N/2의 배열을 비교하며 정렬을 수행해야 하는데, 비교연산을 한 번 할때마다 하나의 데이터가 정렬되므로, N개의 데이터를 정렬하기 위해서는 N번의 비교연산이 필요하다.

3) N개의 데이터를 1개의 데이터로 쪼개기 위한 분할 횟수는 logN이다.

4) 그리고 각각의 분할에 대해서 N번의 비교연산을 진행하기 때문에 최종적으로 시간복잡도는 NlogN이 된다.

[JAVA 코드]

public static void mergeSort(int[] arr, int left, int right) {
 
        if (left < right) {
 
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merging(arr, left, mid, right);
        }
    }
 
 
 
public static void merging(int[] arr, int left, int mid, int right) {
 
        int fIdx = left;
        int rIdx = mid + 1;
        int idx = left;
 
        int[] temp = new int[right + 1];
 
        while (fIdx <= mid && rIdx <= right) {
 
            if (arr[fIdx] <= arr[rIdx])
                temp[idx++] = arr[fIdx++];
            else
                temp[idx++] = arr[rIdx++];
        }
 
        if (fIdx > mid)
            for (int i = rIdx; i <= right; i++)
                temp[idx++] = arr[i];
 
        if (rIdx > right)
            for (int i = fIdx; i <= mid; i++)
                temp[idx++] = arr[i];
 
        for (int i = left; i <= right; i++)
            arr[i] = temp[i];
 
    }