Insertion Sort in C Program with Algorithm and Function Code Reducing Techniques :
Example for Insertion Sorting in C Language Program with Explanations is given below :-
Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.
Sorting is typically done in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted. In each iteration the first remaining entry of the input is removed, inserted into the result at the correct position, thus extending the result:
#include<stdio.h>
#include<conio.h>
void insertion_Sort(int, int []); /* function prototype declaration */
void main()
{
int arr[100] , a , n ;
clrscr();
printf("Enter the number of array elements to be Sorted :");
scanf( "%d" , &n );
printf("\nEnter the array elements :\n");
for( a = 0 ; a < n ; scanf("\n %d",&arr[a]) , a++ ); /* see help below */
insertion_Sort(n,arr); /* function calls here. n means array length and arr means array name its enough while passing array */
printf("\nSorted array is given below :");
for( a = 0 ; a < n ; printf(" \n%d " , arr[a] ) , a++ ) ;
/* use ; to end loop, as it contains one statement inside. if we use printf() out side for() loop as usual, then do not use ; at the end of for() loop */
getch();
}
// main() ends here
void insertion_Sort(int n, int arr[]) /* UDF defines here */
{
int i , temp , j ;
for( i = 1 ; i < n ; i++ )
{
temp = arr[i];
j = i - 1 ;
while( j >= 0 )
{
if( temp <= arr[j] )
{
arr[j+1] = arr[j] ;
arr[j] = temp ;
}
j = j - 1 ;
}
}
}
/* below function is same as above, but the program code has been reduced. if you understand, you can use it instead of above function code :
void insertion_Sort(int n, int arr[])
{
int i , temp , j ;
for( i = 1 ; i < n ; i++ )
for( j = i - 1 , temp = arr[i] ; j >= 0 ; j-- )
if( temp <= arr[j] )
{
arr[j+1] = arr[j] ;
arr[j] = temp ;
}
}
*/