Quicksort korrekte Implementierung, aber mit einigen zusätzlichen Vergleichen

Question

Ich versuche, das Maximum aus meiner Quicksort-Implementierung herauszuholen. Es ist funktional korrekt und hat kanonische Form, aber ich habe einige überflüssige Vergleiche gezählt. Ich benutze das erste Element als Drehpunkt:

#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; 
} 

der Eingang Gegeben: 3,9,8,4,6,10,2,5,7,1 nur 25 Vergleiche erforderlich sind, aber es hat 27. Ich habe das drei Tage lang getestet und habe keine Hinweise. Wenn Sie irgendwelche Orte sehen, die im Sinne von weniger Vergleichen optimiert werden sollten, könnten Sie mir bitte eine Wegbeschreibung geben? Wie ich es verstehe, liegt das an einem redundanten Rekursion-Durchlauf, da das Partitions-Unterprogramm und das darin enthaltene Zählen korrekt implementiert sind.

Answer 1

ich das Problem entdeckt haben kann:

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

Sie brauchen nicht das Schwenkelement in der Rekursion aufzunehmen; wir wissen, dass es in der richtigen Position ist. Ändern Sie diesen ersten Zeile

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

Sie keine Debug-Ausgabe angezeigt haben, wie eine Spur von Druck Argumente auf Funktion Eintrag, und ich fürchte, ich keine Zeit, es selbst zu tun haben, jetzt zu tun. Ich hoffe, dass dies das Problem ist.