병합정렬(Merge sort)

■ 잡담

병합정렬에 대해서는 고등학교 1학년인 작년에 이미 배워서 직접 짜본적도 있었습니다. 하지만, 정렬 알고리즘을 사용하지 않다보니 배웠던것도 까먹게 되더군요.. 그래서 이번에는 병합정렬 알고리즘에 대해 알아보도록 하겠습니다.

■ 병합정렬

병합정렬은 이름만 듣게되면 무언가 합치는 정렬이라고는 짐작이 될것 같습니다. 일부분은 맞는 말 입니다.

병합정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이며 분할정복 기법중 하나입니다.

1. 분할

정렬되지 않은 데이터를 위의 그림과 같이 최소한의 크기로분할합니다.

2.합병

분할한 데이터를 2 그룹씩 짝을지어 합병하고 정렬을 수행합니다. 이 과정을 반복하게 되면 최종적으로 데이터 정렬을 모두 마치게 됩니다.

3.정렬

분할된 데이터를 정렬하며 합병을 할때 정렬되는 과정은 아래 그림과 같습니다.

위의 그림은 분할된 데이터를 정렬하는 일부 과정입니다. 병합하고자 하는 데이터들의 길이만큼의 새로운 공간을 만들고 정렬을 진행합니다.

병합하고자 하는 두 그룹의 데이터는 이미 이전 단계에서 정렬이 된 데이터이기 때문에 무조건 앞부분에는 작은 데이터가 존재하게 됩니다. 따라서 두 그룹의 앞쪽 데이터들을 순서대로 비교하여 더 작은것을 집어넣게 됩니다.

위의 병합정렬을 코드로 만들게 되면 아래와 같습니다.

public static int array[] = { 5, 1, 3, 8, 0, 4};
 
    public static void main(String args[]) {
        merge_sort(array, 0, array.length - 1);
        for (int a : array)
            System.out.print(a + " ");
    }
 
    public static void merge_sort(int array[], int left, int right) {
        int mid;
        if (left < right) { //요소의 크기가 1이 아닐때 분할 후 정렬
            mid = (left + right) / 2;
            merge_sort(array, left, mid);
            merge_sort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
 
    public static void merge(int array[], int left, int mid, int right) {
        int leftOffset, rightOffset, offset;
 
        leftOffset = left;
        rightOffset = mid + 1;
        offset = left;
 
        int sortArray[] = new int[array.length];
 
        //왼쪽 그룹과 오른쪽 그룹의 인덱스별로 크기 비교
        while (leftOffset <= mid && rightOffset <= right) {
            if (array[leftOffset] < array[rightOffset]) {
                sortArray[offset] = array[leftOffset];
                leftOffset++;
            } else {
                sortArray[offset] = array[rightOffset];
                rightOffset++;
            }
            offset++;
        }
        
        //양 쪽 그룹일 모두 비교하고 남는 데이터가 있는지 확인
        if (leftOffset <= mid) { //왼쪽 그룹의 데이터가 남을시
            for (int m = leftOffset; m <= mid; m++) {
                sortArray[offset] = array[m];
                offset++;
            }
        } else { //오른쪽 그룹의 데이터가 남을시
            for (int m = rightOffset; m <= right; m++) {
                sortArray[offset] = array[m];
                offset++;
            }
        }
        
        //정렬한 배열을 기존 배열에 저장
        for (int m = left; m <= right; m++) {
            array[m] = sortArray[m];
        }
    }

■ 분할정복 기법

위에서 언급한 분할정복 기법은 문제를 더 이상 나눌 수 없을 때까지 나눈 뒤에 나누어진 문제들을 각각 풀어냄으로써 전체의 답을 얻는 알고리즘을 말합니다.

분할정복의 과정은 분할, 정복, 결합 세 가지가 있습니다.

1. 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.

2. 정복(Conquer) : 하위 문제를 해결한다. 단, 하위 문제가 여전히 분할 가능한 상태라면 문제를 해결하지 않고 하위 집합에 대해 1번 과정을 수행한다.

3. 결합(Combine) : 2번 과정에서 정복된 답을 취한다.

병합정렬의 과정과 매우 비슷한것을 느낄 수 있습니다. 문제 해결 기법에는 분할정복 뿐만 아니라 욕심쟁이 기법, 동적 계획법등 다양한 기법들이 있습니다. 이에 대해서는 다른 포스팅에서 자세하게 다루도록 하겠습니다.

■ 느낀점

앞으로 근 한달정도는 면접에서 질문받았던 이론적인 부분들, 또는 자료구조, 컴퓨터 구조 등의 기초적인 부분들을 공부하며 포스팅할 계획입니다. 면접을 처음 보고나니 기초가 필요하다는것이 많이 느껴졌습니다. 사실상 프로젝트만 하다보면 기초적이고 원리적인 부분들을 놓치거나 까먹는 경우가 많아서..