Selection Sorting의 시간 측정

 

Insertion Sorting에 이어 이번에는 Selection Sorting의 시간을 측정해 보았다.

 

 

 

이번에도 마찬가지로 1,000,000개의 랜덤한 숫자를 생성한 뒤 Selection Sorting을 이용하여 정렬하고 시간을 측정해 보았다.

 

측정된 시간은 1772.119초, 약 29분 53초가 소요되었다.

 

역시 정렬되기 전 숫자들은 before.txt 파일에, 정렬된 후의 숫자들은 after.txt에 저장하고 제대로 정렬이 되었는지 또한 확인해 보았다.

 

 

 

 

 

 

제대로 정렬된 모습을 볼 수 있었다.

 

 

같은 1,000,000개의 숫자를 정렬 할 때 Insertion Sorting과 비교해 본다면 정렬해야 할 숫자의 양이 많아질 때는 

 

Selection Sorting이 비교적 느린 속도를 보여주었다.

 

 

 

그래프에서 보는 것 처럼 일정 범위내에서는 비슷한 속도를 보이지만 연산량이 많아질수록 Selection Sorting의 속도가

 

더 오래 걸리는 모습을 확인할 수 있었다.

 

 

 

소스코드

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define arrSize 100000

int main(void)
{
	//int arr[arrSize];
	
	int cnt=0, i=0, j=0, k=0;
	int temp;
	FILE *fp;
	FILE *fp_out;
	clock_t chktime;

	// arrSize 만큼 메모리를 할당한다. (4byte integer 형 배열)
	int* arr = (int*)malloc(sizeof(int)*arrSize);
	if(arr==NULL)
	{
		printf("메모리 할당 실패\n");
		exit(1);
	}

	srand(time(NULL));

	fp = fopen("before.txt","w");
	fp_out = fopen("after.txt","w");

	
	printf("0~%d 까지의 랜덤값 생성 시작 --- OK\n",arrSize);
	// 랜덤값 생성
	for(cnt=0;cnt<arrSize;cnt++)
	{
		arr[cnt] = rand()%arrSize+1; // 0~arrSize 범위의 랜덤값 생성후 배열에 저장
		fprintf(fp,"%d ",arr[cnt]); // 생성된 랜덤값을 파일에 생성
	} 
	// 랜덤값을 배열에 저장과 함께 파일에도 저장한다.
	
	printf("0~%d 까지의 랜덤값 파일 저장 --- OK\n",arrSize);
	

	// Selection Sort 사용

	printf("Sorting 시작 --- OK\n");
	chktime = clock(); // 시작 시간 저장

	for(i=0;i<arrSize;i++)
	{
		j=i;
		for(k=i+1;k<arrSize;k++)
		{
			if(arr[k] < arr[j])
			{
				j = k;
			}
		}
		
		temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}

	printf("Sorting 종료 --- OK\n");
	chktime = clock() - chktime; // 종료시간저장

	// Sorting 이후의 값을 저장

	for(cnt=0;cnt<arrSize;cnt++)
	{
		fprintf(fp_out,"%d ",arr[cnt]); // 생성된 랜덤값을 파일에 생성
	} 
	printf("Sorting 이후 값 저장 --- OK\n");
	printf("Sorting 수행시간 : %f\n",(double)chktime/CLOCKS_PER_SEC);


	
	free(arr); // 할당되었던 메모리를 free 시킨다.
	
	fclose(fp);
	fclose(fp_out);
	// 파일을 close 시켜준다.

	return 0;
}