합병정렬(merge sort)

이 글은 합병정렬(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 = { 230, 10, 60, 550, 40, 220, 20 };       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++];     } } Colored by Color Scripter

cs

출처: https://mygumi.tistory.com/309?category=677288 [마이구미의 HelloWorld]