[정렬 알고리즘 - 2] 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

---

이번에 알아볼 정렬 알고리즘은 Merge Sort 입니다. Merge Sort는 정렬할 배열을 최소 단위로 분할 후에 정렬을 하는 알고리즘인데요. 그림으로 보면 무슨 뜻인지 알 수 있습니다.

처음 병합 정렬이라고 하면 느낌이 오지 않더라구요. 저도 처음 강의자료로 봤는데 뭔소린가 싶어서..ㅋㅋ 이리저리 찾아보니까 쪼개고 합치는거로...

그러면 코드로 만든다면 어떻게 만들까요!?!? 정답은 recursive에 있습니다! 먼저 절차를 한번 잘 생각해봅시다.

---

1. 배열을 반으로 잘게잘게 쪼개버린다.
2. 다시 합쳐버린다.

---

간단하게 쪼개는 함수를 sort라고 하고 합치는 함수를 merge라고 하고 pseudo code를 써보면 이렇게 나타낼 수 있겠죠.

배열 A와 길이 n이 있다고 하고,
sort(A,N)
	len1 = n/2 // 앞부분 데이터량
	len2 = n - n/2 // 뒷부분 데이터량
	A -> frontA, backA // 쪼개버려
	sort(frontA,len1) //앞부분 쪼개
	sort(backA,len2)  //뒷부분 쪼개
	merge(len1,len2,frontA,backA) // 쪼갠거 다시 합쳐

조금 이해가 되시나요?? 재귀 함수를 사용해서 보다 편하게 볼 수가 있네요. 코드도 똑같습니다. C, C++은 배열도 주소값으로 할당되기 때문에 그냥 보내주기만 하면되고 ㅎㅎ 정렬이 되면 알아서 값이 바뀌겠죠. 또 함수 호출은 stack의 원리를 사용하니까 merge함수 부분은 다 쪼개진 후에 차근차근 들어가겠죠??

void sort(int n, int *data)
{
    if(n==1) return;
    int len1 = n/2;   //data앞부분
    int len2 = n-n/2; //data뒷부분
    int *data_front, *data_back;
    data_front = data;
    data_back = data+len1;
    sort(len1, data_front);
    sort(len2, data_back);
    
    merge(len1,len2,data_front,data_back,data);
}

이렇게 하면 sort부분이 마무리 되었네요!!! 그럼 merge함수는 어떻게 해결할까요?? 그림을 보면 합치는 부분은 합쳐지는 두 배열이 정렬이 되어있고 합쳐지니까 merge에 들어가는 두 배열도 정렬이 되어있는 것을 전제로 정렬해봅시다.

---

1. 빈 공간을 생성하고 두 배열의 값을 비교해보고 배열 한개가 전부 들어가질 때 까지 집어넣자.
2. 남은 배열의 정보를 모두 뒤에 이어버리자.

---

이런 생각은 두 배열이 모두 정렬이 되어있는 상태라는 전제가 있기 때문에 가능한거겠죠? 완성된 코드는 다음과 같습니다.

void merge(int len1, int len2, int* data_front, int* data_back, int* data)
{
    int i,j;
    int length=0;
    int* result;
    result = new int[len1+len2];
    
    for(i=0,j=0;i<len1 && j<len2;)
    {
        if(data_front[i] > data_back[j]) result[length++] = data_back[j++];
        else                             result[length++] = data_front[i++];
    }
    if(i==len1) // data_front가 다 사용되면
    {
        while(j<len2) result[length++] = data_back[j++];
    }
    else if(j==len2)
    {
        while(i<len1) result[length++] = data_front[i++];
    }
    for(int x=0; x<len1+len2; x++)
    {
        data[x] = result[x];
    }
}

제가 코딩을 좀 단순하게 해서 복잡할 수도 있겠네요..ㅎㅎㅎ 무튼 이렇게 merge sort까지 해보았습니다!