INSERTION SORT

In this sorting algorithm, in the 1st iteration, the 1st and 0th element of the array are compared. During the 2nd iteration, 2nd element is compared with 0th and 1st element. In general, nth element is compared with all the elements before it. (i.e) from 0th till (n-1)th element. If the nth element is greater than any other element appearing before it, say kth element, then all the elements from kth position till (n-1)th position are shifted to the next position. The nth element is then swapped with the kth element.

PROGRAM:

#include <stdio.h>

void print(int *p,int n)
{
    int j=0;
    while(j<n)
    {
        printf("%d",p[j]);
        j++;
    }
    printf("\n");
}

int main() 
{
   
    int array_size,*array, i,temp,j,k;
    printf("Enter the array size\n");
    scanf("%d", &array_size);
    array=(int*)malloc(sizeof(int)*array_size);
    printf("Enter the array elements\n");
    for(i=0;i<array_size;i++) 
    { 
       scanf("%d",&array[i]); 
    }
    printf("Sorting...\n");
    for(i=1;i<array_size;i++)
    {
        for(j=0;j<i;j++)
        {
            
            if(array[j]>array[i])
            {
                temp=array[i];
                for(k=i;k>j;k--)   array[k]=array[k-1];
                array[j]=temp;
            }
        }
        print(array,array_size);
    }
   return 0;
}

OUTPUT:
Enter the array size
9
Enter the array elements
9 8 6 7 3 5 4 1 2

Sorting...

8 9 6 7 3 5 4 1 2
6 8 9 7 3 5 4 1 2
6 7 8 9 3 5 4 1 2
3 6 7 8 9 5 4 1 2
3 5 6 7 8 9 4 1 2
3 4 5 6 7 8 9 1 2 
1 3 4 5 6 7 8 9 2
1 2 3 4 5 6 7 8 9




<br />