[정렬] 합병정렬

합병정렬(merge sort)부터는 기본 정렬(버블, 선택, 삽입)보다 약간 복잡해진다.

하지만 성능은 훨씬 좋아진다.

 

정렬 알고리즘에서 빼놓을 수 없는 합병정렬에 대해 한 번 공부해보자.

 

 

폰 노이만

폰 노이만

 

합병정렬은 폰노이만이 1945년에 개발한 정렬 알고리즘이다.

기초적인 정렬 알고리즘들(선택, 버블, 삽입)은 아무리 효율성을 고려한다고 해도

결국 배열을 싹 훑어내면서 정렬을 해야하는,

태생적인 O(N^2)의 시간복잡도를 가졌었다.

 

하지만 폰 노이만의 합병정렬은 알고리즘에 분할과 정복을 도입하여 정렬의 시간 복잡도를 크게 낮추었다.

 

발상 자체가 굉장히 천재적이다.

합병정렬의 분할과 정복(합병) 최대한 추상적으로 설명해보자면...

 

분할

• 먼저 정렬할 배열을 반으로 분할한다.
• 받은 배열을 또 절반으로 나눈다.
• 절반으로 나눈 배열을 또 절반으로 나눈다.
• 언제까지? 배열 내 엘리먼트가 없거나 한개 일때 까지

 

정복(합병)

• 배열의 엘리먼트가 0, 또는 한개만 남은 배열들을 다시 합친다.
• 이때, 정렬을 해가면서 합친다.
• 정렬을 할 때, 효율적으로 정렬을 하도록 알고리즘을 고려하기에 정렬이 빠르다.
• 합친 정렬을 다시 정렬해가면서 또 합친다. 최종적으로 모든 배열을 정렬된다.

 

위 둘을 재귀(Recursive)적으로 실행한다.

 

아래는 합병 정렬의 단계를 보여주는 그림이다.

위의 설명을 보고 아래 그림(gif)을 본다면 약간의 이해가 가능할 것이다.

출처 - 위키백과

 

---

 

합병정렬 준비물 (재귀, helper function)

합병정렬을 구현하기 위해서는

재귀가 필요하고, helper function이 필요하다.

 

일단 2개의 배열을 정렬하면서 하나의 배열로 합쳐주는

helper function을 구상해보자.

 

helper function은 2개의 배열을 정렬된 하나의 배열로 만들기 위해..

1. 배열 2개를 인수로 받을 것이다.
2. 마지막에는 배열 1개를 리턴할 것이다.
3. 배열 2개의 엘리먼트를 비교하면서 값을 정렬해나갈 것이다.
4. 이 때, 정렬 과정에서 효율적으로 알고리즘을 구상할 것이다.
5. + 인수로 받는 2개의 배열도 정렬이 된 상태여야만 한다!!!

 

아래는 합병정렬의 helper function에 대한 알고리즘 및 해설이다.

 

 

합병정렬 helper function

function merge(arr1, arr2) {
  let results = []
  let i = 0        // * 첫번째 인수로 받은 배열을 순회할 인덱스 
  let j = 0        // * 두번째 인수로 받은 배열을 순회할 인덱스
  while (i < arr1.length && j < arr2.length) {  // (1) 설명은 아래쪽에서 한다.
    if (arr1[i] < arr2[j]) {
      results.push(arr1[i])
      i++
    } else {
      results.push(arr2[j])
      j++
    }
  }
  while (i < arr1.length) {                     // (2) 설명은 아래쪽에서 한다.
    results.push(arr1[i])
    i++
  }
  while (j < arr2.length) {                     // (3) 설명은 아래쪽에서 한다.
    results.push(arr2[j])
    j++
  }
  return results                                // (4) 최종적인 값을 리턴한다.
}

/*
(1) 첫번째 반복문(while)이다.
    일단, arr1과 arr2가 같은 length를 가진 배열이라고 확신할 수 없다.
    따라서 각 배열을 순회하는 인덱스(i, j)가 각자의 배열의 길이보다 작을때까지
    첫번째 반복문은 유효하다.
    
    이때, arr1[i]와 arr2[j]를 비교하면서
    arr1의 엘리먼트가 크다면 그 값을 results에 push해주고 i 인덱스를 1 올린다.
    반대의 경우라면 arr2의 엘리먼트를 results에 push해주고 j 인덱스를 1 올린다.

(2) 이제부터는 첫번째 반복문이 깨진 상황이다.
    배열의 길이보다 i가 작다는 전제 하에 (즉, j는 이미 arr2의 순회를 마친 상태)
    arr1의 모든 엘리먼트를 results에 push해준다.
    
(3) 첫번째 반복문이 깨진 상황 중, arr2의 엘리먼트가 남아있는 상황이다.
    (2)의 상황과 마찬가지로 arr2의 모든 엘리먼트를 results에 push해준다.
    
(2)와 (3)이 가능한 이유는 인수로 두 배열을 받을 때 배열이 이미 정렬된 상태였기 때문이다.
   만약, arr1의 순회를 끝마쳤는데 arr2의 엘리먼트가 남아있다면
   arr2의 남아있는 엘리먼트는 이미 arr1보다 크다는 의미이며, 또한 정렬이 되어있다.
   따라서 모든 엘리먼트를 results에 그대로 push 해줘도 문제가 없다.
*/

 

이렇게 보기만 해서는 직관적인 이해가 되기 어렵기에

아래처럼 한번 손으로 풀어보는 것을 추천한다.

 

손고리즘이 짱이다.

 

그럼 합병에 필요한 helper function의 이해가 되었다는 가정하에

합병 정렬의 재귀함수 부분으로 들어가면 된다.

 

일단, 합병 정렬의 Pseudocode(의사코드) 이다.

1. 정렬할 하나의 배열을 인수로 받는다.
2. 합병 정렬은 재귀적으로 구현해야 한다. 재귀함수를 활용하는 필요조건은 아래와 같다.
   - 재귀함수를 작성할때는 input값이 계속 바뀌어야 하고,
   - 탈출할 구간이 있어야 한다.
3. 이 때, 배열을 계속 반으로 쪼개는 것으로 input값을 바꿔 재귀시키고, (input 변화)
   배열내 엘리먼트가 1개 또는 0개일 때 배열을 반환한다. (재귀 탈출구간)
4. 왼쪽과 오른쪽 배열에 각각 mergeSort를 재귀시키면 된다.

 

그렇다면... 합병정렬을 구현해보자

 

합병정렬

function mergeSort(arr) {
    if(arr.length <= 1) return arr          // (1) 재귀함수의 탈출 구간이다.
    let mid = Math.floor(arr.length/2)      // (2) 배열을 반으로 쪼갤 중간인덱스이다.
    let left = mergeSort(arr.slice(0, mid)) // (3) slice로 배열의 절반을 재귀시킨다.
    let right = mergeSort(arr.slice(mid))   // (4) slice로 배열의 절반을 재귀시킨다.
    return merge(left, right)        // (5) 쪼갠 배열을 정렬해주는 helper function이다.
}


/* 
(1) 재귀함수에 탈출구간을 주지 않는다면 평생 끝나지 않는다.
    합병정렬은 배열의 엘리먼트가 없거나 1개일때까지 배열을 쪼개므로
    위와 같은 조건이 들어가게 된다.
(2) 배열을 반으로 쪼갤 중간 인덱스이다.
(3) 배열을 반으로 쪼갠 값(slice(0, mid)을 재귀시킨다.
    slice는 첫번째 인수부터 두번째 인수 - 1까지 엘리먼트를 잘라간다.
(4) 배열을 반으로 쪼갠 값(slice(mid)을 재귀시킨다.
    인수가 하나라면 그 인수부터 쭉 엘리먼트를 slice한다.
(5) 쪼갠 배열을 정렬해주는 기능을 한다.
    여기에서는 재귀가 끝났을 경우, (즉, 배열의 길이가 0과 1로 이루어진 시점부터)
    하나씩 배열을 주워서 정렬해 올라갈 것이다.
*/

 

직관적인 이해가 가지 않는다면 그려보자.

 

재귀함수가 return된 뒤, helper 함수가 주워간다고 생각하면 조금 편해진다.

 

배열이 계속 쪼개져서 재귀되는데

이 때 배열 내 엘리먼트가 0이나 1이 된다면

[] 이나 [n]이 return될 것이고,

 

그때부터 merge함수가 하나씩 발동되면서

점차적으로 정렬이 될 것이다.

 

---

 

시간복잡도

합병정렬의 시간복잡도는 O(n logN) 이다.

n logN은 어떻게 나오는 것일까?

 

이진탐색의 시간복잡도가 O(logN)인 이유는

배열을 반씩 쪼개기 때문에 그렇다.

반약에 반씩 쪼개서 탐색을 하게 된다면 N이 1024이라는 가정하에

1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 순으로 탐색을 한다.

log2 1024는 10이기 때문에 시간 복잡도가 logN이다.

 

합병정렬에서도 이는 유효하다.

배열을 반씩 쪼개는 과정에서 logN의 시간복잡도가 들게된다.

이때, 배열을 정렬하면서 합병하는 과정에서 모든 배열을 하나씩 참조하는 N개의 연산이 필요하기 때문에

 

최종적으로 합병정렬의 시간복잡도는 O(N logN)이 된다.