This is the simple insertion sort program in the C language. Before programming let’s see some of the definitions and algorithms.

## SORTING

Sorting is a process of arranging the elements of a list either in ascending or in descending order. The operation of sorting is most often performed in business data processing applications.

However, sorting is important to process in every application. In the process of sorting almost all the elements move from one place to another place and arranged either in ascending or in descending order.

**I**nsertion sorting in data structure

Suppose an array **A** with **n** elements A[0], A[1], A[2], . . . . . , A[n-1] is in memory. The insertion sort algorithm scans A from A[1] to A[n-1], Inserting each element into its proper position.

For the implementation of insertion sort, we assume that the first element of an array is already sorted. And follow the following steps:

Pass 1A[1] is inserted either before or after A[0] so that A[1], A[0] is sorted. In this pass we get two elements sorted ie A[0], A[1].Pass 2A[2] is inserted into its proper place in the sorted list ie A[0], A[1]. In this pass we get the first three elements sorted ie A[0], A[1], A[2].Pass 3A[3] is inserted into its proper place ……………………………………………………………….. ………………………………………………………………… ………………………………………………………………..And at the endPass N-1A[n-1]is inserted into its proper place in the sorted list ie A[0], A[1], A[2]……A[n-2] So that A[0],A[1],A[2]…….to A[n-1] all the element will be sorted.

**ALGORITHM OF INSERTION SORT**

**INSERTION_SORT [ i, j, n, a, Temp]**

In the below algorithm **a** is an array with n elements. **i** keeps the track of passes, **j** keeps the track of those locations of elements with whom temp is to be compared. Temp holds the element that is to be inserted in its proper place.

- Initialize i=1.
- Repeat steps 3 ,4 ,5,8,9 while i<=n-1 otherwise move to step 10
- Set: j=i-1.
- temp=a[i]. [Assign value of a[i] to temp]
- Repeat steps 6,7 while j>=0 and temp < a[j].
- a[j+1]=a[j] [Assign a[j] to a[j+1] ]
- j=j-1 [decrement j by one]
- i=i+1 [increment i by one ]
- a[j+1]=temp [Assign temp to a[j+1] (This is insertion of selected element to its proper place) ]
- STOP

## Insertion sort program in the C

### Source Code:

// insertion sort program in c. #include<stdio.h> // function to perform insertion sort void isort(int A[]){ //declaraiton of variables int key,i,j,z; //using nested for to execute insetion sort for(z=0; z<=8-1; z++){ for(j=1; j<=8-1; j=j+1){ key = A[j]; i=j-1; if(i>=0 && A[i]>key){ A[i+1] = A[i]; A[i] = key; } } } } // function to display array void dispArr(int A[]){ int i; for(i=0; i<=8-1; i++){ printf("%d ", A[i]); } } // main funtion void main(){ int i; int A[]= {10, 8, 7, 9, 3, 2, 1, 6}; //statements to display unsorted array printf("This is your given(unsorted) array: "); dispArr(A); //calling funtion to perform insertion sort isort(A); //statements to display sorted array printf("\nThis is your sorted array: "); dispArr(A); }

## Output:

This is your given(unsorted) array: 10 8 7 9 3 2 1 6 This is your sorted array: 1 2 3 6 7 8 9 10