독서 노트 의 빠 른 정렬 (2)

독서 노트 의 빠 른 정렬 (1) 에 있 는 코드 1 - 3 은 한 배열 에 대해 빠 른 정렬 을 하고 평균 비교 횟수 를 통계 하 는 데 사용 된다.비교 횟수 만 집계 하려 면 배열 의 실제 정렬 이 필요 없다.코드 1 - 4 는 요 소 를 정렬 하 는 '실제 조작' 을 제거 하고 프로그램 에서 각종 함수 호출 프레임 워 크 만 유지 합 니 다.

1 - 4 Quicksort 알고리즘 의 프레임 워 크 를 통계 만 하 는 것 으로 축소

 

  
  
  
  

   
   
   
   
void quicksort(int low,int high) 
   
   
   
   
{ 
   
   
   
   
    int m; 
   
   
   
   
    if( low >= high) 
   
   
   
   
    return ; 
   
   
   
   
    m = randint(low ,high); 
   
   
   
   
    comp += high -1; 
   
   
   
   
    quickcount(low ,high -1); 
   
   
   
   
    quickcount(m+1,high); 
   
   
   
   
} 
  
  
  
  

실제 프로그램 에서 배열 의 하 표 (low 와 high) 는 매우 중요 하지만 이 프레임 워 크 에 서 는 중요 하지 않 습 니 다. (우리 가 고려 하 는 것 은 비교 횟수 입 니 다) 따라서 배열 의 크기 를 나타 내 는 정수 n 으로 이 두 개의 하 표를 대체 할 수 있 습 니 다. 예 를 들 어 코드 1 - 5 와 같 습 니 다.

1 - 5 Quicksort 코드 프레임 워 크 에서 배열 크기 를 나타 내 는 매개 변 수 를 사용 합 니 다

 

  
  
  
  

   
   
   
   
void qc(int n) 
   
   
   
   
{ 
   
   
   
   
    int m; 
   
   
   
   
    if( n <= low) 
   
   
   
   
    return ; 
   
   
   
   
    m = randint(low ,n); 
   
   
   
   
    comp += n -1; 
   
   
   
   
    qc(m-1); 
   
   
   
   
    qc(n-m); 
   
   
   
   
} 
  
  
  
  

지금 은 이 과정 을 자 연 스 럽 게 비교 횟수 를 통계 하 는 함수 로 정리 할 수 있 습 니 다. 이 함 수 는 무 작위 Quicksort 알고리즘 에서 의 비교 횟수 를 말 합 니 다.1 - 6 이 함 수 를 드 렸 습 니 다.

1 - 6 Quicksort 프레임 워 크 를 하나의 함수 로 실현

 

  
  
  
  

   
   
   
   
int cc(int n) 
   
   
   
   
{ 
   
   
   
   
    int m; 
   
   
   
   
    if(n <= low )     
   
   
   
   
    return 0; 
   
   
   
   
    m = randint(low,n); 
   
   
   
   
    return n-1 + cc(m-1) + cc(n-m); 
   
   
   
   
}