#012_자료구조와 알고리즘_병합 정렬(Merge Sort)

안녕하세요 삽잡이입니다.

이번시간에는 병합 정렬에 대해서 알아보려고 합니다.

병합정렬은 분할 정복 방식에 기반으로 한 정렬 알고리즘입니다.

분할 정복? 많이 들어보시지 않았습니까? 

맞습니다... 퀵정렬에 대해서 알아볼 때 언급된 내용입니다. 기억이 나시죠? 하하하...

분할 정복이 기억이 안나시는 분들을 위해 간략하게 설명을 드리자면,

커다란 문제를 잘게 나눠서 작은 문제를 극복하는 것이죠...

작은 문제를 해결함으로 나온 값들을 합쳐 

결국 큰 문제를 해결하는 것이 분할 정복 방식의 핵심이라고 생각합니다.

 

병합 정렬은 분할 정복 방식을 기반으로 한다고 했습니다.

다른 정렬들과 다르게 병합 정렬은 기존 데이터가 담겨있는 배열 이외에 

추가적으로 또 다른 배일이 필요합니다. 이에 병합 정렬은 외부 정렬에 속하기도 합니다.

기존에 알아봤던 배열들은 그 배열 내에서 정렬했기 때문에 내부 정렬이라고 할 수 있지요...

아무튼, 병합 정렬에 간략한 소개를 해보도록 하지요...

우선, 정렬할 데이터 집합을 반으로 나눕니다.

그 다음 또 반으로 나누고 반으로 나누고 계속 나누어 

결국은 나눈 데이터의 집합이 하나가 될 때까지 나눕니다.

다음 나누어진 집합을 정렬하며 병합을 시작합니다... 원래 집합의 크기가 될 때 까지 말입니다!

그렇다면 퀵정렬가 뭔차이가 있느냐 한다면...

하나, 퀵 정렬같은 경우에는 정확하게 이분할 되지 않습니다.

병합 정렬은 정확하게(?) 이분할을 하지요...

병합 정렬의 핵심은 

바로, 잘게 나누어진 데이터의 집합이 두 개의 집합으로 나뉠 때입니다.

병합 정렬은 외부 정렬에 속한다고 했지요?

자... 잘개 쪼개어 정렬을 해가며 병합을 하다가 

두개의 정렬된 집합으로 나뉘어 졌을때 두 집합을 비교해가며 

작은 요소들을 원래 집합 크기의 새로운 배열에 차곡 차곡 추가하는 것입니다.

그렇다면, 의사코드(pseudo code)를 보여드리겠습니다.

//조건 : n이 1보다 작거나 같으면
    //종료
//merge_sort(base, n/2, compare) //정렬되고
//merge_sort(base+n/2, n-n/2, compare) // 정렬되고
 
//tbase 할당(n개 보관할 수 있는 임시 버퍼)
//i := 0; //앞쪽 배열을 위한 인덱스
//j := n/2; //뒷쪽 배열을 위한 인덱스
//k := 0; //임시 버퍼를 위한 인덱스
 
//반복 : i<n/2 이면서 j<n일 동안 (한쪽이라도 끝까지 가게되면 나머지들을 그대로 이동시키면 되지)
    //조건 : compare(base[i], base[j])<=0
        tbase[k] := base[i]
        i++;
    //아니면
        //tbase[k]:= base[j]
        //j++
    //k++
 
//반복 : i<n/2
    //tbase[k]:=base[i]
    //i++, k++
//반복 : j<n
    //tbase[l]:=base[j]
    //j++, k++
    //메모리 덤핑(base, tbase, n)
    //tbase 해제

자... 이렇게 의사 코드를 구현할 수 있을 것 같습니다...

나중에 비교해보시면 아시겠지만, 분명 quick 정렬은 빠르다고 했는데... 

병합 정렬이 더 빠른 것을 확인하실 수 있을 것입니다.

위에서 퀵 정렬과 병합 정렬의 차이점을 잠시 언급했었는데, 추가적으로 말씀드려보지요...

퀵 정렬의 경우에는 pivot 즉, 기준이 되는 값이 뭐냐에 의해서,

또한 해당 배열이 정렬되어있는지 아니면 엉망인지에 따라서 속도가 차이가 납니다.

하지만, 병합 정렬의 경우에는 위의 경우 모두 비슷하게 속도를 냅니다. 

추가적으로, 병합 정렬은 안정된 정렬이라고 할 수 있습니다.

안정된 정렬이란, 동일한 값에 의해 기존의 순서가 유지 되는 정렬 방식으로써

쉽게 표현하면, 정렬한뒤에 계속 같은 위치에 데이터가 있는 것이라고 할 수 있습니다.

의사 코드도 수정을 좀 해야하는데.... 코드도 구현해야하고....

근데 졸리네요...

다음시간에 하도록 하지요... 하하하...

이상 삽잡이였습니다!