Insertion Sort Using Functions

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

Logic : Here, sorting takes place by inserting a particular element at the appropriate position, that’s why the name-  insertion sorting. In the First iteration, second element A[1] is compared with the first element A[0]. In the second iteration third element is compared with first and second element. In general, in every iteration an element is compared with all the elements before it. While comparing if it is found that the element can be inserted at a suitable position, then space is created for it by shifting the other elements one position up and inserts the desired element at the suitable position. This procedure is repeated for all the elements in the list.
If we complement the if condition in this program, it will give out the sorted array in descending order.
When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.
Animation showing the algorithm for Insertion sort :

 

A brief view on how the logic Proceeds :

Program for Insertion Sort Compiled and Executed in turbo c++ 

#include<iostream.h>
#include<conio.h>
void insertionsort(int a[],int)   ;
void main()
{
int n,i,j,k,a[30];
cout<<"enter the no of elements you want to enter";
cin>>n;
cout<<"Enter the elements";
for(i=0;i<n;i++)
cin>>a[i];
insertionsort(a,n);
getch();
}
void insertionsort(int array[],int size)
{
int i, j, key;

for (j=1; j<size; j++)
{
key= array[j];
i=j-1;
while((i>=0)&&(array[i]>key))
{
array[i+1]= array[i];
i=i-1;
}
array[i+1]=key;
}
cout<<"sorted array is";
for(i=0;i<size;i++)
cout<<array[i]<<"\t";
}

Class	Sorting algorithm
Data structure	Array
Worst case performance	О(n2)
Best case performance	O(n)
Average case performance	О(n2)
Worst case space complexity	О(n) total, O(1) auxiliary