3

我希望对两种排序算法进行运行时比较——Bubble sot 和 Randomized Quick sort。我的代码工作正常，但我想我正在使用一些原始技术。“时钟”计算发生在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
输入输入数：2000
BuBBle 排序时间为：20000.000000 微

快速排序：

#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;
}

样本输出：

随机快速排序
输入编号。元素数…9999
随机快速排序的时间为：0.000000 ms

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

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

ps：代码大量借鉴网上资源

4

1 回答 1

2

试试下面的代码。

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

我的结果是……

时钟（） 6582 6637

gettimeofday(2) 比时钟(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
于 2014-11-20T19:40:54.847 回答