c - 冒泡排序与插入排序运行时

Question

我正在尝试编写一个程序来计算冒泡排序与插入排序的运行时间。它接受两个输入:元素数量和元素，并计算它们的运行时间。这是我到目前为止所拥有的，但两个分拣机的打印时间相同。

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

int bubblesort(int a[], int n);
int insertionsort(int a[], int n);

int main()
{
    int s,temp,i,j,comparisons,a[20];
    float function_time;
    clock_t start;
    clock_t end;
    printf("Enter total numbers of elements: ");
    scanf("%d",&s);
    printf("Enter %d elements: ",s);

    for(i=0;i<s;i++)
    scanf("%d",&a[i]);

  //Bubble sorting algorithm

    for(i=s-2;i>=0;i--)
    {
        for(j=0;j<=i;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];

                a[j]=a[j+1];

                a[j+1]=temp;
            }
        }
    }

    for(i=0;i<s;i++)
    a[i]= rand()%10000;

    start = clock();    
    comparisons= bubblesort(a, s);
    end = clock();
    function_time = (float)(end)/(CLOCKS_PER_SEC);  // Time in seconds
    printf("\nTime for Bubble Sort is %f microseconds\n ", function_time);

    // Insertion sorting algorithm

    for(i=1;i<s;i++)
    {
        temp=a[i];
        j=i-1;
        while((temp<a[j])&&(j>=0))
        {
            a[j+1]=a[j];
            j=j-1;
        }
        a[j+1]=temp;
    }

    for(i=0;i<s;i++)
    a[i]= rand()%10000;

    start = clock();    
    comparisons= insertionsort(a, s);
    end = clock();
    function_time = (float)(end)/(CLOCKS_PER_SEC);  // Time in seconds
    printf("\nTime for Insertion Sort is %f microseconds\n ", function_time);

    return 0;
}

int bubblesort(int a[], int n)
{
    bool swapped = false;
    int temp=0, counter=0;

    for (int j = n-1; j>0; j--)
    {
        swapped = false;
        for (int k = 0; k<j; k++) 
            {
                counter++;
                if (a[k+1] < a[k]) 
                {
                    temp= a[k];
                    a[k] = a[k+1];
                    a[k+1]= temp;
                    swapped = true;
                }
            }
        if (!swapped)
            break;
    }

return counter;
}

int insertionsort(int a[], int n)
{
    bool swapped = false;
    int temp=0, counter=0;
    for (int i=1; i<=n; i++)
    {    
        for (int s=i; s>0; s--)
        {
            counter++;
            if (a[s]<a[s-1])
            {
                temp=a[s-1];
                a[s-1]=a[s];
                a[s]=temp;
                swapped = true;
            } 
        }
        if (!swapped)
            break;
    }
return counter;
}

Answer 1

首先，你计算排序时间的方式是错误的:

function_time = (float)(end)/(CLOCKS_PER_SEC);

应该是:

function_time = (float)(end-start)/(CLOCKS_PER_SEC);

其次，尽管冒泡排序和插入排序都有O(n平方)的复杂度，但是所花费的时间应该有一些差异，它们不可能相同。如果问题仍然存在，您应该检查clock()函数的输出，它可能在您的系统中不起作用。

编辑:我发现您的代码允许用户手动输入元素。所以我猜你的数组只能比较小。对小尺寸数组进行排序只需要很少的时间，因此很难注意到差异。你应该让代码随机分配元素，这样你就可以生成大数组进行分析。