带保护的C.Insertion排序

Question

我已经解决了这个问题并且修正了一些.really..now图看起来不一样

请告诉我这个程序是否正常工作?你可以在上面的图片中看到结果。如果你发现任何错误(如果有错误的话，当然……)/我只是不确定掉期和补偿的平均数量是否计算正确。我认为这样做应该少一些，但是从经典的插入排序中获得的数据不是很多different.Maybe，这就是为什么我要问的原因。

先谢谢大家

 #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    

    
    int main(int argc, char *argv[]) {
    
        FILE *f=fopen("stat18.csv","w");
        int n=100;
        int i,s;
        while (n<=10000){
        int st=0;
        for (s=0;s<5;s++)
        {
            int *a;
            a=(int *)malloc(n*sizeof(int));
            srand(time(NULL));
            int k;
            for (k=0;k<n;k++)
            {
                *(a+k)=rand()%50;
            }
            int j,comps,swaps;
            swaps=0;
            comps=0;
        int rem = a[0];
        a[0] = -1;
        
        for( i = 2, j; i < n; i++)
        {
            int x = a[i];
            j = i;
            while(j > 1 && a[j-1] > x)
            {
                comps += 2;
                swaps++;
                a[j] = a[j-1];
                j--;
            }
            comps += 2;
            a[j] = x;
        }
        a[0] = rem;
        for(i = 0; i < n-1; i++)
        {
            if(a[i] > a[i+1])
            {
                comps++;
                swaps++;
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
            comps++;
            i++;
        }
        st+=swaps + comps;  
        free(a);
    }
            
        st=st/5;
        fprintf(f,"%d ; %d\n", n , st);
        if (n<1000){
            n+=100;}
        else {n+=1000;} 
        }
        fclose(f);
        return 0;
    }

Answer 1

随机播种

srand(time(NULL));

您可以将其称为循环(实际上是两个循环)。但问题是，time返回自任意历史时间点(1970年1月1日午夜)以来的当前秒数。在循环中的大部分时间，这将是相同的数字。所以你们播种的数字是一样的。但偶尔你会转到下一秒。

您应该创建一个变量

    time_t invocation_time = time(NULL);

然后你就可以用

        srand(invocation_time);

或者把种子调用移到循环之外。

如果您希望始终以相同的数字种子，那么您将创建这个变量，这样每次都会得到相同的“随机”序列。您甚至可以将值设置为固定的值，而不是当前的时间。我只是使用了当前的时间，因为这是你一直在使用的，我没有特别的理由更喜欢不同的价值。通过创建变量，您可以确保每次都使用相同的值进行播种，并获得相同的数字序列。你有时不会重复，有时也不会，就像你现在做的那样。

如果每次都想要一个不同的序列，那么每次调用程序时，只需添加一次随机性即可。对srand的反复调用使事情变得不那么随意，而不是更多。只有当您想要重复原来的结果时，才会这样做。坦率地说，如果这是您想要的，那么只生成一次数据并为每次迭代创建一个副本可能会更容易。

在程序开始时调用srand是更典型的方法。如果希望以某种方式使这些值可重复使用，则可以使用相同的值多次调用它。你现在所做的这两件事都不是。它既不是随机的，也不是可重复的。它有时重复，有时是伪随机序列。这在某种程度上是不可预测的，尽管可能会有一些模式。

我认为，在这种情况下，您想要的是在程序开始时播种一次，所以每次都在a中获得不同的值。但这确实取决于你到底想要测试什么。

可读性

\*(a+k)=rand()%50;

更常见的是这样写

            a[k] = rand() % 50;

现在，我们可以很容易地看到，您正在执行数组取消引用。这可能会对性能产生影响，这也是可以想象的。因为迭代数组是一件经常要做的事情，而且可能是优化的。而指针加法则比较少见，而且可能不是，即使实际上是相同的。但我仍然认为，用这种方式编写代码的主要原因是，人们更容易阅读您的代码来查看正在发生的事情。

您还会注意到，我添加了空格。这也使人们更容易看到什么东西在一起，什么是不同的。编译器将在标记化期间删除这一点，因此它会对可执行文件产生影响。但是对于源代码，它使阅读代码的人更容易理解它在做什么。

一致压痕

类似地，如果始终在块内缩进并在块结束时减少缩进，将更容易读取代码。这使得查看代码从何处开始和结束变得更加容易。

计数

现在来谈谈你实际问的问题。

for( i = 2, j; i < n; i++) { int x = a[i]; j = i; while(j > 1 && a[j-1] > x) { comps += 2; swaps++; a[j] = a[j-1]; j--; } comps += 2; a[j] = x; }

这是否正确地计算比较取决于您想要计算的是什么。

您没有计算在外部循环的每一次迭代中所做的比较i < n。我通常会认为这是你应该衡量的东西。

您正在计算两次内部循环失败的比较，即使只做了一次。也就是说，当j等于1时，您可以计算两个比较，即使短路只做j > 1而不是a[j-1] > x。也许你想数一下，好像短路没有发生一样。

就掉期而言，你也不算

int x = a[i];

或

a[j] = x;

但你在数每一个

a[j] = a[j-1];

什么是交换？如果这是一个作业，那么你应该数前两个。如果这是一个交换，您不应该计算最后一个，因为它不是交换。在那个循环中，你没有做任何“交换”。你在移动一块记忆。

请注意，我实际上所称的交换涉及三个分配(虽然其中很可能只有两个内存，因为其中一个可以保存在寄存器中)。因此，如果您对插入排序的改进是您所做的任务较少，那么您正在计算错误的事情。你应该清点任务，而不是交换。

for(i = 0; i < n-1; i++) { if(a[i] > a[i+1]) { comps++; swaps++; int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } comps++; i++; }

比较

我很难理解您认为什么是“经典”插入排序和您的修订是什么。如果您使用函数，这将更容易理解。然后，您可以用相同的数据调用每个数据并比较这些结果。对于那些阅读您的代码的人，我们可以看到这两个函数之间有什么不同。

这也会在测试设置和排序之间造成更多的分离。事实上，这些东西几乎是一起运行的。在什么是设置和什么是排序之间没有明确的界限。如果您的排序完全是在功能，那么它将更清楚。函数之外的内容是设置的。里面的东西在分类。

如果我们能够看到经典版本和修订版的结果，也会更容易。也许他们正在按预期显示数据。也许不是。如果没有经典版本，我很难看到你想比较什么。所以很难批评它。