Insertion Sort - C Program


#include<stdio.h>
/* Logic : Suppose if the array is sorted till index i then we can sort the arry till i+1 by inserting
           i+1 th element in the correct position from 0 to i+1. The position at which (i+1)th element has
           to be inserted has to be found by iterating from 0 to i. As any array is sorted till 0th postion
           (Single element is always sorted) and we know how to expand, we can sort the whole array
 */

void InsertionSort(int *array , int number_of_elements)
{
       
int iter,jter;
       
for(iter=1;iter<number_of_elements;iter++)
       
{
               
int current_element = array[iter];
                jter
= iter-1;
               
while(jter>=0 && array[jter] > current_element)
               
{
                        array
[jter+1] = array[jter];
                        jter
--;
               
}
                array
[jter+1] = current_element;
       
}
}
int main()
{
       
int number_of_elements;
        scanf
("%d",&number_of_elements);
       
int array[number_of_elements];
       
int iter;
       
for(iter = 0;iter < number_of_elements;iter++)
       
{
                scanf
("%d",&array[iter]);
       
}
       
/* Calling this functions sorts the array */
       
InsertionSort(array,number_of_elements);
       
for(iter = 0;iter < number_of_elements;iter++)
       
{
                printf
("%d ",array[iter]);
       
}
        printf
("\n");
       
return 0;

}
Comments