알고리즘

합병정렬 알고리즘 :: 마이구미

mygumi 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


반응형