C++ 합병정렬 소스(merge sort)

/*

2014.05.20

http://breath91.tistory.com

by_jacob(apodis91@naver.com/apodis91@ks.ac.kr)

*/ 

 

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

#define Max_Size 10           // 배열 사이즈 정의
#define Rand_Num() rand() % 10        // 난수발생 전처리

 

void merge(int low, int mid, int high);
void mergeSort(int low, int high);
void printArr(int a[], int n);
void copyArray(int start, int end);

//시간함수관련
time_t t1, t2;

// 빈 배열
static int mergeArr1[Max_Size]={0,};

// 정렬되지 않은 배열
static int mergeArr2[Max_Size]={0,};

int maxnumsize=sizeof(mergeArr2)/4;

// 합병정렬함수
void mergeSort(int low, int high) {

        int mid;

        if(low < high) {
                mid = (low + high)/2;
                mergeSort(low, mid);
                mergeSort(mid+1, high);
                merge(low, mid, high);

        }
}

 

/*

  TODO 이원합병정렬

  합병함수 - 오름차순

*/

void merge(int low, int mid, int high) {

        int i = low;
        int j = mid+1;
        int k = low;

        while (i<=mid && j<=high)
  {
                if(mergeArr2[i] < mergeArr2[j])
                   mergeArr1[k++] = mergeArr2[i++];
    else if(mergeArr2[i] >= mergeArr2[j])
                   mergeArr1[k++] = mergeArr2[j++];
        }

        // 남은 영역 조사후 mergedArr으로 복사

        if(i>=mid)
   while(j<=high)
    mergeArr1[k++] = mergeArr2[j++];
        if(j>=high)
   while(i<=mid)
    mergeArr1[k++] = mergeArr2[i++];

        copyArray(low, high);
}

 

// 배열 출력 함수

void printArr(int a[], int n) {

         int i;
         for (i=0; i<n; i++) {
   printf("%d ", a[i]);
         }
         printf("\n");
}

 

void copyArray(int start, int end) {

        int i;

        for (i=start; i<=end; i++) {
   mergeArr2[i] = mergeArr1[i];
        }
}

 

int main(int argc, char *argv[]) {
 //시간함수관련
 time(&t1);

 int i, j, size = sizeof( mergeArr2 ) / 4;     // 배열 갯수 선언
 srand( ( int ) time ( NULL ) );       // 난수 발생
 
 for( i = 0; i < Max_Size; i++ )
 mergeArr2[ i ] = Rand_Num();       // 난수를 배열에 저장

 printArr(mergeArr2, maxnumsize);
 mergeSort(0, maxnumsize);
 printArr(mergeArr2, maxnumsize);

 //시간함수관련
 time(&t2);
 printf("총 %f초가 걸렸습니다.", difftime(t2,t1));
  return 0;
}