插入排序 - C中的比較和交換計數

Question

如何計算插入排序中的比較次數和交換次數？我有10個隨機數組。如果有人幫助我如何在這個程序中添加20,50,100,200,500,1000,2000和5000個隨機數，我將會非常高興。我一直在想這個很長時間，但仍然找不到解決辦法。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>    
int main() 
{ 

    int array[10]; 
    int i, j, n, temp; 
    n = 10; 
    for (i = 0; i < n; i++) 
     array[i] = rand(); 

    /*Sort*/ 
    for (i = 1; i < n; i++) { 
     j = i; 
     while ((j > 0) && (array[j - 1] > array[j])) { 
      temp = array[j - 1]; 
      array[j - 1] = array[j]; 
      array[j] = temp; 
      j--; 
     } 
    } 
    /* Print */ 
    printf("Sorted Array\n"); 
    for (i = 0; i < n; i++) 
     printf("%d \n", array[i]); 
    return 0; 
} 

Answer 1

此使用，你可以找出插入比較和交換的總數排序

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

    int main() 
    { 

     int array[10]; 
     int i, j, n, temp,no_swap=0,comp=0;//variables to find out swaps and comparisons 
     n = 10; 
     for (i = 0; i < n; i++) 
     array[i] = rand(10); 

/*Sort*/ 
     for (i = 1; i < n; i++) { 
     j = i; 
     comp++; 
     while ((j > 0) && (array[j - 1] > array[j])) { 
      if(array[j-1]>array[j]){ 
      comp++; 
     } 
     temp = array[j - 1]; 
     array[j - 1] = array[j]; 
     array[j] = temp; 
     j--; 

     no_swap++;//increment swap variable when actually swap is done 
    } 
} 
/* Print */ 

     printf("\nNo of swaps = %d",no_swap); 
     printf("\nNo of comparisions = %d",comp); 
     printf("\nSorted Array\n"); 
     for (i = 0; i < n; i++) 
      printf("%d \n", array[i]); 
     return 0; 
}