Quicksort正確實施，但與一些額外的比較

我想拉我的Quicksort實施的最大限度。它在功能上是正確的，並具有規範形式，但我已經計算了一些多餘的比較。我用的第一個元素爲支點：Quicksort正確實施，但與一些額外的比較

#include <vector> 

using namespace std; 
using uint = unsigned int; 

uint PartitionSub(vector<uint>& inp, uint l, uint r, uint& numOfCmp); 

void QuickSort(vector<uint>& inp, uint l, uint r, uint& numOfCmp) 
{ 
    if (r - l < 2) 
     return; 

    uint newPivotIdx = PartitionSub(inp, l, r, numOfCmp); 

    QuickSort(inp, l, newPivotIdx, numOfCmp); 
    QuickSort(inp, newPivotIdx + 1, r, numOfCmp); 
} 

uint PartitionSub(vector<uint>& inp, uint l, uint r, uint& numOfCmp) 
{ 
    auto swap = [&inp](uint a, uint b) 
    { 
     uint buf = inp[a]; 
     inp[a] = inp[b]; 
     inp[b] = buf; 
    }; 

    //numOfCmp += r - l; // we can use this, but ++numOfCmp just before  
         // comparison is more clear 
    uint i = l + 1; 
    uint j = l + 1; 

    uint p = inp[l]; 

    for (; j <= r; j++) 
    { 
     ++numOfCmp; 
     if (inp[j] < p) 
     { 
      if (i != j) 
       swap(i, j); 
      i++; 
     } 
    } 

    uint newPivotIdx = i - 1; 
    swap(l, newPivotIdx); 
    return newPivotIdx; 
}

給定輸入：3,9,8,4,6,10,2,5,7,1只需要25比較，但它27。我已經調試了三天，沒有線索。如果你們看到任何應該進行優化的地方比較少，請給我一些指導？據我瞭解，這是由於一個多餘的遞歸通道，因爲分區子程序和它的計數正確實施。

來源

2016-07-25 Floating Point

當'i == j'時不要比較？ – Arkadiy

我可能已經發現問題：

QuickSort(inp, l, newPivotIdx, numOfCmp); 
QuickSort(inp, newPivotIdx + 1, r, numOfCmp);

你並不需要在遞歸的轉動部件;我們知道它處於正確的位置。更改第一行

QuickSort(inp, l, newPivotIdx-1, numOfCmp);

您還沒有表現出任何調試輸出，如打印參數的函數入口痕跡，我怕我沒有時間去做自己現在。我希望這恰好是問題所在。

來源

2016-07-25 17:24:04 Prune

newPivotIdx被作爲高低邊界傳遞給遞歸的第一和第二分支，所以它與問題無關，無論如何感謝您的反饋。 –

Quicksort正確實施，但與一些額外的比較

回答

相關問題