Doputer

선택 정렬과 삽입 정렬 비교

비교 방법

  1. 각각 1000, 10000, 100000 크기의 배열 A, B에 0 ~ 999 사이의 난수를 채운다. 단, 동일한 난수로 채운다.
  2. 정렬 안된 상태, 정렬된 상태, 역순 정렬된 상태에서 선택 정렬과 삽입 정렬을 하여 시간을 비교한다.

사용 코드

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;
}

결과

  1. Unsort
100010000100000
Selection sort0.00131280sec0.09303190sec9.10471170sec
Insertion sort0.00068790sec0.04695960sec4.57803530sec

정렬 안된 상태에서는 삽입 정렬이 선택 정렬보다 두 배 가까이 빠릅니다.

  1. Sort
100010000100000
Selection sort0.00091760sec0.09243670sec9.11272040sec
Insertion sort0.00000290sec0.00002820sec0.00027650sec

정렬된 상태에서는 삽입 정렬이 선택 정렬보다 압도적으로 빠릅니다.

  1. Reverse sort
100010000100000
Selection sort0.00095050sec0.09835080sec8.93048030sec
Insertion sort0.00097610sec0.09260770sec9.19390620sec

역순 정렬된 상태에서는 삽입 정렬과 선택 정렬이 비슷한 속도를 보입니다.