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