Merge Sort (합병 정렬)

알고리즘

Array를 반씩 쪼갠다.

한번 쪼개면 두개의 큰 덩어리가 나올 것이다.

이렇게 나온 덩어리를 또 다시 쪼갠다.

이렇게 덩어리를 계속 쪼개다 보면, 결국 한 개의 원소가 하나의 덩어리가 된다.

이 상태에서 다시 덩어리를 뭉치는데, 그냥 뭉치는 것이 아니라

각각의 원소를 비교해 가면서 원소를 차례로 배열한다.

이런 식으로 덩어리를 계속 뭉쳐가다 보면 원래의 Array가 정렬된다.

이것이 합병 정렬의 기본 아이디어다.

코드

#include <stdio.h>
#define LEN 9

void merge_sort(int num[],int start, int end); 
void merge(int num[], int start, int mid, int end);
void tracer(int num[],int len);

int main(void){
    
    int testArr[LEN] = {485,241,454,325,452,685,498,890,281};
    merge_sort(testArr, 0, LEN-1);
}

void merge_sort(int num[],int start, int end){ // Array를 두개의 덩어리로 나눔
    int median = (start + end)/2; // 중간값 설정
    if(start < end){ // 덩어리의 원소가 하나일 때까지
        merge_sort(num, start, median); 
        merge_sort(num, median+1, end); // 각각의 덩어리로 재귀함수 호출 
        merge(num, start, median, end); // 각각의 덩어리를 뭉치면서 정렬
    }
}

void merge(int num[], int start, int median, int end){
    int i,j,k,m,n;
    int tempArr[LEN]; // 임시로 데이터를 저장할 배열
    i = start; // 앞의 덩어리의 시작 Index
    j = median+1; // 뒤의 덩어리의 시작 Index
    k = start; // 임시 배열의 시작 Index

    while (i <= median && j <= end){
        tempArr[k++] = (num[i] > num [j]) ? num [j++] : num [i++];
        //작은 숫자를 찾아 임시 배열에 넣는다. 어느쪽 덩어리든 Index의 끝에 닿으면 빠져나온다.
    }
    
    // 아직 배열에 속하지 못한 부분들을 넣기 위한 부분
    m = (i > median) ? j : i; // 아직 원소가 남아있는 덩어리가 어디인지 파악
    n = (i > median) ? end : median; // 마찬가지로, for문의 끝 Index를 정하기 위함임

    for (; m<=n; m++){ // 앞에서 구한 m, n으로 배열에 속하지 못한 원소들을 채워넣음
        tempArr[k++] = num[m];
    }

    for (m=start; m<=end; m++){
        num[m] = tempArr[m]; // 임시 배열에서 원래 배열로 데이터 옮기기
    }
    printf("Merging: %d ~ %d & %d ~ %d\n",start,median,median+1,end);
    tracer(num,LEN);
}

void tracer(int num[],int len){
    int i;
    for(i=0;i<len;i++){
        printf("%d\t",num[i]);
    }
    printf("\n\n");
}

결과

분석

위에서 9개의 원소를 가진 배열의 인덱스를 각각 0 ~ 8 이라고 했을때,

다음과 같은 덩어리로 나뉘어진다.

(((0, 1), 2), (3, 4)), ((5, 6), (7, 8))

결과에서 표시하고 있는 것은 이렇게 나뉘어진 원소들의 Index와 병합한 이후의 Array라고 할 수 있다.