计算比较数和QuickSort C 中的移动

Question

我有这个分配来开发一个程序，该程序以数组中的第一个元素作为枢轴值来实现QuickSort算法。我已经设法通过在数组中使用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

在您的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;
}

Answer 2

最简单的方法是将 compr和 move定义为 global 变量（仅用于调试目的），然后在运行结束时打印值。