병합 정렬의 구현 (1) - 분할과 정복

이 글은 칸 아카데미 - 알고리즘을 정리한 글입니다.

 

 

 

실습 - 병합 정렬의 구현

병합 정렬을 간단하게 구현해보겠습니다. 이번 구현에 쓰이는 코드는 자바 스크립트입니다.ddd

 

var merge = function(array, p, q, r) {
    // This code has been purposefully obfuscated,
    //  as you'll write it yourself in next challenge.
    var a=[],b=[],c=p,d,e;for(d=0;c<=q;d++,c++){a[d]=array[c];}for(e=0;c<=r;e++,c++){b[e]=array[c];}c=p;for(e=d=0;d<a.length&&e<b.length;){if(a[d]<b[e]){array[c]=a[d];d++;} else {array[c]=b[e]; e++;}c++; }for(;d<a.length;){array[c]=a[d];d++;c++;}for(;e<b.length;){array[c]=b[e];e++;c++;}
};

우선 하위 배열 두 개를 결합 하는 기능을 담은 merge() 함수에 대해서는 다음 글에서 짚고 넘어가도록 하겠습니다. 먼저 저희는 재귀가 이루어지는 과정을 확인하겠습니다.

 

var mergeSort = function(array, p, r) {
    if(p<r)
    {
        var q = Math.floor((p+r)/2);
        mergeSort(array, p, q);
        mergeSort(array, q+1, r);
        merge(array, p, q, r);
    }
};

mergeSort(array, p, r)은 병합 정렬 함수입니다. 이 함수에서 탈출조건은 if(p<r)입니다. 이어서 q: var는 (p+r)/2를 내림해준 값입니다. 배열의 중간을 의미하는 q는 다시 한 번 병합 정렬 함수를 호출합니다. 대신 p~q까지의 배열, q+1에서 r까지의 배열을 호출합니다. 이렇게 절반씩 쪼개면서 탈출조건에 도달할때까지 재귀가 호출되며 이를 merge() 함수를 통해 병합시켜주면 원하는 결과가 도출됩니다.

 

var array = [14, 7, 3, 12, 9, 11, 6, 2];
mergeSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]);

이렇게 배열을 선언해주고 올바르게 작동하는지 테스트까지 완료했습니다.

 

 

 

---

 

 

 

결과

정상적으로 작성됐음을 확인했습니다. 다음 글에선 하위 배열 두 개를 병합시키는 (병합시키면서 정렬시키는) 기능을 담은 merge()에 대해서 알아보겠습니다.