計算快速排序中的比較次數

我有一個家庭作業，我需要使用三種分區策略實施快速排序並計算每個策略的比較次數。計算快速排序中的比較次數

爲了簡單起見，我們被要求在每次我們對長度爲m的數組進行遞歸調用時將m-1添加到計數中。

我的代碼總是返回一個負數，它不是一個整數溢出問題。
我用long long int，我仍然有它，並且沒有辦法增加比較的數量那麼多，所以我的計數方式出了問題。

我測試使用is_sorted 100000元素陣列上的代碼中調用我的實現之後，它通過了，所以排序是正確的
這裏是我的代碼：

long quick_sort (vector <int>& A, int l , int r){ 
    static long count = 0; 
    if (r<= l) 
     return 0; 

    //partition 
    int i = partition(A, l, r); 

    //quicksort left 
    int amount = (((i -1) -l) >= 0 ? 
          ((i-1) -l) : 
            0); 
    count += amount; 
    quick_sort (A,l, i-1); 

    //quicksort right 
    amount = ((r - (i +1)) >= 0 ? 
         (r - (i +1)) : 
            0); 
    count += amount; 
    quick_sort (A,i+1, r); 

    return count; 

}

來源

2014-10-27 Mhd.Tahawi

作爲一個建議：計算你做他們的比較，這是行'int i = partition（A，l，r）;'。更容易，更容易出錯。 – Deduplicator 2014-10-27 23:09:51

更改測試值保持正確的表情：

count += ((i-1)-l >= 0 ? (i-1)-l : 0) 
quick_sort (A,l, i-1);

和

count += (r-(i+1) >= 0 ? ... 
quick_sort (A,i+1, r);

來源

2014-10-27 23:04:26 2501

'（i-1） - l == i -1 - l' and'r - i - 1 == r - （i + 1）'，對吧？ – 2014-10-27 23:06:31

@ Mhd.Tahawi不一定。試試我的方式。 – 2501 2014-10-27 23:07:11

它工作！，儘管這是違反數學規律的。：D 你能解釋爲什麼這有效嗎？ – 2014-10-27 23:17:14

您的靜態變量可能未設置爲0，如果您期望它。使其成爲全局變量。

此外，爲什麼在進行遞歸調用而不是調用時進行這項工作？做一次而不是兩次會容易得多。

來源

2014-10-27 23:04:40

計算快速排序中的比較次數

回答

相關問題