알고리즘 과제 #3 (정렬 및 속도 비교)

문제 :  정렬 알고리즘의 실행시간 비교

1. Exchange sort, Merge Sort와 Quick Sort 알고리즘들을 구현하고, key를 비교한 횟수, key가 move된 횟수, 실행시간을 측정하여 비교한다. (clock 함수 사용)

2. 원소 개수가 다른 3가지 정렬된 데이터(S[i] = i, 1≤ i ≤n)를 생성하여 Exchange sort와 Quick Sort를 비교한다. 단, n은 실행시간이 충분한 유효 숫자를 가질 수 있도록 각자 정한다.

3. 원소 개수가 다른 3가지 임의의 데이터를 생성하여 Merge Sort와 Quick Sort를 비교한다. 각 경우에 대해 (원소 개수가 같은) 5개의 데이터를 생성하여 평균값을 구한다. 데이터는 프로그램 안에서 생성한다. 

4. 측정된 실행시간과 이론적 시간 복잡도가 일치하는지 분석한다. 

입력

입력 파일의 이름은 input.txt이다. 처음 세 줄에는 정렬된 데이터의 크기가 입력된다. 그 다음 세 줄에 임의의 데이터의 크기가 입력된다.

10 /* 정렬된 데이터의 크기

20

30

100 /* 임의 생성된 데이터의 크기

200

300

출력

출력은 다음과 같은 형식으로 한다. 

소스코드

#include "time.h" #include "stdlib.h" #include<iostream> #include<fstream> #include<iomanip> using namespace std; /* 프로그램 작성자 : americano@korea.ac.kr 개발 날짜 : 2012-4-3 */ typedef struct sortKey{ int compares, moves; double time; }key; typedef key* Kptr; //배열에 정렬된 데이터 입력 void creatSortedData(int* ary1, int* ary2, int size); //배열에 임의의 데이터 입력 void creatRandomData(int* ary1, int* ary2, int size); //표로 결과값을 출력함 void print(Kptr eKey, Kptr qKey1, Kptr mKey, Kptr qKey2, int* size1, int* size2); //교환정렬 void Exchange(int* ary, int size, Kptr eKey); //합병정렬2 void Merge2(int low, int mid, int high, int* ary, Kptr mKey); //합병정렬 void Merge(int low, int high, int* ary, Kptr mKey); //쾌속정렬 void Quick(int low, int high, int* ary, Kptr qKey); //분할함수 void partition(int low, int high, int *pivot, int* ary, Kptr mKey); int main(){ ifstream fin; fin.open("input.txt"); int size1[3], size2[3]; fin>>size1[0]>>size1[1]>>size1[2]; fin>>size2[0]>>size2[1]>>size2[2]; //키값을 모두 0으로 초기화시킴 key exchangeKey[3] = {{0,0,0},{0,0,0},{0,0,0}}; key mergeKey[3] = {{0,0,0},{0,0,0},{0,0,0}}; key quickKey1[3] = {{0,0,0},{0,0,0},{0,0,0}}; key quickKey2[3] = {{0,0,0},{0,0,0},{0,0,0}}; srand((unsigned)time(NULL)); for(int i = 0; i<3; i++){ //각 정렬함수가 정렬하려고하는 데이터 배열 동적할당 int *sortBox1 = new int[size1[i]]; int *sortBox2 = new int[size1[i]]; int *randBox1 = new int[size2[i]]; int *randBox2 = new int[size2[i]]; //배열에 데이터입력 creatSortedData(sortBox1, sortBox2, size1[i]); creatRandomData(randBox1, randBox2, size2[i]); //정렬된 데이터 교환정렬시작 및 시간측정 clock_t time = clock(); Exchange(sortBox1 , size1[i], exchangeKey+i); exchangeKey[i].time = ((double)(clock()- time))/CLOCKS_PER_SEC; //정렬된 데이터 쾌속정렬시작 및 시간측정 time = clock(); Quick(0, size1[i]-1, sortBox2, quickKey1+i); quickKey1[i].time = ((double)(clock()- time))/CLOCKS_PER_SEC; //임의의 데이터 합병정렬 시작및 시간측정 time= clock(); Merge(0, size2[i]-1, randBox1, mergeKey+i); mergeKey[i].time = ((double)(clock()- time))/CLOCKS_PER_SEC; //임의의 데이터 쾌속정렬 시작 및 시간측pp정 time = clock(); Quick(0, size2[i]-1, randBox2 , quickKey2+i); quickKey2[i].time = ((double)(clock()- time))/CLOCKS_PER_SEC; delete []sortBox1; delete []sortBox2; delete []randBox1; delete []randBox2; } //표로 키값을 출력함 print(exchangeKey, quickKey1, mergeKey, quickKey2, size1, size2); fin.close(); } //배열에 정렬된 데이터 입력 함수 void creatSortedData(int* ary1, int* ary2, int size){ for(int i = 0; i<size; i++){ ary1[i] = i; ary2[i] = i; } } //배열에 임의의 데이터 입력 함수 void creatRandomData(int* ary1, int* ary2, int size){ for(int i = 0; i<size; i++){ ary1[i] = rand()%size; ary2[i] = rand()%size; } } //비교횟수, 이동횟수, 걸린시간을 표로 출력하는 함수 void print(Kptr eKey, Kptr qKey1, Kptr mKey, Kptr qKey2, int* size1, int* size2){ cout<<setw(30)<<""<<setw(6)<<"N="<<setw(7)<<size1[0]<<setw(6)<<"N="<<setw(7)<<size1[1]<<setw(6)<<"N="<<setw(7)<<size1[2]<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Compares"<<setw(13)<<eKey[0].compares<<setw(13)<<eKey[1].compares<<setw(13)<<eKey[2].compares<<endl; cout<<setw(15)<<"Exchange sort"<<setw(15)<<"Key Moves"<<setw(13)<<eKey[0].moves<<setw(13)<<eKey[1].moves<<setw(13)<<eKey[2].moves<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Time"<<setw(13)<<eKey[0].time<<setw(13)<<eKey[1].time<<setw(13)<<eKey[2].time<<endl<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Compares"<<setw(13)<<qKey1[0].compares<<setw(13)<<qKey1[1].compares<<setw(13)<<qKey1[2].compares<<endl; cout<<setw(15)<<"Quick sort"<<setw(15)<<"Key Moves"<<setw(13)<<qKey1[0].moves<<setw(13)<<qKey1[1].moves<<setw(13)<<qKey1[2].moves<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Time"<<setw(13)<<qKey1[0].time<<setw(13)<<qKey1[1].time<<setw(13)<<qKey1[2].time<<endl<<endl<<endl; cout<<setw(30)<<""<<setw(6)<<"N="<<setw(7)<<size2[0]<<setw(6)<<"N="<<setw(7)<<size2[1]<<setw(6)<<"N="<<setw(7)<<size2[2]<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Compares"<<setw(13)<<mKey[0].compares<<setw(13)<<mKey[1].compares<<setw(13)<<mKey[2].compares<<endl; cout<<setw(15)<<"Merge sort"<<setw(15)<<"Key Moves"<<setw(13)<<mKey[0].moves<<setw(13)<<mKey[1].moves<<setw(13)<<mKey[2].moves<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Time"<<setw(13)<<mKey[0].time<<setw(13)<<mKey[1].time<<setw(13)<<mKey[2].time<<endl<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Compares"<<setw(13)<<qKey2[0].compares<<setw(13)<<qKey2[1].compares<<setw(13)<<qKey2[2].compares<<endl; cout<<setw(15)<<"Quick sort"<<setw(15)<<"Key Moves"<<setw(13)<<qKey2[0].moves<<setw(13)<<qKey2[1].moves<<setw(13)<<qKey2[2].moves<<endl; cout<<setw(15)<<""<<setw(15)<<"Key Time"<<setw(13)<<qKey2[0].time<<setw(13)<<qKey2[1].time<<setw(13)<<qKey2[2].time<<endl; } //교환정렬함수 void Exchange(int* ary, int size, Kptr eKey){ for(int i = 1; i<= size-1; i++){ for(int j = i+1; j<size; j++){ eKey->compares++; if(ary[j]<ary[i]){ eKey->moves += 3; int temp = ary[i]; ary[i] = ary[j]; ary[j] = temp; } } } } //합병정렬함수2 void Merge2(int low, int mid, int high, int* ary, Kptr mKey){ int i = low; int j = mid+1; int k = 0; int* newAry = new int[high-low+1]; while(i <= mid && j <= high){ mKey->compares++; if(ary[i] < ary[j]){ newAry[k] = ary[i]; mKey->moves++; i++; } else{ mKey->moves++; newAry[k] = ary[j]; j++; } k++; } if(i>mid){ while(j<=high){ mKey->moves++; newAry[k++] = ary[j++]; } } else{ while(i<=mid){ mKey->moves++; newAry[k++] = ary[i++]; } } for(k=0; k<=(high-low); k++){ mKey->moves++; ary[low+k] = newAry[k]; } delete[] newAry; } //합병정렬함수 void Merge(int low, int high, int* ary, Kptr mKey){ int mid; if(low<high){ mid = ((low+high)/2); Merge(low, mid, ary, mKey); Merge(mid+1,high, ary, mKey); Merge2(low,mid,high,ary,mKey); } } //쾌속정렬함수 void Quick(int low, int high, int* ary, Kptr mKey){ int pivot; if(high>low){ partition(low, high, &pivot, ary, mKey); Quick(low, pivot-1, ary, mKey); Quick(pivot+1, high, ary, mKey); } } //쾌속정렬에 쓰이는 분할 함수 void partition(int low, int high, int *pivot, int* ary, Kptr mKey){ int i, j; int item = ary[low]; j = low; for(i = low+1; i<= high; i++){ mKey->compares++; if(ary[i]<item){ j++; mKey->moves += 3; int temp = ary[i]; ary[i] = ary[j]; ary[j] = temp; } } *pivot = j; mKey->moves += 3; int temp = ary[low]; ary[low] = ary[j]; ary[j] = temp; }

보고서 문서

정렬 알고리즘의 실행시간 비교_by AmericanoJH.pdf