Question

The insertion sort algorithm updates its sorted array as each new data value is entered. It is an in-place algorithm, in that the sorted array at each step writes over the array from the previous step.

• Let us start with sorting in descending order (largest to smallest). The ascending order case follows as a simple modification to the descending case.

• Assume that we have thus far read N values and these are sorted in correct order (largest to smallest) in our array. We then read the next number, and we desire to place it in our array in the proper position. In order to do so, we compare the new input with the existing array values, starting with the last array element. If the new input has a value greater than the last array element, shift the array element to the next higher index (i.e., copy the N-th element to the N+1-th element). Continue to compare with lower indices; as long as the new input has a greater value than the current element, copy that element to the next higher index. At some point, the input value may not be greater than the array element; in this case, break out of the element-by-element testing and replace the previously compared element by the new input.

• For example: Assume that we have already read these five numbers: {1, 5, 3, 2, 6}. The numbers are sorted as they are read, thus our array will look like the following (where beyond the fifth element the array values are undefined and hold some random value):

6

5

3

2

1

?

...

?

Answer 1

/* Program for Insertion Sort in desending order for 10

elements*/
#include<stdio.h>
#include<conio.h>
int main()
{
   int a[10], n,i,b,temp, j;
   printf("\n Enter Number of elements you want to

insert");
   scanf("%d",&n);
   printf("\n Enter Elements for the array : ");
   for(i=0;i<n-1;++i)
   {
   scanf("%d",&a[i]);
   }
  
   for(i=1;i<n-1;++i)
   {
       for(b=0;b<i;++b)
           {
           if(a[b]<a[i])
           {
           temp=a[i];
           j=i;
           while(j!=b)
           {
               a[j]=a[j-1];
               --j
           }
       a[b]=temp;
       }
       }
   printf("\n The Descending Order is as follows: ");
   for(i<0;i<=n-1;++i)
   {   printf("%d ",a[i]); }
   return 0;
}