計算比較的數量，並在快速排序中移動C++

Question

我有這個任務來開發一個程序，實現快速排序算法與數組中的第一個元素作爲樞軸值。我已經設法通過使用數組中的20個元素來進行排序。

現在，我想計算比較的次數和在排序過程中發生的移動。我已經試過這段代碼，但輸出結果看起來不正確。比較和移動反覆保持打印輸出。我怎樣才能打印出移動和比較只有一次？希望有人願意幫助我。提前致謝。

代碼的比較和招式：

int partition1(int arr[], int start, int end) { //select first element as pivot value 
int pivot = arr[start]; 
int L = start + 1; 
int R = end; 
int temp = 0; 
int compr = 0; 
int move = 0; 

while (true) { 
    while ((L < R) && (arr[R] >= pivot)) { //bringing R to the left 
     --R; 
     compr++; 
    } 
    while ((L < R) && (arr[L] < pivot)) { //bringing R to the right 
     ++L; 
     compr++; 
    } 
    if (L == R) { //If they coincide 
     break; 
    } 
    //swapping L and R 
    temp = arr[L]; 
    arr[L] = arr[R]; 
    arr[R] = temp; 
    move += 2; 
} 

cout << "Comparison : " << compr << endl; 
cout << "Moves : " << move << endl; 

if (pivot <= arr[L]) { //special case 
    return start; 
} 
else { 
    arr[start] = arr[L]; //real pivot 
    arr[L] = pivot; 
    return L; 
} } 

而這一次是快速排序功能：

void quickSort(int arr[], int start, int end) { 
int boundary; 
if (start < end) { 
    boundary = partition1(arr, start, end); 
    quickSort(arr, start, boundary - 1); 
    quickSort(arr, boundary + 1, end); 
} } 

Answer 1

最簡單的方法是定義compr和move爲全球變量（僅用於調試目的），然後在運行結束時打印值。

Answer 2

在你while ((L < R) && (arr[R] >= pivot))循環還有一個比較 - 如果條件爲false，這就是爲什麼你應該增加compr以前這兩個循環：

int partition1(int arr[], int start, int end, int & compr, int & move) { //select first element as pivot value 
int pivot = arr[start]; 
int L = start + 1; 
int R = end; 
int temp = 0; 
//int compr = 0; 
//int move = 0; 
while (true) { 
compr++; // !!! 
while ((L < R) && (arr[R] >= pivot)) { //bringing R to the left 
    --R; 
    compr++; 
} 
compr++; // !!! 
while ((L < R) && (arr[L] < pivot)) { //bringing R to the right 
    ++L; 
    compr++; 
} 
... // the same lines to the end of function partition1, except of printing compr and move 
} 

void quickSort(int arr[], int start, int end, int & compr, int & move) { 
int boundary; 
if (start < end) { 
    boundary = partition1(arr, start, end, compr, move); 
    quickSort(arr, start, boundary - 1, compr, move); 
    quickSort(arr, boundary + 1, end, compr, move); 
} } 

int main() { 
    int compr = 0; 
    int move = 0; 
    quickSort({ 3, 2, 4, 1 }, 0, 3, compr, move); 

    cout << "Total comparison : " << compr << endl; 
    cout << "Total moves : " << move << endl; 
}