时间戳

首页 > 解决方案 > 如何打印出 QuickSort 切换和检查的次数？

c++ - 如何打印出 QuickSort 切换和检查的次数？

问题描述

我有这个任务，我必须对快速排序算法进行研究，并且我必须测量该算法检查数字（if 语句）并切换它们的时间。之后我需要打印出 2 个变量来显示检查和切换数字的次数。我认为我遇到了问题，因为我使用的是递归函数，但我想不出更好的方法来编写代码。

void quickSort(int* arr, int low, int high, int checks, int switches){

    switches++;
    int i = low;
    int j = high;
    int temp;
    int pivot = arr[(i + j) / 2];
    checks++;
    while (i <= j)
    {
        checks++;


        while (arr[i] < pivot)
            i++;

        checks++;


        while (arr[j] > pivot)
            j--;
        checks++;


        if (i <= j)
        {

            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    checks++;

    if (j > low) {
        quickSort(arr, low, j, checks, switches);
    }
    checks++;

    if (i < high) {
        quickSort(arr, i, high, checks, switches);
    }
        cout << checks<<" "<<switches << endl;
}

我在两个 if 之后都打印了检查和开关变量，但是数字被打印了几次（如果数组很大，例如 arr[400] 这些数字会被打印很多次）。我试图使快速排序函数成为一个 INT 函数并将这些变量返回给 main，然后将它们打印出来，但我的尝试没有成功。我还尝试编写另一个 if 语句if(j< low && i>high) {cout << checks<<" "<<switches << endl;}，但它不会打印。

任何关于如何改进我的代码的帮助或有用信息都将受到赞赏。

先感谢您。

标签： c++algorithmquicksort

解决方案

  1. Makechecks和switches全局变量。
while (arr[i] < pivot)
    i++;
    checks++;

这不应该是

while (arr[i] < pivot) {
    i++;
    checks++;
} 
checks++;

感谢@NateEldridge 指出最后一个终止循环的检查也必须被计算在内，因此checks++在最后。

3.

if (i <= j)
        {

            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }

在此代码中，您正在交换arr[i]，arr[j]因此您应该更新switches.

  1. 在某些地方，您checks似乎switches无缘无故地更新；看来你应该只更新and checks。arr[i] < pivotarr[j] > pivot

推荐阅读