Insertion Sort

Insertion Sort

AU May-19, Marks 7

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

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. 7.2.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))

{

Alj+1]=A[j];

j=j-1; smel

}.

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. 7.2.2: Write a routine for insertion sort. Sort the following sequence using insertion sort. 3, 10, 4, 2, 8, 6, 5, 1.

AU May-19, Marks 7

Sol. : We will store the elements in an array.

The process will start from the first element.