Insertion Sorting의 시간 측정

 

삽입정렬, (Insertion Sorting)을 이용하여 1,000,000개의 랜덤한 숫자를 생성한 뒤 Insertion Sorting을 통해 정렬한뒤

 

시간을 측정해 보았다.

또한 정렬되기 전 랜덤하게 생성된 숫자들을 before.txt 라는 파일에 저장하고,

정렬이 완료된 숫자는 after.txt라는 파일에 저장하여 두 파일을 비교 해 보았다.

 

 

 

Sorting을 진행한 총 시간은 1059.978 sec 즉, 17분 6663초 정도가 소요 되었다.

 

 

 

 

before.txt파일과 after.txt 파일을 비교해 보면 정렬 또한 제대로 된 것을 확인 할 수 있다.

 

 

 

 

데이터의 양에 따른 Sorting 시간을 측정해 보았는데

 

 

 

일정 양을 넘어가면 Sorting 시간이 기하급수적으로 증가하는 모습을 볼 수 있었다.

 

 

다음 포스팅에는 Selection Sorting을 이용한 정렬 시간과 이에대한 결과로 Insertion Sorting과의 비교를 해 보도록 하겠다.

 

 

 

소스 코드

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

#define arrSize 500000

int main(void)
{
	//int arr[arrSize];
	
	int cnt=0, i=0;
	int temp, move_index;
	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);
	

	// Insertion Sort 사용

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

	for(i=1;i<arrSize;i++)
	{
		temp = arr[i];
		move_index=i-1;

		while(move_index >= 0 && arr[move_index] > temp)
		{
			arr[move_index+1] = arr[move_index];
			move_index--;
		}
		arr[move_index+1] = 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;
}