## 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. }