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. 

Related Post : How to host your website for FREE (google drive )

.

.

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 

Related Post : Effective Way to test Number is Prime or Not .

---

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)

Related Post :  test your programming skill P-2

---

C++ program : 

---

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

---

Output :

---

Related Post :  Test your Programming Skill : P-1