본문 바로가기

대학교시절

알고리즘 과제 #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



출력


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




소스코드


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