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