Bubble排序和快速排序的運行時間比較

Question

我希望做兩個排序算法 - 泡泡sot和隨機快速排序的運行時間比較。我的代碼工作正常，但我想我正在使用一些原始技術。 '時鐘'計算髮生在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; 
} 

輸出樣本：2000
時間爲冒泡排序爲：

冒泡
輸入的輸入數字： 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; 
} 

樣本輸出：

隨機快速排序
輸入no。元素... 9999
時間爲隨機快速排序爲：0.000000毫秒

正如你所看到的，快速排序沒有表現出任何的運行時間與我的技術，即使有一個更大的輸入大小比冒泡。

有人可以幫助改進與運行時間比較的那部分？

P.S：該代碼是寬鬆線上來源

Answer 1

借來試試follwoing代碼。

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