[게임알고리즘] 1-4강 정렬

[DSU] 게임알고리즘 2026. 3. 13. 00:38

728x90

이름은 A에서 Z까지이며, 각 이름별 1점에서100점까지 랜덤하게 점수입력 후,

다양한 유형의 정렬로, 오름차순으로 이름과 점수를 구하는데 걸리는 시간을 각각 측정하고,

측정한 시간을 기준으로, 오름차순으로 정렬의 이름과 걸린 시간을 출력하기.

1. 정렬별 시간을 구하기

- 함수 포인터를 이용하기 반복문 만들기

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

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
 
// 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
struct Data {
    char name[2];
    int score;
};
 
void bubbleSort(Data* d, int n);
void selectionSort(Data* d, int n);
void insertionSort(Data* d, int n);
void mergeSort(Data* d, int n);
void quickSort(Data* d, int n);
void heapSort(Data* d, int n);
void countingSort(Data* d, int n);
 
typedef void (*Method)(Data* d, int n);
Method method[] = {
    bubbleSort, selectionSort, insertionSort,
    mergeSort, quickSort, heapSort, countingSort
};
    
int main() {
    
    // 멀티플레이에서 같은 랜덤값 공유하기 위해서는 시드값 공유
    // 흐르는 시간은 매번 다르기 때문에 시드값으로 훌륭함
    int seed = time(NULL);
    srand(seed);
 
    // 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
    int num = 'Z' - 'A' + 1;
    Data* data = new Data[num];
     for(int i=0; i<num; i++)
    {
        Data* d = &data[i];
        d->name[0] = 'A' + i;
        d->name[1] = 0;
        d->score = 1 + rand() % 100;
    }
    
    Data* tmp = new Data[num];
    
    // 정렬별 걸리는 시간 측정
    for(int i=0; i<7; i++)
    {
        memcpy(tmp, data, sizeof(Data) * num);
        
        clock_t start = clock();
        method[i](tmp, num);
        clock_t end = clock();
        double takeTime = (double)(end - start) / CLOCKS_PER_SEC;
        printf("sort[%d] 걸린 시간: %f 초\n", i, takeTime);
    }
    
    delete tmp;
    delete data;
 
    return 0;
}
 
void bubbleSort(Data* d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k-i; j++) {
            if(d[j].score > d[j+1].score) {
                Data t = d[j];
                d[j] = d[j+1];
                d[j+1] = t;
            }
        }
    }
}
 
void selectionSort(Data* d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(d[j].score < d[min].score)
                min = j;
        }
 
        Data t = d[i];
        d[i] = d[min];
        d[min] = t;
    }
}
 
void insertionSort(Data* d, int n) {
    Data key;
    for(int i = 1; i < n; i++) {
        key = d[i];
        int j = i - 1;
 
        while(j >= 0 && d[j].score > key.score) {
            d[j+1] = d[j];
            j--;
        }
 
        d[j+1] = key;
    }
}
 
void mergeSort(Data* d, int n) {
    bubbleSort(d, n);// 별도 구현
}
 
void quickSort(Data* d, int n) {
    bubbleSort(d, n);// 별도 구현
}
 
void heapSort(Data* d, int n){
    bubbleSort(d, n);// 별도 구현
}
 
void countingSort(Data* d, int n) {
    bubbleSort(d, n);// 별도 구현
}
Colored by Color Scripter

cs

2. 구조체로 묶는다.

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

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
 
// 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
struct Data {
    char name[2];
    int score;
};
 
struct Sort {
    static void bubble(Data* d, int n);
    static void selection(Data* d, int n);
    static void insertion(Data* d, int n);
    static void merge(Data* d, int n);
    static void quick(Data* d, int n);
    static void heap(Data* d, int n);
    static void counting(Data* d, int n);
};
 
typedef void (*Method)(Data* d, int n);
Method method[] = {
    Sort::bubble, Sort::selection, Sort::insertion,
    Sort::merge, Sort::quick, Sort::heap, Sort::counting, 
};
    
int main() {
    
    // 멀티플레이에서 같은 랜덤값 공유하기 위해서는 시드값 공유
    // 흐르는 시간은 매번 다르기 때문에 시드값으로 훌륭함
    int seed = time(NULL);
    srand(seed);
 
    // 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
    int num = 'Z' - 'A' + 1;
    Data* data = new Data[num];
     for(int i=0; i<num; i++)
    {
        Data* d = &data[i];
        d->name[0] = 'A' + i;
        d->name[1] = 0;
        d->score = 1 + rand() % 100;
    }
    
    Data* tmp = new Data[num];
    
    // 정렬별 걸리는 시간 측정
    for(int i=0; i<7; i++)
    {
        memcpy(tmp, data, sizeof(Data) * num);
        
        clock_t start = clock();
        method[i](tmp, num);
        clock_t end = clock();
        double takeTime = (double)(end - start) / CLOCKS_PER_SEC;
        printf("sort[%d] 걸린 시간: %f 초\n", i, takeTime);
    }
    
    delete tmp;
    delete data;
 
    return 0;
}
 
void Sort::bubble(Data* d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k-i; j++) {
            if(d[j].score > d[j+1].score) {
                Data t = d[j];
                d[j] = d[j+1];
                d[j+1] = t;
            }
        }
    }
}
 
void Sort::selection(Data* d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(d[j].score < d[min].score)
                min = j;
        }
 
        Data t = d[i];
        d[i] = d[min];
        d[min] = t;
    }
}
 
void Sort::insertion(Data* d, int n) {
    Data key;
    for(int i = 1; i < n; i++) {
        key = d[i];
        int j = i - 1;
 
        while(j >= 0 && d[j].score > key.score) {
            d[j+1] = d[j];
            j--;
        }
 
        d[j+1] = key;
    }
}
 
void Sort::merge(Data* d, int n) {
    bubble(d, n);// 별도 구현
}
 
void Sort::quick(Data* d, int n) {
    bubble(d, n);// 별도 구현
}
 
void Sort::heap(Data* d, int n){
    bubble(d, n);// 별도 구현
}
 
void Sort::counting(Data* d, int n) {
    bubble(d, n);// 별도 구현
}
 
Colored by Color Scripter

cs

 

3. 각 정렬별 걸린 시간에 따라 정렬한 결과값을 출력한다.

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

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
 
// 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
struct Data {
    char name[2];
    int score;
};
 
struct Sort {
    static void bubble(Data* d, int n);
    static void selection(Data* d, int n);
    static void insertion(Data* d, int n);
    static void merge(Data* d, int n);
    static void quick(Data* d, int n);
    static void heap(Data* d, int n);
    static void counting(Data* d, int n);
};
 
typedef void (*Method)(Data* d, int n);
 
struct SortInfo {
    Method method;
    const char* name;
    double takeTime;
};
 
SortInfo sortInfo[] = {
    { Sort::bubble, "bubble", },
    { Sort::selection, "selection", },
    { Sort::insertion, "insertion", },
    { Sort::merge, "merge", },
    { Sort::quick, "quick", },
    { Sort::heap, "heap", },
    { Sort::counting, "counting", },
};
    
int main() {
    
    // 멀티플레이에서 같은 랜덤값 공유하기 위해서는 시드값 공유
    // 흐르는 시간은 매번 다르기 때문에 시드값으로 훌륭함
    int seed = time(NULL);
    srand(seed);
 
    // 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
    int num = 'Z' - 'A' + 1;
    Data* data = new Data[num];
     for(int i=0; i<num; i++)
    {
        Data* d = &data[i];
        d->name[0] = 'A' + i;
        d->name[1] = 0;
        d->score = 1 + rand() % 100;
    }
    
    Data* tmp = new Data[num];
    
    // 정렬별 걸리는 시간 측정
    for(int i=0; i<7; i++)
    {
        memcpy(tmp, data, sizeof(Data) * num);
        
        SortInfo* si = &sortInfo[i];
        clock_t start = clock();
        si->method(tmp, num);
        clock_t end = clock();
        si->takeTime = (double)(end - start) / CLOCKS_PER_SEC;
    }
    
    for(int i=0; i<6; i++)
    {
        for(int j=1+i; j<7; j++)
        {
            if( sortInfo[i].takeTime > sortInfo[j].takeTime )
            {
                SortInfo t = sortInfo[i];
                sortInfo[i] = sortInfo[j];
                sortInfo[j] = t;
            }
        }
    }
    
    for(int i=0; i<7; i++)
    {
        SortInfo* si = &sortInfo[i];
        printf("No.%d, Sort(%s) takeTime(%f초)\n", 
            1 + i, si->name, si->takeTime);
    }
    
    delete tmp;
    delete data;
 
    return 0;
}
 
void Sort::bubble(Data* d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k-i; j++) {
            if(d[j].score > d[j+1].score) {
                Data t = d[j];
                d[j] = d[j+1];
                d[j+1] = t;
            }
        }
    }
}
 
void Sort::selection(Data* d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(d[j].score < d[min].score)
                min = j;
        }
 
        Data t = d[i];
        d[i] = d[min];
        d[min] = t;
    }
}
 
void Sort::insertion(Data* d, int n) {
    Data key;
    for(int i = 1; i < n; i++) {
        key = d[i];
        int j = i - 1;
 
        while(j >= 0 && d[j].score > key.score) {
            d[j+1] = d[j];
            j--;
        }
 
        d[j+1] = key;
    }
}
 
void Sort::merge(Data* d, int n) {
    bubble(d, n);// 별도 구현
}
 
void Sort::quick(Data* d, int n) {
    bubble(d, n);// 별도 구현
}
 
void Sort::heap(Data* d, int n){
    bubble(d, n);// 별도 구현
}
 
void Sort::counting(Data* d, int n) {
    bubble(d, n);// 별도 구현
}
 
Colored by Color Scripter

cs

4. 값을 Swap 속도 향상

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

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
 
// 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
struct Data {
    char name[2];
    int score;
};
 
struct Sort {
    static void bubble(Data** d, int n);
    static void selection(Data** d, int n);
    static void insertion(Data** d, int n);
    static void merge(Data** d, int n);
    static void quick(Data** d, int n);
    static void heap(Data** d, int n);
    static void counting(Data** d, int n);
};
 
typedef void (*Method)(Data** d, int n);
 
struct SortInfo {
    Method method;
    const char* name;
    double takeTime;
};
 
SortInfo sortInfo[] = {
    { Sort::bubble, "bubble", },
    { Sort::selection, "selection", },
    { Sort::insertion, "insertion", },
    { Sort::merge, "merge", },
    { Sort::quick, "quick", },
    { Sort::heap, "heap", },
    { Sort::counting, "counting", },
};
    
int main() {
    
    // 멀티플레이에서 같은 랜덤값 공유하기 위해서는 시드값 공유
    // 흐르는 시간은 매번 다르기 때문에 시드값으로 훌륭함
    int seed = time(NULL);
    srand(seed);
 
    // 이름은A에서Z까지이며,각이름별1점에서100점까지랜덤하게점수입력
    int num = 'Z' - 'A' + 1;
    Data* _data = new Data[num];
    Data** data = new Data*[num];
     for(int i=0; i<num; i++)
    {
        Data* d = &_data[i];
        data[i] = d;
        d->name[0] = 'A' + i;
        d->name[1] = 0;
        d->score = 1 + rand() % 100;
    }
    
    Data** tmp = new Data*[num];
    
    // 정렬별 걸리는 시간 측정
    for(int i=0; i<7; i++)
    {
        memcpy(tmp, data, sizeof(Data*) * num);
        
        SortInfo* si = &sortInfo[i];
        clock_t start = clock();
        si->method(tmp, num);
        clock_t end = clock();
        si->takeTime = (double)(end - start) / CLOCKS_PER_SEC;
    }
    
    for(int i=0; i<6; i++)
    {
        for(int j=1+i; j<7; j++)
        {
            if( sortInfo[i].takeTime > sortInfo[j].takeTime )
            {
                SortInfo t = sortInfo[i];
                sortInfo[i] = sortInfo[j];
                sortInfo[j] = t;
            }
        }
    }
    
    for(int i=0; i<7; i++)
    {
        SortInfo* si = &sortInfo[i];
        printf("No.%d, Sort(%s) takeTime(%f초)\n", 
            1 + i, si->name, si->takeTime);
    }
    
    delete tmp;
    delete data;
    delete _data;
 
    return 0;
}
 
void Sort::bubble(Data** d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k-i; j++) {
            if(d[j]->score > d[j+1]->score) {
                Data* t = d[j];
                d[j] = d[j+1];
                d[j+1] = t;
            }
        }
    }
}
 
void Sort::selection(Data** d, int n) {
    int k = n-1;
    for(int i = 0; i < k; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(d[j]->score < d[min]->score)
                min = j;
        }
 
        Data* t = d[i];
        d[i] = d[min];
        d[min] = t;
    }
}
 
void Sort::insertion(Data** d, int n) {
    Data* key;
    for(int i = 1; i < n; i++) {
        key = d[i];
        int j = i - 1;
 
        while(j >= 0 && d[j]->score > key->score) {
            d[j+1] = d[j];
            j--;
        }
 
        d[j+1] = key;
    }
}
 
void Sort::merge(Data** d, int n) {
    bubble(d, n);// 별도 구현
}
 
void Sort::quick(Data** d, int n) {
    bubble(d, n);// 별도 구현
}
 
void Sort::heap(Data** d, int n){
    bubble(d, n);// 별도 구현
}
 
void Sort::counting(Data** d, int n) {
    bubble(d, n);// 별도 구현
}
 
Colored by Color Scripter

cs

5. 정렬함수에 전달하는 타입(Data, SortInfo)때문에, 74라인 정렬 코드가 중복되었다.

2강에서 Sort을 타입과 상관없이 구현하여, 게임에서 유용하게 사용할 수 있는 방법을 찾자.

'[DSU] 게임알고리즘' 카테고리의 다른 글

[게임알고리즘] 2-1강 정렬 다듬기 최종 (0)	2026.03.13
[게임알고리즘] 1-5강 함수포인터 대응 (0)	2026.03.13
[게임알고리즘] 1-3강 최소값, 최대값 구하기3 + 정렬 (0)	2026.03.13
[게임알고리즘] 1-2강 최소값, 최대값 구하기2 (0)	2026.03.13
[게임알고리즘] 1-1강 최소값, 최대값 구하기1 (0)	2026.03.12

ABOUT ME

개발자의 일상 개발자의 일상

'[DSU] 게임알고리즘' 카테고리의 다른 글

티스토리툴바

ABOUT ME

'[DSU] 게임알고리즘' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바