c++ - 计算快速排序 C++ 中的比较和移动次数

Question

我的任务是开发一个程序，该程序以数组中的第一个元素作为枢轴值来实现快速排序算法。我已经设法通过在数组中使用 20 个元素来进行排序。

现在，我想计算排序过程中比较和移动的次数。我已经尝试过此代码，但输出似乎不正确。比较和 Action 不断打印出来。我怎样才能只打印一次 Action 和比较？希望有人愿意帮助我。提前致谢。

比较和移动代码:

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