Insertion Sort

Insertion Sort

In this method the elements are inserted at their appropriate place. Hence is the name insertion sort. Let us understand this method with the help of some example -

For Example

Consider a list of elements as,

The process starts with first element

Algorithm

Although it is very natural to implement insertion using recursive(top down) algorithm. but it is very efficient to implement it using bottom up(iterative) approach.

Algorithm Insert_sort(A[0...n-1])

//Problem Description: This algorithm is for sorting the

//elements using insertion sort

//Input: An array of n elements

//Output: Sorted array A[0...n-1] in ascending order

for i←1 to n-1 do

{

temp←A[i]//mark A[i]th element

j←i-1//set j at previous element of A[i]

while(j>=0)AND (A[j]>temp)do

//comparing all the previous elements of A[i] with

 //A[i].If any greater element is found then insert

//it at proper position

A[j+1] ← A[j]

j←j-1

}

A[j+1] ← temp //copy A[i] element at A[j+1]

}

Advantages of insertion sort

1. Simple to implement.

2. This method is efficient when we want to sort small number of elements. And this method has excellent performance on almost sorted list of elements.

3. More efficient than most other simple O (n2) algorithms such as selection sort or

bubble sort.

4. This is a stable (does not change the relative order of equal elements).

5. It is called in-place sorting algorithm (only requires a constant amount O(1) of extra memory space). The in-place sorting algorithm is an algorithm in which the input is overwritten by output and to execute the sorting method it does not require any more additional space.

Let us now see the implementation of this method using C.

Ex. 6.5.1: C program sorting elements using insertion sort.

Sol. :

/*************************************************************

Implementation of insertion sort

*************************************************************/

#include<stdio.h>

#include<conio.h>

void main()

{

int A[10],n,i;

void Insert_sort(int A[10],int n);

clrscr();

printf("\n\t\t Insertion Sort");

printf("\n How many elements are there?");

scanf("%d", &n);

printf("\n Enter the elements\n");

for(i=0;i<n;i++)

scanf("%d", &A[i]);

Insert_sort(A,n);

getch();

}

void Insert_sort(int A[10], int n)

{

int i,j,temp;

for(i=1;i<=n-1;i++)

{

temp =A[i];

j=i-1;

while((j>=0)&&(A[j]>temp))

{

A[j+1]=A[j];

j=j-1;

}

A[j+1]=temp;

}

printf("\n The sorted list of elements is...\n");

for(i=0;i<n;i++)

printf("\n%d",A[i]);

}

Output

Insertion Sort

How many elements are there?5

Enter the elements

30

20

10

40

50

The sorted list of elements is

10

20

30

40

50

Logic Explanation

For understanding the logic of above C program consider a list of unsorted elements as,

Then the control moves to while loop. As j >= 0 and A[j] > temp is True, the while loop will be executed."

Now since j >= 0 is false, control comes out of while loop.

Then list becomes,

Thus we have scanned the entire list and inserted the elements at corresponding locations. Thus we get the sorted list by insertion sort.

Ex. 6.5.2: Write a routine for insertion sort. Sort the following sequence using insertion sort. 3, 10, 4, 2, 8, 6, 5, 1.

Sol. We will store the elements in an array.

The process will start from the first element.