c언어 - 병합 정렬(Merge Sort)

이전 글에서 퀵 정렬에 대해 포스팅 했다.

병합 정렬은 퀵 정렬과 매우 비슷하지만 조금 다른 정렬이다.

퀵 정렬은 피벗을 정해 정렬을 하는데 피벗을 선택하는데서 정렬의 성능이 정해진다.

병합 정렬은 배열의 크기를 반으로 쪼개 정렬해 정렬되는 속도가 일정하다.

시간 복잡도로 보면

	최악	평균	최선
퀵 정렬	O(N^2)	O(NlogN)	O(NlogN)
병합 정렬	O(NlogN)	O(NlogN)	O(NlogN)

시간 복잡도를 보면 평균은 비슷 하지만 최악에서 차이가 난다. O(N^2)는 버블, 선택 정렬과 같아 느리다.

속도가 일정하다는 장점을 가지고 있다.

단점은 메모리가 필요하다. 병합과정에서 같은 사이즈의 다른 배열에 임시로 저장하기 때문이다.

 

이제 병합 정렬은  배열의 크기/2 의 값을 기준으로 좌, 우로 나눠지면서 값을 쪼갠다.

나눠지는 값들의 크기가 1일때 병합을 시작 하며 이때 정렬이 이뤄지고, 다시 배열의 크기까지 병합을 한다.

 

핵심 알고리즘

---

    LS = left;
    RS = mid +1;
    toM = left;
    while(toM <= right) {
        if(RS > right)
            m[toM++] = arr[LS++];
        else if(LS > mid)
            m[toM++] = arr[RS++];
        else if(arr[LS] <= arr[RS])
            m[toM++] = arr[LS++];
        else if(arr[LS] >= arr[RS])
            m[toM++] = arr[RS++];
    }
//같은 사이즈 다른 배열에 저장된 값을 가져오는 부분
    for(l=left;l<=right;l++
        arr[l] = m[l];

일단 mid 값을 구할때 분할할 값의 첫 시작점과 끝 점을 더한후 나눈다.

그래야 중간값을 분할할 수가 있다.

그리고 분할한 값을의 첫 자리부터 비교하여 병합을 하고 각 자리수를 증가하며 정렬한다.

그 후 비교되지 않은 자리의 값들도 넣어줘야한다. 

 

 

코드

---

#include<stdio.h>

void Combine(int *arr,int left, int mid, int right );
void Divide(int *arr, int left, int right);

# define n 10
int m[n];

int main()
{
    int arr[n] = {9,6,5,8,10,1,3,7,4,2};
    Divide(arr,0,n-1);

    for(int c=0;c<n;c++)
        printf("%d ",arr[c]);
}

void Combine(int *arr,int left,int mid, int right )
{
    int LS, RS, toM, l;
    LS = left;
    RS = mid +1;
    toM = left;
    while(toM <= right) {
        if(RS > right)
            m[toM++] = arr[LS++];
        else if(LS > mid)
            m[toM++] = arr[RS++];
        else if(arr[LS] <= arr[RS])
            m[toM++] = arr[LS++];
        else if(arr[LS] >= arr[RS])
            m[toM++] = arr[RS++];
    }
    for(l=left;l<=right;l++)
        arr[l] = m[l];
}

void Divide(int *arr, int left, int right)
{
    int mid;

    if(left < right) {
    mid = (left+right)/2;
    Divide(arr, left, mid);
    Divide(arr, mid+1, right);

    Combine(arr, left, mid, right);
    }
}