C++) 합병 정렬 (Merge Sort)

#include<iostream>

#include<windows.h>

#include<time.h>

#include<stdlib.h>

#include "sort.h"

#pragma warning (disable : 4996)

const int N = 10000;

int b[N + 1] , a[N+1];

void MergeSort(int a[], int l, int r)

{

int i, j, k, m;

if (r > l)

{

m = (r + l) / 2;

MergeSort(a, l, m);

MergeSort(a, m + 1, r);

for (i = m + 1; i > l; i--) b[i - 1] = a[i - 1];

for (j = m; j < r; j++) b[r + m - j] = a[j + 1];

for (k = l; k <= r; k++)

a[k] = b[i] < b[j] ? b[i++] : b[j--];

}

}

int main()

{

int i;

double start_time;

srand(time(NULL));

for (i = 1; i <= N; i++) a[i] = rand();

start_time = clock();

MergeSort(a, 1, N);

cout << "(난수값을 갖는 랜덤 배열일때) 합병 정렬의 실행 시간 (N = " << N << ") : " << (clock() - start_time)/CLOCKS_PER_SEC << "초" << endl;

CheckSort(a, N);

cout << endl;

int reverse = N;

for (i = 1; i <= N; i++) a[i] = reverse--;

start_time = clock();

MergeSort(a, 1, N);

cout << "(역순으로 정렬된 배열일때) 합병 정렬의 실행 시간 (N = " << N << ") : " << (clock() - start_time)/CLOCKS_PER_SEC << "초" << endl;

CheckSort(a, N);

cout << endl;

for (i = 1; i <= N; i++) a[i] = i;

start_time = clock();

MergeSort(a, 1, N);

cout << "(정렬된 배열) 합병 정렬의 실행 시간 (N = " << N << ") : " << (clock() - start_time) / CLOCKS_PER_SEC << "초" << endl;

CheckSort(a, N);

cout << endl;

system("pause");

return 0;

}