프로그래밍

정렬 알고리즘

흰앙큼호두과자 2010. 4. 19. 12:43

정렬 알고리즘 매 학기마다 새로운 걸 배웠었지만 정리해보니 다양합니다. ^^

각종 변형도 많이 있고 성능측정도 쉽지 않네요.

처음 성능 측정할 때는 윈도에서 Performance Query 찾아서 썼었는데 그냥 편하게 ClockTick 쓰는 게 나은 것도 같고…

기초적이고 쉬우면서도 알수록 어려운 듯합니다. ㅠㅠ

exchangeSort

   1: void exchangeSort(int a[], int n){
   2:   int i,j,temp;
   3:   for ( i= 0; i<n ; i++ ){
   4:     for ( j=i; j<n ; j++) {
   5:         if(a[i] > a[j] ) {
   6:           temp = a[i];
   7:           a[i] = a[j];
   8:             a[i] = temp;
   9:         }
  10:      }
  11:   }
  12: }

 

selectionSort

   1: void selectionSort(int *a, int n){
   2:     int i,j,k,temp;
   3:     for( i= 0; i< n ; i++){
   4:         j=i;
   5:         for( k=i+1;k<n;k++)
   6:             if(a[k] < a[j]) j=k;
   7:         temp = a[i]; a[i]=a[j]; a[j]=temp;
   8:     }
   9: }

 

insertionSort 시간복잡도

clip_image002[18]

   1: void insertion_sort ( int *a, int n ){
   2:     int i, j, temp;
   3:     for ( i = 1; i <= n; i++ ){
   4:         temp = a[ (j=i) ];
   5:         while ( --j >= 0 && temp < a[j] ) a[j+1] = a[j];
   6:         a[j+1] = temp;
   7:     }
   8: }

 

//

# 여기까지 평균 n^2

//

 

MergeSort 시간복잡도

W(n) = W(h)      +   W(m)     +  h+m-1

          U정렬시간   V정렬시간    합병시간

clip_image002[12]

clip_image004

   1: void mergeSort(int a[], int l, int h) {
   2:   int mid;
   3:   if (l < h) {
   4:     mid = (l + h) / 2;
   5:     mergeSort(a, l, mid);
   6:     mergeSort(a, mid+1, h);
   7:     merge(a, l, mid, h);
   8:   }
   9: }
  10:  
  11: void merge(int a[], int l, int m, int h) {
  12:   int b[h-l+1];
  13:   int i, left, right, buf;
  14:   left=l; right= m+1; buf=0;
  15:   while(left <= m && right <= h)
  16:     if (a[left] < a[right])
  17:       b[buf++] = a[left++];
  18:     else
  19:       b[buf++] = a[right++];
  20:   if (left > m)
  21:     for (i=right; i<=h; i++)
  22:       b[buf++] = a[i];
  23:   else
  24:     for (i=left; i<=m; i++)
  25:       b[buf++] = a[i];
  26:   for (i=l; i<=h; i++) {
  27:     a[i] = b[i-l];
  28:   }
  29: }

 

bubleSort

   1: void BubbleSort(int *a, int i, int l)
   2: {
   3:     int temp;
   4:     if(i == l){
   5:         return;
   6:     }
   7:     else{
   8:         if(a[i]>a[i+1]){
   9:             swap(a[i], a[i+1], temp);
  10:         }
  11:         BubbleSort(a, i+1, l);
  12:     }
  13:     BubbleSort(a, i, --l);
  14: }
  15:  
  16: void swap(int *x, int *y) {
  17:  int t;
  18:  t = *x; *x= *y; *y = t;
  19: }

 

Quick Sort 시간복잡도

T(n) = T(0)          +   T(n-1)             +  n-1

         왼쪽 정렬시간  오른쪽 정렬시간     분할시간

clip_image002[16]

clip_image004[6]

clip_image006[4]

clip_image008[4]

평균 시간복잡도

clip_image002[10]

필요 스택 공간(공간복잡도)

O(n) ~ O(log n)

   1: void quickSort(int a[], int l, int r) {
   2:  int m;
   3:  if (r > l) {
   4:   m = partition(a, l, r+1);
   5:   quickSort(a, l, m-1);
   6:   quickSort(a, m+1, r);
   7:  }
   8: }
   9:  
  10: int partition(int a[], int l, int r) {
  11:  int partElem, val;
  12:  partElem = l;
  13:  val = a[partElem];
  14:  do {
  15:   do {} while(a[++l] < val);
  16:   do {} while(a[--r] > val);
  17:   if (l<r) {
  18:    swap(&a[l], &a[r]);
  19:  
  20:   } else
  21:    break;
  22:  } while (1);
  23:  a[partElem] = a[r];
  24:  a[r] = val;
  25:  return r;
  26: }
  27:  
  28: void swap(int *x, int *y) {
  29:  int t;
  30:  t = *x; *x= *y; *y = t;
  31: }

 

기타 - 만들어보긴 했지만… 어디 저장해놨는지 못찾았음.

이진트리를 이용한 최대힙정렬

clip_image002[20]

라딕스 정렬

O(d(n+r))

반응형