비교 방법
- 각각 1000, 10000, 100000 크기의 배열 A, B에 0 ~ 999 사이의 난수를 채운다. 단, 동일한 난수로 채운다.
- 정렬 안된 상태, 정렬된 상태, 역순 정렬된 상태에서 선택 정렬과 삽입 정렬을 하여 시간을 비교한다.
사용 코드
c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubble(int *L, int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (L[j] < L[j + 1])
swap(&L[j], &L[j + 1]);
}
void selection(int *L, int n) {
int *value = NULL;
for (int i = 0; i < n - 1; i++) {
value = &L[i];
for (int j = i + 1; j < n; j++)
if (*value > L[j])
value = &L[j];
if (L[i] > *value)
swap(&L[i], value);
}
}
void insertion(int *L, int n) {
int j, value;
for (int i = 1; i < n; i++) {
j = i - 1;
value = L[i];
while (j >= 0 && L[j] > value) {
L[j + 1] = L[j];
j--;
}
L[j + 1] = value;
}
}
void input(int *A, int *B, int n) {
int var;
for (int i = 0; i < n; i++) {
var = rand() % 1000;
A[i] = var;
B[i] = var;
}
}
int main(void) {
int *A = NULL;
int *B = NULL;
int n, opt;
LARGE_INTEGER ticksPerSec;
LARGE_INTEGER start, end, diff;
srand((unsigned)time(NULL));
while (1) {
printf("Input option(1: unsort, 2: sort, 3: reverse, 4: exit): ");
scanf("%d", &opt);
if (opt == 4)
break;
printf("Input data size: ");
scanf("%d", &n);
A = (int *)malloc(sizeof(int) * n);
B = (int *)malloc(sizeof(int) * n);
input(A, B, n);
if (opt == 2) {
selection(A, n);
selection(B, n);
}
else if (opt == 3) {
bubble(A, n);
bubble(B, n);
}
QueryPerformanceFrequency(&ticksPerSec);
QueryPerformanceCounter(&start);
selection(A, n);
QueryPerformanceCounter(&end);
diff.QuadPart = end.QuadPart - start.QuadPart;
printf("Selection sort: %.8fsec\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
QueryPerformanceFrequency(&ticksPerSec);
QueryPerformanceCounter(&start);
insertion(B, n);
QueryPerformanceCounter(&end);
diff.QuadPart = end.QuadPart - start.QuadPart;
printf("Insertion sort: %.8fsec\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
free(A);
free(B);
A = NULL;
B = NULL;
}
return 0;
}
c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubble(int *L, int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (L[j] < L[j + 1])
swap(&L[j], &L[j + 1]);
}
void selection(int *L, int n) {
int *value = NULL;
for (int i = 0; i < n - 1; i++) {
value = &L[i];
for (int j = i + 1; j < n; j++)
if (*value > L[j])
value = &L[j];
if (L[i] > *value)
swap(&L[i], value);
}
}
void insertion(int *L, int n) {
int j, value;
for (int i = 1; i < n; i++) {
j = i - 1;
value = L[i];
while (j >= 0 && L[j] > value) {
L[j + 1] = L[j];
j--;
}
L[j + 1] = value;
}
}
void input(int *A, int *B, int n) {
int var;
for (int i = 0; i < n; i++) {
var = rand() % 1000;
A[i] = var;
B[i] = var;
}
}
int main(void) {
int *A = NULL;
int *B = NULL;
int n, opt;
LARGE_INTEGER ticksPerSec;
LARGE_INTEGER start, end, diff;
srand((unsigned)time(NULL));
while (1) {
printf("Input option(1: unsort, 2: sort, 3: reverse, 4: exit): ");
scanf("%d", &opt);
if (opt == 4)
break;
printf("Input data size: ");
scanf("%d", &n);
A = (int *)malloc(sizeof(int) * n);
B = (int *)malloc(sizeof(int) * n);
input(A, B, n);
if (opt == 2) {
selection(A, n);
selection(B, n);
}
else if (opt == 3) {
bubble(A, n);
bubble(B, n);
}
QueryPerformanceFrequency(&ticksPerSec);
QueryPerformanceCounter(&start);
selection(A, n);
QueryPerformanceCounter(&end);
diff.QuadPart = end.QuadPart - start.QuadPart;
printf("Selection sort: %.8fsec\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
QueryPerformanceFrequency(&ticksPerSec);
QueryPerformanceCounter(&start);
insertion(B, n);
QueryPerformanceCounter(&end);
diff.QuadPart = end.QuadPart - start.QuadPart;
printf("Insertion sort: %.8fsec\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
free(A);
free(B);
A = NULL;
B = NULL;
}
return 0;
}
결과
- Unsort
1000 | 10000 | 100000 | |
---|---|---|---|
Selection sort | 0.00131280sec | 0.09303190sec | 9.10471170sec |
Insertion sort | 0.00068790sec | 0.04695960sec | 4.57803530sec |
정렬 안된 상태에서는 삽입 정렬이 선택 정렬보다 두 배 가까이 빠릅니다.
- Sort
1000 | 10000 | 100000 | |
---|---|---|---|
Selection sort | 0.00091760sec | 0.09243670sec | 9.11272040sec |
Insertion sort | 0.00000290sec | 0.00002820sec | 0.00027650sec |
정렬된 상태에서는 삽입 정렬이 선택 정렬보다 압도적으로 빠릅니다.
- Reverse sort
1000 | 10000 | 100000 | |
---|---|---|---|
Selection sort | 0.00095050sec | 0.09835080sec | 8.93048030sec |
Insertion sort | 0.00097610sec | 0.09260770sec | 9.19390620sec |
역순 정렬된 상태에서는 삽입 정렬과 선택 정렬이 비슷한 속도를 보입니다.