문제 : 정렬 알고리즘의 실행시간 비교
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
출력
출력은 다음과 같은 형식으로 한다.
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 | #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
'대학교시절' 카테고리의 다른 글
프로그래밍 언어 정리 (0) | 2016.07.29 |
---|---|
알고리즘 과제 #4 (그래프 최소 경로 구하기) (0) | 2015.09.28 |
알고리즘 과제 #2 (인접한 노드 그래프 생성) (0) | 2015.09.28 |
알고리즘 과제 #1 (이진 트리 높이 구하기) (0) | 2015.09.28 |
운영체제 과제 #3 (mmap() 시스템콜 성능) (0) | 2015.09.28 |