티스토리 뷰

C/C++

퀵 소팅 알고리즘

긴자손 2010.10.15 16:45

void quick_sort(int list[], int left, int right)
 {  
   if(left<right){     
      int q=partition(list, left, right);
      quick_sort(list, left, q-1);   
      quick_sort(list, q+1, right);  
    }
 }



최상의 경우:
거의 균등한 리스트로 분할되는 경우
패스 수: log2n
2->1
4->2
8->3

n->log2n
각 패스안에서의 비교횟수: n
총비교횟수: n log2n
총이동횟수: 비교횟수에 비하여 무시가능

댓글
댓글쓰기 폼
공지사항
Total
16,167
Today
0
Yesterday
1
«   2019/10   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
글 보관함