분할 정복 (Divide and Conquer)

분할 정복

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법
• 대표적인 예: Quick Sort, Merge Sort
• 재귀함수를 사용해 구현

 

분할 정복의 단점

• 재귀함수를 사용하기 때문에 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게된다.

 

Merge Sort

정렬해야 할 리스트가 주어지면 해당 리스트를 최대한 작게 쪼갠 후, 인접한 원소들끼리 비교하며 정렬해 합치는 방법이다. 위 gif는 merge sort 과정에서 업데이트 되는 정렬 리스트를 보여주는 것이기 때문에 정렬 과정을 이해하기엔 어려우니 아래 그림을 통해 이해해보자. 이해가 쉽도록 리스트 원소의 개수를 8개로 하였다. 

더이상 쪼갤 수 없을 때까지 쪼갠 후, 합치면서 정렬하는 것을 확인할 수 있다. 항상 2개로 나눠야하는 것은 아니지만, 보통 2개로 나누어 사용한다. 이러한 방식을 two-way 방식이라고 한다.

 

여기서 노란색으로 칠해진 리스트들은 모두 정렬된 상태인 것을 알 수 있다. 즉, 병합할 때 정렬된 상태로 합쳐야된다는 것이다. 이때 다른 정렬 방법을 사용하는 것이 아니라, 하나의 빈 리스트를 가지고 정렬 순서대로 넣어준 뒤 마지막에 원본 배열에 복사하면 된다. 

 

코드

public class Main {

    static int[] list;
    static int[] sorted;

    public static void main(String[] args) {
        list = new int[]{46, 43, 21, 19, 30, 43, 20, 17, 35, 6};
        sorted = new int[list.length];

        mergeSort(0, list.length - 1);
        
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println();
    }

    private static void mergeSort(int left, int right) {
        if (left == right) {
            return;
        }

        int mid = (left + right) / 2;

        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        merge(left, mid, right);
    }

    private static void merge(int left, int mid, int right) {
        int l = left;
        int r = mid + 1;
        int idx = left;

        while (l <= mid && r <= right) {
            if (list[l] < list[r]) {
                sorted[idx++] = list[l++];
            } else {
                sorted[idx++] = list[r++];
            }
        }

        while (l <= mid) {
            sorted[idx++] = list[l++];
        }
        while (r <= right) {
            sorted[idx++] = list[r++];
        }

        for (int i = left; i <= right; i++) {
            list[i] = sorted[i];
        }
    }
}