runtime - 冒泡排序和快速排序的运行时间比较

Question

我希望对两种排序算法(冒泡排序和随机快速排序)进行运行时间比较。我的代码工作正常，但我想我正在使用一些原始技术。 “时钟”计算以 int 为单位，因此即使我尝试以微秒为单位获取时间，我也会得到类似 20000.000 微秒的结果。

代码:冒泡排序:

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

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

int main()
{
int arr[9999], size, i, comparisons;
clock_t start;
clock_t end;
float function_time;    

printf("\nBuBBleSort\nEnter number of inputs:");
scanf("%d", &size);
//printf("\nEnter the integers to be sorted\n");
for(i=0;i<size;i++)
    arr[i]= rand()%10000;

start = clock();    
comparisons= bubblesort(arr, size);
end = clock();
/* Get time in milliseconds */
function_time = (float)(end - start) /(CLOCKS_PER_SEC/1000000.0);

printf("Here is the output:\n");
for(i=0;i<size ;i++)
    printf("%d\t",arr[i]);
printf("\nNumber of comparisons are %d\n", comparisons);
printf("\nTime for BuBBle sort is: %f micros\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]) 
                {
                    //swap (a,k,k+1)
                    temp= a[k];
                    a[k]= a[k+1];
                    a[k+1]= temp;
                    swapped = true;
                }
            }
        if (!swapped)
            break;

    }
return counter;
}

示例输出:

BuBBleSort
Enter number of inputs:2000
Time for BuBBle sort is: 20000.000000 micros

快速排序:

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

int n, counter=0;
void swap(int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}

void quicksort(int s[], int l, int h)
{
int p; /* index of partition */
if ((h- l) > 0) 
{
    p= partition(s, l, h);
    quicksort(s, l, p- 1);
    quicksort(s, p+ 1, h);
}
}

int partition(int s[], int l, int h)
{

int i;
int p; /* pivot element index */
int firsthigh; /* divider position for pivot element */

p= l+ (rand())% (h- l+ 1);
swap(&s[p], &s[h]);
firsthigh = l;

for (i = l; i < h; i++)
if(s[i] < s[h]) 
    {
        swap(&s[i], &s[firsthigh]);
        firsthigh++;
    }

swap(&s[h], &s[firsthigh]);

return(firsthigh);
}  

int main()
{
int arr[9999],i;
clock_t start;
clock_t end;
float function_time;    


printf("\nRandomized Quick Sort");
printf("\nEnter the no. of elements…");
scanf("%d", &n);
//printf("\nEnter the elements one by one…");

for(i=0;i<n;i++)
    arr[i]= rand()%10000;

start = clock();    
quicksort(arr,0,n-1);
end = clock();
/* Get time in milliseconds */
function_time = (float)(end - start) / (CLOCKS_PER_SEC/1000.0);



printf("\nCounter is %d\n\n", counter);
printf("\nAfter sorting…\n");

for(i=0;i<n;i++)
    printf("%d\t",arr[i]);

printf("\nTime for Randomized Quick Sort is: %f ms\n", function_time);

return 0;
}

示例输出:

Randomized Quick Sort
Enter the no. of elements…9999
Time for Randomized Quick Sort is: 0.000000 ms

正如您所看到的，即使输入大小比冒泡排序大得多，快速排序也不会使用我的技术显示任何运行时间。

有人可以帮助通过运行时间比较的那部分来改进它吗？

附注:该代码是从在线资源中大量借用的

Answer 1

尝试以下代码。

printf("Clock() %ld", clock());
sleep(1);
printf("\t%ld\n", clock());

我的结果是...

时钟() 6582 6637

gettimeofday(2) 比clock(3) 更好。因为 gettiemofday(2) 在结构中存储时间

struct timeval {  
    time_t      tv_sec;     /* seconds */  
    suseconds_t tv_usec;    /* microseconds */  
};

记录开始时间和停止时间，然后可以通过公式得到耗时(以微秒为单位)

(stop.tv_sec - start.tv_sec) * 1000000. + stop.tv_usec - start.tv_usec