簡單的排序程序中的計數比較和掉期

-1

我有一個任務，我需要一點幫助。我們必須在C中選擇兩種排序算法，並對效率進行比較。我寫了下面的代碼，但我不確定比較是否正確。我認爲互換是可以的。我對此很新，所以如果你看到任何明顯的缺陷，就要溫柔一些。簡單的排序程序中的計數比較和掉期

#include <stdlib.h> 
#include <time.h> 
#define MAX 20 


int main(void) 
{ 
//Declare variables 
int i,x,y,temp; 
int comparsioncounter=0; 
int swapcounter=0; 
//Assign values to our array. I didn’t use random numbers so we could compare the two methods 
int array[MAX]= {3,1,5,8,7,13,17,34,22,31,28,2,17,44,23,67,32,9,12,30}; 

//start clock to time execution time 
clock_t start, end; 
start = clock(); 
printf("Unsorted array\n"); 
//print unsorted array 
for(i=0; i<MAX;i++){ 
printf("%d ",array[i]); 
} 
printf("\n"); 
//Our sort algorithm 
for (x=0; x<MAX; x++){ 
    for(i=0;i<MAX-1;i++){ 
     //counter to keep track of how many times the comparison loops 
     comparsioncounter++; 
     if(array[i]>array[i+1]) 
     { 
      temp=array[i]; 
      array[i]=array[i+1]; 
      array[i+1]=temp; 
      //Counter to keep track of how many times the comparison loops 
      swapcounter++; 
     } 
    } 

} 
      //print sorted array 
    printf("\nSorted array\n"); 
    for(i=0; i<MAX;i++){ 
    printf("%d ",array[i]); 

} 
//Print out number of comparsions and swaps 
printf("\n\nNumber of comparsions is %d\n", comparsioncounter); 
printf("Number of swaps is %d", swapcounter); 
end = clock(); 
//print out execution time 
printf("\nTime taken in seconds: %.5lf\n", ((double)(end - start))/CLOCKS_PER_SEC); 
return 0; 
}

來源

2015-02-06 niallo27

對於非常小的一組輸入，在紙*上進行計算*，然後與您在程序中獲得的結果進行比較。如果兩者都相同，那麼你可能是正確的，否則有什麼問題。 – 2015-02-06 13:12:44

'x <20; .. i <19'：20 * 19 ='380' – BLUEPIXY 2015-02-06 13:13:56

如果我將數組縮小到4的大小。掉換計數正確，但比較返回16.我不認爲這是正確的 – niallo27 2015-02-06 13:14:03

似乎是正確的。

另一種可能更明顯的方法是編寫一個比較和交換函數來計數它們的計數器。

這樣的：

static unsigned comps = 0, swaps = 0; 

int compare(int l, int r) 
{ 
    comps++; 
    return (l > r); 
} 

void swap(int *l, int *r) 
{ 
    swaps++; 
    int t = *l; 
    *l = *r; 
    *r = t; 
}

，然後用它們來代替。

來源

2015-02-06 13:22:31

簡單的排序程序中的計數比較和掉期

回答

相關問題