• 합병정렬 알고리즘 :: 마이구미
    알고리즘 2018. 4. 14. 16:28

    이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다.

    누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.

    빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다.

    이유는 분할 정복 방식을 따르기 때문이다.

    퀵 정렬 - http://mygumi.tistory.com/308


    1. 합병정렬이란 무엇인가?

    2. 합병정렬은 어떻게 구현하는가?

    3. 합병정렬의 유용한 예는 언제인가?


    합병정렬은 분할 정복 방법을 통해 구현된다.

    분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다.

    (* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.)


    시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다.

    또한 안정 정렬로 속한다. (안정 정렬의 의미를 모른다면 참고글)


    재귀 방식으로 구현될 수 있어, 코드가 복잡하지 않다.

    전체적인 흐름만 이해한다면, 쉽게 이해할 수 있다.


    요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식이다.

    쪼개는 방식은 퀵정렬과 같은 방식으로, 왼쪽 오른쪽을 분리시킨다.


    우선 전체적인 흐름을 볼 수 있는 코드를  통해 퀵정렬과 합병정렬을 비교해본다.


    public void mergeSort(int[] array, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(array, left, mid); mergeSort(array, mid + 1, right); merge(array, left, mid, right); } }


    public void quicksort(int[] array, int left, int right) { if (left >= right) { return; } int pi = partition(); quicksort(array, left, pi - 1); quicksort(array, pi + 1, right); }


    정렬 로직에 있어, 퀵정렬은 partition(), 합병정렬은 merge() 메소드가 된다.


    정렬의 경우 우선 피벗을 통해 정렬을 우선적으로한 후(partition), 영역을 쪼갠다.(quicksort)

    반대로 합병정렬은 영역을 쪼갤 수 있을 만큼 쪼갠 후(mergesort), 정렬한다.(merge)


    합병정렬의 전체적인 흐름을 표현하면 다음과 같다.


    합병정렬


    빨간 선은 쪼개는 것을 나타내고, 초록 선은 합치는 것을 나타낸다.

    보다시피 더이상 쪼갤 수 없다면, 합치게 된다.


    public static void merge(int[] array, int left, int mid, int right) { int[] L = Arrays.copyOfRange(array, left, mid + 1); int[] R = Arrays.copyOfRange(array, mid + 1, right + 1); int i = 0, j = 0, k = left; int ll = L.length, rl = R.length; while (i < ll && j < rl) { if (L[i] <= R[j]) { array[k] = L[i++]; } else { array[k] = R[j++]; } k++; } // remain while (i < ll) { array[k++] = L[i++]; } while (j < rl) { array[k++] = R[j++]; } }


    merge() 메소드에서 단순히 두 영역 배열로 만들어서 순차적으로 비교하면서 정렬하는 것을 볼 수 있다.

    이것이 가능한 이유는 합병의 대상이 되는 두 영역은 각 영역에서 대해서는 이미 정렬되어있기 때문이다.

    그래서 단순히 두 배열을 순차적으로 비교하여 정렬할 수 있게 된다.


    합병정렬

    합병정렬의 과정을 설명하면서 순차적이라는 말을 많이 사용했다.

    그 이유는 합병정렬이 사용되는 예를 설명하기 위해서다.

    합병정렬은 링크드리스트(LinkedList) 이 정렬이 필요로 할 때 유용하다.


    극단적인 예로, LinkedList 의 요소를 정렬하기 위해 퀵정렬을 사용한다면 어떻게 될까?

    결과적으로 성능이 좋지 않다.

    왜냐하면 퀵정렬은 순차적 접근이 아닌 임의적으로 접근하기 때문이다.


    자세히 설명하자면 LinkedList 는 삽입 및 삭제 연산에 있어, 유용하지만 접근 연산에 있어서는 유용하지않는다.

    배열의 경우에는 인덱스를 통해 접근하기 때문에 시간복잡도가 O(1) 이지만, LinkedList 는 Head부터 탐색해야하기때문에 O(n) 이다.

    그렇기에, 임의적인 접근에 있어서는 오버헤드가 증가한다.

    이러한 이유로 LinkedList 는 순차적인 접근과 같은 합병정렬을 사용하는 것이 유용하다.


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    private void solve() {
        int[] array = { 23010605504022020 };
     
        mergeSort(array, 0, array.length - 1);
     
        for (int v : array) {
            System.out.println(v);
        }
    }
     
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
     
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
     
    public static void merge(int[] array, int left, int mid, int right) {
        int[] L = Arrays.copyOfRange(array, left, mid + 1);
        int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
     
        int i = 0, j = 0, k = left;
        int ll = L.length, rl = R.length;
     
        while (i < ll && j < rl) {
            if (L[i] <= R[j]) {
                array[k] = L[i++];
            } else {
                array[k] = R[j++];
            }
            k++;
        }
     
        while (i < ll) {
            array[k++= L[i++];
        }
     
        while (j < rl) {
            array[k++= R[j++];
        }
    }
    cs


    댓글 0

Designed by Tistory.