Program For Insertion Sort in C++[How to]

Insertion Sort

Goal: Program For insertion sort in C++.

Method-used: Insertion Sort.               

Description:-  The simplest way to understand Insertion sort is-

                        1.It divides given array into two parts. First is sorted one and second is remaining elements of input array those are unsorted.

                        2.It always take one element from second input unsorted array and finds its appropriate place in sorted one.

                        3.It repeats step-2,until there is no element in unsorted array.

     Example:

                            0  5  1  4  2  3

                            0  5  1  4  2  3
                            0  5  1  4  2  3

                            0  1  5  4  2  3

                            0  1  4  5  2  3

                            0  1  2  5  4  3

                            0  1  2  3  4  5  

                            Insertion Sort is not used for large data items.It is less efficient than advanced sorting techniques like quick sort,bubble sort and merge sort etc.

There are also some advantage of Insertion sort that is-

                 1.It has simple implememtation.

                 2. It doesn't take memory space more than O(1) .

                 3.It sorts the array as it receives it ,it increase its time efficiency in some online applications.

Program:-

#include<iostream>

using namespace std;

#include<conio.h>

int main()

  {

          int a[10],i,temp,n,k;

          cout<<"\n\tHow many numbers you wnat to have in array\n";

          cout<<"\t";

          cin>>n;

          cout<<"\n\tEnter elements--";

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

             {

                           cout<<"\t";

                           cin>>a[i];

             }  

         a[0]=0;

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

          {

             temp=a[i];

             k=i-1;

             while(temp<a[k])

              {

                  a[k+1]=a[k];   //Moving element forward

                  k=k-1;

              }    

              a[k+1]=temp;

          }   

          cout<<"\n\tSorted Elements :\n";

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

             {

                           cout<<"\t";

                           cout<<a[i];

             }  

             getch(); 

  }

Output:-

Complexity:-

                       Worst case- Worst case occurs when given array is in reverse order and inner loop must use the maximum no. (k-1) of comparison .

             f(n)=1+2+3..........+(n-1)=n(n-1)/2             f(n)=n^2

Complexity is same for average case in which no of comaparison is (n-1)/2.

If you want to share more information about topic discussed above or find anything incorrect Please do comments.