by Dinesh Thakur Category: Array Pointer and Union

Insertion Sort is a sorting technique based on the idea of inserting a new element in a set of given elements so that the resulting elements are also in sorted order. Suppose a set of 4 elements A[0], A[l], A[2], A[3] are to be sorted in ascending order. Initially sort A[0]and A[l] in ascending order. If A[l] is less than A[0], interchange their positions. Otherwise the positions of the elements remain the same. Next insert A[2] in the appropriate position so that the resulting array A[0], A[l] and A[2] remain sorted. The process is repeated in this manner.

 

Example

 

The program illustrates sorting numbers in ascending order using Insertion sort.

 

#include <iostream.h>

const int n=5;

void main( )

{

int a[n], i,j,k;

int temp;

cout<<"enter the values "<<"\n";

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

cin>>a[i];

for(j=1;j<n;j++)

{

for(k=0;k<j;k++)

{

if (a[j]<a[k])

{

temp=a[j];

for(int l=j;l>k;l--)

a[l]=a[l-1];

a[k]=temp;

break;

}

}

cout<<"pass "<<j<<" ";

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

cout<<a[i]<<" ";

cout<<endl;

}}

 

The first j elements are sorted where j =2,3 ... upto n. The place where (j+1) th element is to be inserted ,that is k, is found .The elements between places k and j are shifted by one position. After that the (j+l)th element is inserted at the kth position.

 

Input and Output:

 

enter the values

 

34        22        49        10        2

 

pass     1          22        34        49        10        2

pass     2          22        34        49        10        2

pass     3          10        22        34        49        2

pass     4          2          10        22        34        49



About Dinesh Thakur

Dinesh ThakurDinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.



Related Articles