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

Answer 2

这是使用插入排序对数组进行排序并计算最佳、平均和最坏情况的比较次数的代码。

#include<iostream>
using namespace std;
int  insertionsort( int arr[ ], int n)
{
 int i,temp,j;
 int comp=0;

 for( i=1; i<n ; i++ )
{
  temp=arr[i];
  j = i - 1;

   while( j>=0 && temp<arr[j])
  {
   arr[j+1] = arr[j] ;
   j = j-1 ;
   comp++;
  }
  arr[j+1]=temp;
  if(temp>arr[j])
  {
    comp++;
  }
}
  return comp;
}
void display(  int arr[ ], int n, int comp )
{
  cout<<" Elements of array after sorting "<<endl;
  for( int i=0; i<n; i++ )
  {
     cout<<arr[i]<<"  ";
  }
  cout<<endl;
  cout<<" Number of comparisions "<<comp<<endl;

 }
int main()
{
   int size;
   int comp = 0;
   cout << " Enter the size of an array " << endl;
   cin >> size;
   int arr[size];
   int n= sizeof(arr) / sizeof(arr[0]);
   cout<<" Enter the elements of array "<<endl;
   for( int i=0; i<size; i++ )
   {
      cin>>arr[i];
   }
   cout<<" Elements of array before sorting "<<endl;
   for( int i=0; i<size; i++ )
   {
        cout<<arr[i]<<"  ";
   }
   cout<<endl;
   int compairsion = insertionsort( arr, n);
   display(  arr, n, compairson);
   return 0;
 }

Answer 3

DIGVIJAY SINGH NAYAL 的回答几乎是正确的。要获得正确的关键比较数量，您需要执行以下操作：

if(j>= 0 && temp>arr[j])
{
   comp++;
}