比較次數中位數quicksort

Question

如何計算中位數快速排序中的比較次數？我必須在哪裏增加計數器來計算這個值？

void my_swap(vector<int>&vect, int dex1, int dex2) { 
    int temp = vect[dex1]; 
    vect[dex1] = vect[dex2]; 
    vect[dex2] = temp; 
} 
int find_median(vector<int>&vect, int p, int r) { 
    int center = (p + r)/2; 
    if (vect[p] > vect[center]) 
     my_swap(vect, p, center); 
    if (vect[p] > vect[r]) 
     my_swap(vect, p, r); 
    if (vect[center] > vect[r]) 
     my_swap(vect, center, r); 
    my_swap(vect, center, r - 1); 
    return vect[r - 1]; 
} 
void standart_sort(vector<int>&vect, int p, int r) { 
    if (r - p + 1 <= 1){ 
     return; 
    } 
    if (r - p + 1 == 2) { 
     if (vect[p] > vect[r]){ 
     my_swap(vect, p, r); 
     } 
     return; 
    } else { 
     if (vect[p] > vect[r - 1]){ 
     my_swap(vect, p, r - 1); 
     } 
     if (vect[p] > vect[r]){ 
     my_swap(vect, p, r); 
     } 
     if (vect[r - 1] > vect[r]){ 
     my_swap(vect, r - 1, r); 
     } 
    } 
} 
int partition_for_median(vector<int>&vect, int p, int r, double pivot) { 
    double x = pivot; 
    int i = p - 1; 
    for(int j = p; j <= r - 1; j++) 
    { 
     counter++; //pasted here 
     if(vect[j] <= x) 
     { 
     i++; 
     my_swap(vect, i, j); 
     } 
    } 
    my_swap(vect, i + 1, r); 
    return i; 
} 
void quick_sort_median(vector<int>&vect, int p, int r) { 
    if (r - p + 1 <= 3){ 
     counter2++; 
     standart_sort(vect, p, r); 
    } 
    else { 
     double median = find_median(vect, p, r); 
     int partition = partition_for_median(vect, p, r, median); 
     quick_sort_median(vect, p, partition - 1); 
     quick_sort_median(vect, partition + 1, r); 
    } 
} 

例如這個數組{3,7,5,1,9,6,4,10,8,2}中有25比較，但我怎麼計算出：我下面正中快速排序的代碼？

Answer 1

您可以使用自定義比較函數進行常規整數比較，但也可以增加全局計數器。一個類似的想法是用自己的比較函數在自定義類中包裝int，做類似的事情。這個類將有一個靜態計數器。

更危險的方法是直接在你的代碼中進行檢測。在您的代碼中查找發生比較的每個地方並增加一個計數器。