clock() 函数无法按预期使用排序函数

Question

我正在尝试编写一个程序来比较快速排序和插入排序函数所花费的时间，具体取决于数组中元素的数量。这是我想出的代码:

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


//prototypes of insertion sort and quick sort
int * naive_sort(int * );
void smarter_sort(int * sorted, int left, int right);

int main(void)
{
    int size;

    long naiveTime, smarterTime;
    clock_t time1, time2, time3, time4;
    //creating an array of all the array sizes to be tested
    int arraySizes[5] = {10, 100, 1000, 5000, 10000};
    //loop to go through all the array sizes in arraySize
    for(int z = 0; z<5; z++)
    {
        size = arraySizes[z];
        int unsorted[size];
        int * sortedNaive;
        int * sortedSmarter;

        //filling unsorted array with random variables
        for(int i = 0; i<size; i++)
            unsorted[i] = rand() %100000;


        time3 = clock();
        //call quick sort
        sortedSmarter = unsorted;
        smarter_sort(sortedSmarter, 0, size-1);
        time4 = clock();

        time1 = clock();
        //call insertion sort
        sortedNaive = naive_sort(unsorted);
        time2 = clock();




        naiveTime = (time2-time1)/CLOCKS_PER_SEC;
        smarterTime = (time4 - time3)/CLOCKS_PER_SEC;

        printf("Time taken for insertion sort with %d elements: %e \n", arraySizes[z], naiveTime);
        printf("Time taken for quick sort with %d elements:     %e \n", arraySizes[z], smarterTime);

}
    return 0;
}

//insertion sort function
int * naive_sort(int * sort)
{
    int i,j, temp; //pointer variables

    int size = sizeof(sort);
    for(i = 1; i<size; i++)
    {
        j = i-1;

        while(sort[i] < sort[j] && i>0)
        {
            temp = sort[j];
            sort[j] = sort[i];
            sort[i] = temp;
            j--;
            i--;
        }
    }
    return sort;
}



//quicksort
void smarter_sort(int * sorted, int left, int right)
{
    //left has the lowest index of the array to be sorted
    //right has the highest index of the array to be sorted

    int  p ;  //pivot
    int temp; //temporary
    int i ;
    int j ;

    if(left<right)      //function will stop sorting when lowest index         passes highest index
    {
        p = left;       //pivot is set to leftmost element
        i = left;       //i is set to leftmost element
        j = right;      //j is set to rightmost element

        while(i < j)        //stops sorting when left pointer passes right pointer
        {
            while(sorted[i]<=sorted[p] && i < right)    //increments left pointer until it is greater than pivot
                i++;
            while(sorted[j] > sorted[p])                //decrements right pointer until it is smaller than pivot
                j--;
            if(i<j)                                    //swap occurs only when left pointer is lower than right pointer
            {
                //swap i and j
                temp = sorted[i];
                sorted[i] = sorted[j];
                sorted[j] = temp;
            }

        }

        temp = sorted[p];           //swaps pivot and right pointer
        sorted[p]=sorted[j];
        sorted[j]=temp;
        smarter_sort(sorted,left,j-1);  //recursive call of sorting function on left side of pivot
        smarter_sort(sorted,j+1,right); //recursive call of sorting function on right side of pivot

    }
}

运行时，输出表明排序花费了 ~8.7e-313 秒，这太小了关于可能出错的任何想法

Answer 1

您尝试使用 %e 格式说明符打印 naiveTime 和 smarterTime(long 类型的变量)它需要一个 double 类型的参数。这是未定义的行为，会导致您观察到虚假输出。要解决此问题，请使这两个变量的类型为 double 并将计算更改为:

    naiveTime = (time2-time1)/(double)CLOCKS_PER_SEC;
    smarterTime = (time4 - time3)/(double)CLOCKS_PER_SEC;

所以除法实际上是作为浮点除法而不是整数除法完成的。