알고리즘 정리 - 병합정렬

알고리즘 병합정렬은 배열을 정렬하는 효율적인 알고리즘 중 하나이다.

이 알고리즘은 분할 정복을 이용해서 정렬한다!

 

(1) 분할 : 배열을 반으로 나눈다. 이 과정은 배열을 작은 단위의 하위 배열로 계속해서 나누는 과정이다.

(2) 정복 : 각 하위 배열을 재귀적으로 정렬한다. 이 정렬은 배열이 충분히 작고 정렬된 상태(length가 1일때까지) 계속 된다.

(3) 병합 : 정렬된 하위 배열들을 병합하여 하나의 정렬된 배열을 만든다.

 

가장 극악의 상황에서도 O(NlogN)의 상황을 보장하는 알고리즘으로

꽤 효율적인 알고리즘이라고 할 수 있다

 

첨에는 진짜 무슨 소리인지 몰라서 ㅠㅠ 1시간을 넘도록 뚫어져라 쳐다보다가

재귀 << 를 놓친걸 까먹어서 겨우 이해할 수 있었다

 

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    // 왼쪽 배열이나 오른쪽 배열 중 남아있는 요소들을 result 배열에 추가
    // (어느 한 배열은 이미 모든 요소를 추가했기 때문에 나머지 배열의 요소들을 모두 추가해도 상관 없음)
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

const arr = [8, 3, 1, 7, 0, 10, 2];
console.log("정렬 전:", arr);
const sortedArr = mergeSort(arr);
console.log("정렬 후:", sortedArr);

 

처음에 할당받은 배열을 다 length가 1이 될 때 까지 분할한 후에

역으로 병합해 나가면서 최종적으로 정렬된 배열을 리턴하는 로직이다.

 

그러니까,,

[8, 3, 1, 7, 0, 10, 2]   (시작)
          ↓
  [8, 3, 1]   [7, 0, 10, 2]   (분할)
     ↓             ↓
  [8] [3, 1]    [7, 0] [10, 2]   (분할)
        ↓              ↓
     [3] [1]       [7] [0] [10] [2]   (분할)
        ↓              ↓
     [3, 1]       [7, 0] [10, 2]   (분할 완료 - 정복 시작?)
         ↓               ↓
     [1, 3]       [0, 7] [2, 10]   (정복)
         ↓               ↓
    [1, 3, 8]      [0, 2, 7, 10]   (병합)
         ↓                ↓
   [0, 1, 2, 3, 7, 8, 10]    (최종 병합)

 

이런 느낌?

중간에 분할 완료후에 1,3 정렬하고 도대체 8이 어케 튀어나오지 하고

이해를 못했는데 재귀를 생각하니 이해가 가는 코드였다