Tuesday, 22 October 2013

Insertion Sort (concept & algorithm)

insertion like cards


An array A with N elements A[1], A[2] … A[N] is in memory

Insertion Sort scan A from A[1] to A[N] inserting each elements A[k] into its proper position in the previously sorted subarray A[1], A[2], …. A[K-1]

Pass 1: A[1] by itself is trivially sorted
Pass 2: A[2] is inserted either before or after A[1] so that A[1], A[2] is sorted
Pass 3: A[3] is inserted in its proper place in A[1], A[2], that is before A[1], between A[1] and A[2] or after A[2] so that A[1], A[2], A[3] is sorted

Pass 4: A[4] is inserted in its proper place in A[1], A[2], A[3] so that A[1], A[2], A[3], A[4]  is sorted. 
.
.
Pass N: A[N] is inserted in its proper place in A[1], A[2], A[3], .. A[N-1]  so that A[1], A[2], A[3], A[4] ,  A[N]  is sorted. 


Insertion Sort Example :

Sort an array A with 8 elements
77, 33, 44, 11, 88, 66, 55 

Insertion Algorithm :

This algorithm sort an array with N elements
[1] Set A[0] = -∞ [Initialize a delimiter]
[2] Repeat Steps 3 to 5 for K = 2, 3, …, N
[3] Set TEMP = A[K] and PTR = K-1
[4] Repeat while TEMP < A[PTR]
(a) Set A[PTR+1] = A[PTR]
(b) Set PTR = PTR -1
[5] Set A[PTR+1] = TEMP
[6] Exit

Related Post : TOWER OF HANOI

Complexity of Insertion Sort :


  Worst Case: O(n^2)


   Average Case: O(n^2)

C++ program : 



  1. /*
  2. Insertion sort   //most optimise algorithm
  3. beginer2cs.blogspot.com
  4. */
  5. #include<iostream>
  6. #include<malloc.h> 
  7. using namespace std;
  8. main()
  9. {
  10.         int *arr,n,i,j,key;
  11.        
  12.         cout<<"Number of element to sort : ";
  13.         cin>>n;
  14.        
  15.         arr=(int*)malloc(sizeof(int)*n); //allocating space to array
  16.        
  17.         cout<<"Enter element of array \n";
  18.         for(i=0;i<n;i++)
  19.           cin>>*(arr+i);  //taking input
  20.          
  21.         /********** insertion sort begin  ************/
  22.         for(j=1;j<n;j++)  //start from second element
  23.           {
  24.                 key=*(arr+j); //storing j'th element to temp variable
  25.                 i=j-1;
  26.                 while(i>=0 && key<*(arr+i))
  27.                 {
  28.                         *(arr+i+1)=*(arr+i);
  29.                         i--;
  30.                 }
  31.                 *(arr+i+1)=key ;  //final position where key placed
  32.           }
  33.         /***************sorting complete ********************/
  34.        
  35.         //Print sorted array
  36.         cout<<"sorted list \n ";
  37.         for(i=0;i<n;i++)
  38.          cout<<*(arr+i)<<"  ";
  39.          
  40.          return 0;
  41. }

Output :

insertion sort


No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets