Simple Insertion Sort Program in C Language

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.

Insertion 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 1 A[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 2 A[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 3 A[3] is inserted into its proper place

………………………………………………………………..

…………………………………………………………………

………………………………………………………………..

And at the end

Pass N-1 A[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.

10. 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[]) {
    int key,i,j;
    for(i=1; i<8; i++) {
        key = A[i];
        j = i-1;
        while(j>=0 && A[j] > key) {
            A[j+1] = A[j];
            j = j-1;
        }
        A[j+1] = key;
    }
}

// function to display array
void dispArr(int A[]) {
    int i;
    for(i=0; i<8; i++) {
        printf("%d ", A[i]);
    }
}

// main function 
int main() {
    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 function to perform insertion sort
    isort(A);
    
    //statements to display sorted array
    printf("\nThis is your sorted array: ");
    dispArr(A);
    return 0;
}

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