保持比较执行排序

我想跟踪一个简单的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举行认为值。当然不是，开始扫描只能保持最大尺寸-1。这绝对不是进行比较的次数。

我想也许它会在变量索引中找到。所以我创建了int temp = index;，因为我很懒，不想处理它，但是当我返回temp的值时，它也仅仅是size-1。不知道为什么我期望有什么不同，但我想我会尝试。

然后我开始考虑这个问题......我甚至知道比较在哪里发生？

原来我不知道我是否做。我想我所有的比较都发生在第二个循环中，即 for (int index = startScan + 1; index < size; index++)，甚至还有嵌套在里面的if声明。

无论何时if语句运行，它都会比较一些内容。 SWEET，我想。所以我在我的函数顶部创建了int temp = 0;，在if语句中打了一个temp++，并认为这肯定会给我一些比较结果。

这次给了我一个鼓舞人心的数字。当对随机列表中的13个数字进行排序时（我随机选择了随机数字），我的temp返回了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; 


}

来源

2016-05-31 Podo

每个循环也有每次迭代时间的比较。 – lcs

所以我想我的第一个循环会运行'大小-1'次，我的第二个循环也会运行'大小-1'次，然后我的if循环运行多次？ Addem都起来了吗？ – Podo

那么，当条件为真时，'temp'变量现在只会增加。当它是错误的时候也会发生比较。 – lcs

您提高柜台只有当数组值小于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; 
}

来源

2016-05-31 20:23:10 user463035818

好的，这是给我一个更大更合理的数字！ – Podo

保持比较执行排序

回答

相关问题