计算比较的数量，并在快速排序中移动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; 
}