선택 정렬 vs 삽입 정렬 비교⏱

비교 방법

1. 각각 1000, 10000, 100000 크기의 배열 A, B에 0 ~ 999 사이의 난수를 채운다. (단, 동일한 난수로 채운다.)

2. 정렬 안된 상태, 정렬된 상태, 역순 정렬된 상태에서 선택 정렬과 삽입 정렬을 하여 시간을 비교한다.

 

사용 코드

#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

	1000	10000	100000
Selection sort	0.00131280sec	0.09303190sec	9.10471170sec
Insertion sort	0.00068790sec	0.04695960sec	4.57803530sec

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

 

2) Sort

	1000	10000	100000
Selection sort	0.00091760sec	0.09243670sec	9.11272040sec
Insertion sort	0.00000290sec	0.00002820sec	0.00027650sec

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

 

3) Reverse sort

	1000	10000	100000
Selection sort	0.00095050sec	0.09835080sec	8.93048030sec
Insertion sort	0.00097610sec	0.09260770sec	9.19390620sec

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