Doputer

선택 정렬 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

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

반응형

'알고리즘' 카테고리의 다른 글

메모이제이션이란?📄  (0) 2020.10.07
시간 복잡도 가시적으로 확인해보기👀  (0) 2020.10.01
선택 정렬🧺  (0) 2020.10.01
칵테일 셰이커 정렬🧺  (0) 2020.09.30
거품 정렬🧺  (0) 2020.09.30

이 글의 태그

블로그의 정보

Doputer

#김도현

활동하기