#include <iostream> #include <ctime> #define SIZE 16 using namespace std; template <class data> void merge_sort(data *arr, int size); int main() { int arr[SIZE]; srand(time(0)); for(int i = 0 ; i < SIZE ; i++) { arr[i] = rand()%100 + 1; cout<<arr[i]<<" "; } merge_sort(arr, SIZE); cout<<endl<<endl; for(int i = 0 ; i < SIZE ; i++) { cout<<arr[i]<<" "; } return 0; } template <class data> void merge_sort(data *arr, int size) { if(size==1) { return; } merge_sort(arr, size/2); merge_sort(arr+(size/2), size-(size/2)); int tmp1[SIZE+1], tmp2[SIZE+1]; int i; int l = 0, r = 0; for(i = 0 ; i < size/2 ; i++) { tmp1[i] = arr[i]; } tmp1[i] = INT_MAX; for(i = 0; i < size-(size/2) ; i++) { tmp2[i] = arr[i+(size/2)]; } tmp2[i] = INT_MAX; for(i = 0 ; i < size ; i++) { if(tmp1[l] > tmp2[r]) { arr[i] = tmp2[r]; r++; } else { arr[i] = tmp1[l]; l++; } } }
'Algorithm > _Source' 카테고리의 다른 글
DFS를 이용한 스도쿠 문제 풀이 알고리즘 (0) | 2010.02.05 |
---|