c - 插入排序 - 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;
 }