[자료구조]병합 정렬

병합 정렬(Merge Sort)

병합 정렬은 분할 정복이라는 알고리즘 디자인 기법에 근거하여 만들어 졌다. 분할 정복이란 복잡한 문제를 복잡하지 않은 문제로 분할해 정복하는 방법이다. 정복 후에는 결합 과정이 필요하다.

1.분할 : 해결이 용이한 단계까지 문제를 분할해 나간다.

2.정복 : 해결이 용이한 수준까지 분할된 문제를 해결한다.

3.결합 :분할해서 해결한 결과를 결합하여 마무리한다.

 

8개의 데이터를 4개로, 4개를 2개로, 2->1 로 나누어 정렬하고 크기에 맞춰 결합을 한다.

나눌 때 사용되는 방법은 재귀 함수가 있겠다.

 

 

위 사진이 병합 정렬을 도식화한 것이다.

 

 

정렬 함수를 살펴보자.

void MergeSort(int *arr,int left,int right);

첫번째 인자로 정렬대상이 담긴 배열의 주소를 전달하고, 두번째 인자와 세번째 인자로 대상의 범위정보를 인덱스 값의 형태로 전달한다.

이전까지는 데이터의 개수를 전달했지만 이번엔 시작 배열,끝 배열을 전달했다. 정렬 대상의 범위가 계속해서 바뀌기 때문이다.

 

void MergeSort(int *arr,int left,int right){
	int mid;
    
    if(left < right){
    	mid = (left+right)/2;
        
        MergeSort(arr,left,mid);
        MergeSort(arr,mid+1,right);
        
        MergeTwoArea(arr,left,mid,right);
    }
}

 

재귀함수로 MergeSort가 계속해서 호출된다. if조건에 의해 배열이 한개 남을 때까지 계속 호출된다.

이 때, MergeTwoArea함수도 재귀함수 내에 같이 호출된다. 그 과정에서 배열들이 크기 순으로 정렬이 된다.

 

그럼 MergeTwoArea함수는 무엇일까?

코드를 보자.

 

 

void MergeTwoArea(int *arr,int left,int mid,int right){
    int fidx = left;
    int ridx = mid+1;
    int i;

    int * sortArr = (int*)malloc(sizeof(int)*(right+1));    //right(6)+1개 만큼 배열 만듬,형변환을 하는 이유는?
    int sidx = left;

    while(fidx <= mid && ridx <= right){    
        if(arr[fidx]<=arr[ridx]){    
            printf("sortArr[%d] = %d\n",sidx,arr[fidx]);
            sortArr[sidx] = arr[fidx++];    
        }
        else{
            printf("sortArr[%d] = %d\n",sidx,arr[fidx]);
            sortArr[sidx] = arr[ridx++];
        }
        
        sidx++;
    }

    if(fidx > mid){ //mid다음 부터 병합
        for(i=ridx;i<=right;i++,sidx++){
            printf("sortArr[%d] = %d\n",sidx,arr[fidx]);
            sortArr[sidx] = arr[i];
        }
    }
    else{
        for(i=fidx;i<=mid;i++,sidx++){
            printf("sortArr[%d] = %d\n",sidx,arr[fidx]);
            sortArr[sidx] = arr[i];
        }
    }
    for(i=left;i<=right;i++)
        arr[i] = sortArr[i];

    free(sortArr);
}

 

전체 코드는

 

#include<stdio.h>
#include<stdlib.h>

void MergeTwoArea(int *arr,int left,int mid,int right){
    int fidx = left;
    int ridx = mid+1;
    int i;

    int * sortArr = (int*)malloc(sizeof(int)*(right+1));    //right(6)+1개 만큼 배열 만듬,형변환을 하는 이유는?
    int sidx = left;

    while(fidx <= mid && ridx <= right){    //끝까지 가면
        if(arr[fidx]<=arr[ridx])  //왼쪽 배열과 오른쪽 배열을 비교
            sortArr[sidx] = arr[fidx++];    //왼쪽이 작으면 값 리턴 후 한칸 앞으로
        
        else
            sortArr[sidx] = arr[ridx++];    //오른쪽이 작으면 값 리턴 후 한칸 앞으로
        
        
        sidx++;
    }

    if(fidx > mid){ //남은걸 병합
        for(i=ridx;i<=right;i++,sidx++)
            sortArr[sidx] = arr[i];
        
    }
    else{
        for(i=fidx;i<=mid;i++,sidx++)
            sortArr[sidx] = arr[i];
        
    }
    for(i=left;i<=right;i++)
        arr[i] = sortArr[i];

    free(sortArr);
}

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

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

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

int main(){
    int arr[7] = {3,2,4,1,7,6,5};
    int i;
    
    MergeSort(arr,0,sizeof(arr)/sizeof(int)-1);

    for(i=0;i<7;i++)
        printf("%d ",arr[i]);

}

 

병합 정렬의 성능을 평가해보자.

 

병합 1단계를 보자.

이렇게 병합하는 부분에서 비교연산이 1회 일어난다.

그리고 각 MergeTwoArea함수의 if~else 부분에서 비교연산이 1회 일어나 총 2회이다.

 

 

총 4번 있으니 8회의 비교연산.

 

다음은 병합 2단계이다.

 

이 과정에서 최대 비교연산 횟수는 4회이다.

13과 15, 25와 15, 25와22, 마지막 25의 if~else연산

 

이게 2개 있으니 총 8회이다.

 

병합 1단계와 2단계를 합쳐 16회의 비교연산이 일어난다. 즉, n개의 데이터에 대해 2n번의 연산이 일어난다는 의미이다.

2n은 n과 같다고 볼 수 있으니 O(nlog 2 n)이다. 여기서 log 2 n인 이유는 8개의 데이터에 대해 3번의 병합 단계가 있어서 이다.