[7][알고리즘 - 정렬] 병합정렬(Merge Sort)이란? javascript 구현

병합 정렬이란

 

출처 - https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

합병 정렬 또는 병합 정렬이라고 불리며

O(n log n) 비교 기반 정렬 알고리즘입니다.

일반적인 방법으로 구현했을 때

이 정렬은 안정 정렬에 속하며,

분할 정복 알고리즘의 하나입니다.

 

출처 - https://commons.wikimedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

 

정렬하고자 하는 데이터의 모임을

비슷한 크기의 두 부분으로 반복하여 나눈 뒤, 

나누어진 부분 데이터들을 정렬한 다음에 

다시 병합하면서 하나의 정렬된 데이터 모임으로 

만드는 방법입니다.

 

// 합병 정렬
const merge = (left, right) => {
    let arr = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) arr.push(left.shift());
        else arr.push(right.shift());
    }
    return [...arr, ...left, ...right];
}

// 합병 정렬
const mergeSort = (array) => {
    if (array.length < 2) return array;
    const half = array.length / 2;
    const left = array.splice(0, half);
    return merge(mergeSort(left), mergeSort(array));
}


/// 실행

// 임의 배열 만들기
const makeRandomValueArr = (length) => {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }

    for (let i = 0; i < arr.length; i++) {
        const randomNum = Math.floor(Math.random() * arr.length);
        [arr[i], arr[randomNum]] = [arr[randomNum], arr[i]];
    }

    return arr;
}

const arr = makeRandomValueArr(10); // 10개

console.log('arr==', arr);
// [1, 3, 4, 5, 8, 0, 6, 7, 9, 2]
console.time('merge');
const result = mergeSort(arr);
console.timeEnd('merge');
console.log('result==', result);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

사실 코드로만 보거나,

글만 읽어서는 이해하기가 정말 힘들었습니다.

 

merge라는 병합 기능을 만들고

하나하나 log로 찍어보면서

결국엔 가장 위에 애니메이션을

다시 보고 과정을 반복해야

이해가 되더군요.

 

이러한 알고리즘을 어떻게 생각해냈는지

정말 놀라울 따름입니다.