c++ - 跟踪排序中执行的比较

Question

我正在尝试跟踪为简单的 C++ 排序函数所做的比较的数量。

void sort(int arr[], int size)
{

int startScan, minIndex, minValue;

for (startScan = 0; startScan < (size - 1); startScan++)
{
    minIndex = startScan;
    minValue = arr[startScan];

    for (int index = startScan + 1; index < size; index++)
    {
        if (arr[index] < minValue)
        {
            minValue = arr[index];
            minIndex = index;
        }
    }
    arr[minIndex] = arr[startScan];
    arr[startScan] = minValue;
}



}

我正在研究我认为可能会返回比较次数的值，起初我认为比较次数可能会保存在 startScan 中。 .当然不是，start scan 只会hold ever hold maximum-1。这绝对不是进行比较的次数。

我想也许它会在变量索引中找到。所以我创建了int temp = index;因为我很懒，不想解决这个问题，但是当我返回 temp 的值时，果然它也只是 size-1。不知道为什么我期望有任何不同，但我想我会尝试。

然后我开始思考......我什至知道比较发生在哪里？

事实证明我不知道我是否这样做。我认为我所有的比较都发生在第二个 for 循环中， for (int index = startScan + 1; index < size; index++)即使那样真的只是if语句嵌套在里面。

任何时候 if语句运行，它正在比较某些东西。甜蜜，我想。所以我创建了int temp = 0;在我的函数顶部，打了一个 temp++在 if 语句中，并认为这肯定会给我比较的数量。

这次给了我一个鼓舞人心的数字。在对包含 13 个数字的随机列表进行排序时(随机，因为我选择了随机数)我的温度返回值 18。据我所知，这与我的任何其他数字都没有线性关系。

所以这是我真正的问题。这行得通吗？我的最终代码是否按照我的意愿执行，并且确实返回了比较次数？或者我只是发现了另一个任意数字，我碰巧比其他测试产生的其他数字更喜欢它。我不知道如何手动计算比较次数。我喜欢这个数字，但据我所知，它可能还差得远。

最终代码:

int sort(int arr[], int size)
{
int temp = 0;
int startScan, minIndex, minValue;

for (startScan = 0; startScan < (size - 1); startScan++)
{
    minIndex = startScan;
    minValue = arr[startScan];

    for (int index = startScan + 1; index < size; index++)
    {
        if (arr[index] < minValue)
        {
            minValue = arr[index];
            minIndex = index;
            temp++;
        }


    }
    arr[minIndex] = arr[startScan];
    arr[startScan] = minValue;
}

return temp; 


}

Answer 1

仅当数组值小于 minValue 时才增加计数器:

    if (arr[index] < minValue)
    {
        minValue = arr[index];
        minIndex = index;
        temp++;
    }

如果要统计arr[index] < minValue的个数你所做的比较，你应该将代码更改为:

    if (arr[index] < minValue)
    {
        minValue = arr[index];
        minIndex = index;
    }
    temp++;

也许给计数器一个更好的名字，counter怎么样？ ？ ;)

顺便说一句，以防万一你想将你的排序与 std::sort 进行比较你可以像这样计算它的比较次数:

#include <algorithm>
#include <iostream>

bool myCountingCompare(int a,int b){
    static int counter = 0;
    counter++;
    std::cout << "number of comparisons : " << counter << std::endl;
    return a > b;
}

int main() {
    int array[3] = {1,2,3};
    std::sort(&array[0],&array[3],myCountingCompare);
    return 0;
}