LoginGustBookCategories
Categories
Algorithms

Merge Sort

thumbnailCreatehb21·2022년 01월 15일 20:53

https://images.unsplash.com/photo-1621165755630-367fc1c27da4?ixlib=rb-1.2.1&ixid=MnwxMjA3fDB8MHxzZWFyY2h8OHx8bWVyZ2V8ZW58MHx8MHx8&auto=format&fit=crop&w=800&q=60


앞으로 다루게 될 Merge, Quick, Radix 정렬 알고리즘은 앞서 배웠던 세가지의 알고리즘보다 훨씬 더 빠릅니다. 앞선 알고리즘들은 n제곱의 시간 복잡도를 가지는 반면, 앞으로 다루는 알고리즘은 n log n의 시간 복잡도를 가지게 됩니다.
첫째로, 병합 정렬(Merge Sort)에 대해서 얘기해보겠습니다.


Merge Sort


병합 정렬의 핵심은 크게 보자면 세 가지입니다. 분리하기, 병합하기, 정렬하기.

만약 8개의 요소가 있는 배열을 가지고 작업을 한다면, 이 배열을 쪼개고, 쪼개고, 쪼개서 요소가 하나씩 있는 배열 8개로 쪼갠 다음에 정렬하고 합치고, 정렬하고 다시 합치고를 반복해서 병합된 정렬된 배열을 마지막에 리런받는 방식이라고 생각하면 그나마 이해하기 편합니다.

우선 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 과정은 병합 정렬의 필수 과정입니다. 다음은 이러한 과정을 수행하는 코드입니다.

1. 두 개의 정렬된 배열을 병합하기


// 예시 [1,4,54,99] , [2,3,44,102] 라는 정렬된 두 개의 배열이 있다면, [1,2,3,4,44,54,99,102] 라는 배열로 병합합니다.

function merge(arr1, arr2) {
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j]);
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i]);
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j]);
        j++; 
    }
    return results;
}

여기까지가 병합 정렬의 첫 번째 핵심 파트입니다.

그 다음으로는 최초의 배열을 쪼개고, 또 쪼개고, 식의 반복을 어떻게 할 것인가에 대한 물음인데요, slice 메소드를 재귀 방식으로 활용합니다. 그리하여 제대로 쪼개진 배열은 다시금 위의 merge 함수에 left, right 값으로 두 개의 배열을 보내서 하나의 정렬된 배열 리턴값을 받아옵니다.


2. 분리하기 및 정렬하기


대부분의 병합 정렬 코드는 재귀를 사용합니다. 재귀 함수에 대해서 잘 모르신다면 재귀 함수에 관해 정리한 포스트 글이 있으니, 먼저 보고 오시는 것을 추천드립니다.

밑의 mergeSort 함수의 기반 조건(Base Case)은 배열의 길이가 1보다 작거나 같아야 한다입니다. 

function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid)); 
    return merge(left, right);   // 위에서 작성한 merge 함수를 사용합니다.
}

mergeSort([10, 24, 76, 73]);

재귀 함수를 실제로 사용한다는 것은 꽤나 혼란을 일으킬 수 있습니다. 병합 정렬의 코드 내용이 한번에 이해가 가지 않을 수 있고 기죽을 필요 없이 오히려 이는 당연하다고 합니다. 만약 이해가 쉽게 되지 않는다 하시면, 콘솔창의 break point를 활용하여, 각 호출 스택을 하나씩 확인해보시면서 정리해나기시는 것도 좋은 도움이 됩니다.

다음으로는 병합 정렬의 빅오 복잡도에 대해서 살펴봅니다.


Big O of mergeSort

  • Time Complexity(Best) - O(n log n)
  • Time Complexity(Average) - O(n log n)
  • Time Complexity(Worst) - O(n log n)
  • Space Complexity - O(n)
최상의 경우, 평균적인 경우, 최악의 경우 모두 시간 복잡도 면에서는 O(n log n)을 가집니다.

사실 병합 정렬은 최선, 평균, 최악의 경계값이 거의 없다고 봐도 무방합니다. 데이터가 어떻게 생겼는지 얼마나 복잡한지 신경을 쓰지 않고 효과도 없습니다. 그저 배열을 다 쪼갠 다음에 다시 하나하나 병합하는 겁니다.
이미 정렬이 되어있든, 반대로 정렬이 되어있든, 완전히 무작위이든간에 무방합니다. 이게 첫 번째 특징입니다.

두 번째로, 왜 병합 정렬은 n log n의 값을 가질까요? 이것을 반드시 알아야 하거나 계산할 줄 알아야 하는 것은 아닙니다만 기본적인 내용은 다음과 같습니다.

32개의 요소가 있는 배열을 받는다고 가정해보겠습니다. 이를 사용해서 쪼갠다면 16개의 요소가 든 배열이 두개가 나오고 그걸 다시 나누면 8개의 요소를 가진 4개의 배열이 나옵니다. 그리고 그걸 다시 쪼개면... 이러한 것을 계속 반복한다고 하면 결국 우리는 한 개의 요소를 가진 배열 32개를 가지게 됩니다.

여기에서 나누는 작업은 몇 번이 될까요? 배열의 길이가 n이고, n이 32라면 5번의 쪼개기 작업을 해야 합니다.
n이 8이면 3번이고요, 여기서 log n이 나옵니다. 배열의 길이가 n 증가할 때마다 쪼개는 횟수는 log n에 비례해서 늘어나는 거죠.


그러면 log n 앞에 있는 n은 어디서 나오는 걸까요?

우리가 배열을 쪼갤 때마다 생기는 배열들을 다시 합칠 때에는 빅오(n)번만의 비교를 매번 하게 됩니다. 즉 길이 n이 증가할수록 병합 알고리즘 그 자체는 merge 함수에서 빅오(n)의 시간 복잡도를 가지게 됩니다. 배열에 천 개의 요소가 있다면, 대략 천 번의 비교를 해야 합니다. 그래서 결국은 n log n의 값이 나오게 됩니다.


정리하자면 log n은 n이 커짐에 따라 늘어나는 분할의 횟수이고, 각각의 분할에 대해 병합을 다시 하려면 n번의 비교를 해야 합니다. 그래서 결국 빅오(n log n)의 값이 나옵니다! 그리고 정렬 알고리즘 중에서는 n log n의 시간복잡도가 최고입니다(이상한 데이터 형태때문에 이득이 생기는 상황이 아니라면) 👍.


마지막으로 공간복잡도를 보겠습니다. 이건 상수값을 가지는 버블 정렬과 비교하면 약간 다릅니다. 병합 정렬을 다룰 때는 배열이 커질수록 메모리에 저장해야 하는 배열의 개수가 많아집니다. 그래서 더 많은 공간이 필요합니다.
보통은 시간 복잡도에 더 집중을 하지만, 공간 복잡도 또한 고려 해야 합니다. 특히 병합 정렬 같은 경우는 버블 벙렬이나 다른 앞에서 배운 정렬들에 비하면 더 많은 공간을 점유합니다.

좋아요, 여기까지 병합 정렬의 빅오 복잡도였습니다! 다음 포스팅에서는 퀵 정렬에 대해서 다뤄볼 예정입니다.

# algorithms# merge# sort
© 2021 Createhb21.