merge sort(병합 정렬)

분할정복 접근법을 이용한 merge sort

분할 : 정렬할 n개의 원소의 수열을 n/2개씩 두 개의 부분 수열로 분할한다.

정복 : 병합 정렬을 이용해서 재귀적으로 그 두 부분 수열을 정렬한다.

결합 : 정렬된 두 개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다.

-> 여기서 정렬할 수열의 크기가 1이 되면 다 정렬된것이므로 더이상 재귀적 호출은

일어나지 않게됩니다.

병합을 위한 과정으로는 Merge(A,p,q,r)이 필요한데 여기서

A = 배열, p,q,r은 index입니다(p <= q < r) 

Merge는 두 부분 배열 A[p...q]와 A[q+1...r]이 정렬되어 있다고 가정하고

이들을 병합해서 하나의 정렬된 배열을 만들면서 원래의 부분 배열인

A[p...r]을 대체합니다.

/* merge.cpp */

 

#include <stdio.h>

#define LEN 9

 

void merge_sort(int num[], int start, int end);

void merge(int num[], int start, int median, int end);

int main()

{

        int i;

        int arr[LEN] = {10, 67, 63, 17, 23, 78, 12, 73, 86};

        merge_sort(arr, 0, LEN-1);

        for(i=0; i<LEN; i++)

        {

               printf("%d\t", arr[i]);

        }

}

void merge_sort(int num[], int start, int end) // arr를 두 덩어리의 배열로 나눈다

{

        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;

        j = median+1;

        k = start;

        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]; // 임시 배열에서 원래 배열로 데이터 넣기

}