정렬 알고리즘의 C코드 구현과 성능 비교

 주어진 10,000개의 임의의 정수로 이루어진 배열을 크기 순서대로 정렬하는, 정렬 문제에 대해 버블 알고리즘(bubble algorithm)과 선택 알고리즘(selection algorithm)의 성능을 비교하였다.

 성능은 각각의 알고리즘이 실행되는데 소요되는 시간으로 측정하였다.

 본 글에서는 임의로 생성된 배열 1개에 대해서만 비교하였다. 통계적으로 엄밀하게 해보고 싶으신 분들은 (1)여러 랜덤 배열을 생성하여 (2) 본 실험을 반복 수행 하시고 (3) 통계 내보시길 바랍니다.

 

성능 예상

• 버블 알고리즘 : O(N²)
• 선택 알고리즘 : O(N²)

코드

#include string.h
#include stdlib.h
#include time.h

void swap(int *a, int *b){ // 
 // function to swap two elements of the array
  int dum;
  dum=*a;
  *a=*b;
  *b=dum;
}

int main(int argc, char **argv){
  clock_t s1, s2, e1, e2;  // 알고리즘 수행에 걸린 시간을 비교하기 위한 변수들
  const int n=1000; // 테스트를 위해 정렬할 array의 길이
  int test1; // bubble algorithm의 타겟 array
  int test2; // selection algorithm의 타겟 array
  for (int i=0; in; i++){ // 두 알고리즘으로 정렬할 array 생성
    test1=rand();
    test2=test1;
  }

/*
  printf("original list:\n"); // 정렬 이전의 array를 출력
  for (int i=0; in; i++){
    printf("%d\n",test1);
  }
*/


 // bubble algorithm 수행
  printf("sorted list by bubble:\n");
  s1=clock();
  for (int j=0; jn; j++){
    for (int i=0; in-1; i++){
      if (test1test1[i+1]){
        swap(test1+i,test1+i+1);
      }
    }
  }
  e1=clock();
  /*for (int i=0; in; i++){ // 정렬된 결과를 출력
    printf("%d\n",test1);
  }*/
  printf("past time: %lf\n\n",(float)(e1-s1)/CLOCKS_PER_SEC); // bubble 알고리즘의 소요 시간 출력
 
 // selection algorithm 수행
  printf("sorted list by selection:\n");
  s2=clock();
  int smallest_index;
  for (int i=0; in; i++){
    smallest_index=i;
    for (int j=i; jn; j++){
      if (test2[smallest_index]test2[j]){
        smallest_index=j;
      }
    }
    swap(test2+i, test2+smallest_index);
  }
  e2=clock();
  /*
  for (int i=0; in; i++){ // 정렬된 결과를 출력
    printf("%d\n",test2);
  }
  */
  printf("past time %lf\n\n",(float)(e2-s2)/CLOCKS_PER_SEC); // selection 알고리즘의 소요 시간 출력
}

결과

소요시간(초)

• 버블 알고리즘 : 0.106536 초
• 선택 알고리즘 : 0.028610 초

확실히, 선택 알고리즘이 보다 빨랐다. 하지만, N값을 증가시켜보면 두 소요시간의 차이가, 소요시간 크기에 비해 미미해지는 것을 볼 수 있다. 즉, 두 소요시간이 충분히 큰 N값에 대해서 수렴한다.