Simple Insertion Sort Program in C Language

/ C / By

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.

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

    //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