알고리듬 성능비교 - Selection Sort 공부하는 것2016. 2. 27. 17:55
회사에서 요구하는 자격조건을 만족시키기 위해서 알고리듬을 공부해야한다.
공부하는 것은 싫어하지는 않지만, 그동안 내가 개발에 필요한 알고리듬은 천재적인 어떤 사람들이 만들어 놓은 Library를 이용하는 된다고 생각해서, 만들어 놓을 것을 잘 파악해서 내가 필요한 곳에 적절하게 사용하면 된다라고 생각해 왔고, 이러한 나의 생각은 지금까지도 변함이 없다.
그런데, 대학 생활 이후로는 크게 관심을 가지지 않았었는데, 다시 되집어 가면서 보아야 하는 상황이 나에게 왔다.
뭐, 그래도 즐기면서 하면되니까, 즐겁게 하련다.
아래의 코드는 "창의적 알고리듬"에 나오는 코드인데, 이를 조금 개선해 보았다.
코드는 다음과 같다. (코드는 짦기 때문에 따로 설명하지 않았다.)
[코드 1: 개선전]
#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
int n, S[100000];
void print_array()
{
for (int i = 0; i < n; i++)
{
printf("%d ", S[i]);
}
printf("\n");
}
void swap(int ai, int bi)
{
int t = S[ai];
S[ai] = S[bi];
S[bi] = t;
}
void selection_sort(void)
{
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (S[i] > S[j])
{
swap(i, j);
}
}
}
}
void selection_sort(void)
{
int idx = 0;
for (int i = 0; i < n; i++)
{
idx = i;
for (int j = idx + 1; j < n; j++)
{
if (S[idx] > S[j])
{
idx = j;
}
}
swap(idx, i);
}
}
int main()
{
srand(time(NULL));
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
S[i] = rand();
}
int start = clock();
selection_sort();
printf("result=%.3lf(sec)\n", (double)(clock() - start) / CLOCKS_PER_SEC);
print_array();
return 0;
}
아래 코드는 위 코드에서 swap함수를 호출하는 부분에서 비교 결과에 대한 array index값을 변수에 저장하여 swap()함수의 호출수를 줄였다. (아래 "코드 2"의 붉은 박스 부분 참조)
[코드 2: 개선후]
#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
int n, S[100000];
void print_array()
{
for (int i = 0; i < n; i++)
{
printf("%d ", S[i]);
}
printf("\n");
}
void swap(int ai, int bi)
{
int t = S[ai];
S[ai] = S[bi];
S[bi] = t;
}
void selection_sort2(void)
{
int idx = 0;
for (int i = 0; i < n; i++)
{
idx = i;
for (int j = idx + 1; j < n; j++)
{
if (S[idx] > S[j])
{
idx = j;
}
}
swap(idx, i);
}
}
int main()
{
srand(time(NULL));
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
S[i] = rand();
}
int start = clock();
selection_sort2();
printf("result=%.3lf(sec)\n", (double)(clock() - start) / CLOCKS_PER_SEC);
print_array();
return 0;
}
PC의 성능에 따라 다르겠지만, 코드를 실행하여, 100개에 대해서는 거의 같은 성능을 보이나, 1000개 이상에서는 성능차이가 보인다.
내 PC에서 1000개에 대해 소팅을 실행할 경우에,
"[코드 1]"은 0.013초가 결렸고, "[코드 2]"는 0.002초로 걸린다. 약 6배정도 "[코드 2]"가 빠른 결과를 가져온다고 볼수 있다.
'공부하는 것' 카테고리의 다른 글
| 요즘 내가 공부하는 것 (1) | 2019.06.07 |
|---|---|
| Visual Studio Code 1.0 정식 Released (2) | 2016.04.16 |
| Byte and Bit에 대해서... (0) | 2009.10.20 |
| GRails 공부 자료들... (0) | 2009.10.04 |
| Silverlight 3 Released (0) | 2009.07.11 |
