what is Insertion Sort?

Insertion Sort

Insertion sort is the simple sorting algorithm which is commonly used in the daily lives while ordering a deck of cards. In this algorithm, we insert each element onto its proper place in the sorted array. This is less efficient than the other sort algorithms like quick sort, merge sort, etc.

Technique

Consider an array A whose elements are to be sorted. Initially, A[0] is the only element on the sorted set. In pass 1, A[1] is placed at its proper index in the array.

In pass 2, A[2] is placed at its proper index in the array. Likewise, in pass n-1, A[n-1] is placed at its proper index into the array.

To insert an element A[k] to its proper index, we must compare it with all other elements i.e. A[k-1], A[k-2], and so on until we find an element A[j] such that, A[j]<=A[k].

All the elements from A[k-1] to A[j] need to be shifted and A[k] will be moved to A[j+1].

Complexity

Complexity	Best Case	Average Case	Worst Case
Time	Ω(n)	θ(n2)	o(n2)
Space			o(1)

Algorithm

• Step 1: Repeat Steps 2 to 5 for K = 1 to N-1
• Step 2: SET TEMP = ARR[K]
• Step 3: SET J = K ? 1
• Step 4: Repeat while TEMP <=ARR[J]
  SET ARR[J + 1] = ARR[J]
  SET J = J ? 1
  [END OF INNER LOOP]
• Step 5: SET ARR[J + 1] = TEMP
  [END OF LOOP]
• Step 6: EXIT

C Program

1. #include<stdio.h>  
2. void main ()  
3. {  
4.     int i,j, k,temp;  
5.     int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
6.     printf("\nprinting sorted elements...\n");  
7.     for(k=1; k<10; k++)   
8.     {  
9.         temp = a[k];  
10.         j= k-1;  
11.         while(j>=0 && temp <= a[j])  
12.         {  
13.             a[j+1] = a[j];   
14.             j = j-1;  
15.         }  
16.         a[j+1] = temp;  
17.     }  
18.     for(i=0;i<10;i++)  
19.     {  
20.         printf("\n%d\n",a[i]);  
21.     }  
22. }  

Output:

Printing Sorted Elements . . . 
7
9
10
12
23
23
34
44
78 
101 

---

C++ Program

1. #include<iostream>  
2. using namespace std;  
3. int main ()  
4. {  
5.     int i,j, k,temp;  
6.     int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
7.     cout<<"\nprinting sorted elements...\n";  
8.     for(k=1; k<10; k++)   
9.     {  
10.         temp = a[k];  
11.         j= k-1;  
12.         while(j>=0 && temp <= a[j])  
13.         {  
14.             a[j+1] = a[j];   
15.             j = j-1;  
16.         }  
17.         a[j+1] = temp;  
18.     }  
19.     for(i=0;i<10;i++)  
20.     {  
21.         cout <<a[i]<<"\n";  
22.     }  
23. }  

Output:

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

---

Java Program

1. public class InsertionSort {  
2. public static void main(String[] args) {  
3.     int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
4.     for(int k=1; k<10; k++)   
5.     {  
6.         int temp = a[k];  
7.         int j= k-1;  
8.         while(j>=0 && temp <= a[j])  
9.         {  
10.             a[j+1] = a[j];   
11.             j = j-1;  
12.         }  
13.         a[j+1] = temp;  
14.     }  
15.     System.out.println("printing sorted elements ...");  
16.     for(int i=0;i<10;i++)  
17.     {  
18.         System.out.println(a[i]);  
19.     }  
20. }  
21. }  

Output:

Printing sorted elements . . . 
7
9
10
12
23
23
34
44
78 
101 

---

C# Program

1. using System;  
2.                       
3. public class Program  
4. {  
5.       
6.     public static void Main()  
7.     {  
8.         int i,j, k,temp;  
9.         int[] a = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
10.     Console.WriteLine("\nprinting sorted elements...\n");  
11.     for(k=1; k<10; k++)   
12.     {  
13.         temp = a[k];  
14.         j= k-1;  
15.         while(j>=0 && temp <= a[j])  
16.         {  
17.             a[j+1] = a[j];   
18.             j = j-1;  
19.         }  
20.         a[j+1] = temp;  
21.     }  
22.     for(i=0;i<10;i++)  
23.     {  
24.         Console.WriteLine(a[i]);  
25.     }  
26. }  
27. }  

Output:

printing sorted elements . . . 
7
9
10
12
23
23
34
44
78 
101 

---

Python Program

1. a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]  
2. for k in range(1,10):  
3.     temp = a[k]   
4.     j = k-1  
5.     while j>=0 and temp <=a[j]:  
6.         a[j+1]=a[j]  
7.         j = j-1  
8.     a[j+1] = temp   
9. print("printing sorted elements...")  
10. for i in a:  
11.     print(i)  

Output:

printing sorted elements . . . 
7
9
10
12
23
23
34
44
78 
101 

---

Swift Program

1. import Foundation  
2. import Glibc  
3.     var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];   
4.     print("\nprinting sorted elements...\n");  
5.     for k in 1...9  
6.     {  
7.         let temp = a[k];  
8.         var j = k-1;  
9.         while j>=0 && temp <= a[j]  
10.         {  
11.             a[j+1] = a[j];   
12.             j = j-1;  
13.         }  
14.           
15.         a[j+1] = temp;  
16.     }  
17.     for i in a  
18.     {  
19.         print(i);  
20.     }     

Output:

printing sorted elements...

7
9
10
12
23
23
34
44
78
101

---

JavaScript Program

1. <html>  
2. <head>  
3. <title>   
4.     Insertion Sort   
5. </title>   
6.     </head>  
7.     <body>   
8.         <script>   
9.                 var txt = "<br>";  
10.             var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
11.             document.writeln("printing sorted elements ... "+txt);  
12.             for(k=0;k<10;k++)  
13.             {  
14.                 var temp = a[k]  
15.                 j=k-1;  
16.                 while (j>=0 && temp <= a[j])  
17.                 {  
18.                     a[j+1] = a[j];   
19.                     jj = j-1;  
20.                 }  
21.                 a[j+1] = temp;  
22.             }  
23.           
24.             for(i=0;i<10;i++)  
25.             {  
26.                 document.writeln(a[i]);  
27.                 document.writeln(txt);  
28.             }  
29.         </script>   
30.     </body>  
31. </html>  

Output:

printing sorted elements ...
7
9
10
12
23
23
34
44
78
101

---

PHP Program

1. <html>  
2. <head>  
3. <title>Insertion Sort</title>  
4. </head>  
5. <body>  
6. <?php  
7.  $a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);  
8.             echo("printing sorted elements ... \n");  
9.             for($k=0;$k<10;$k++)  
10.             {  
11.                 $temp = $a[$k];  
12.                 $j=$k-1;  
13.                 while ($j>=0 && $temp <= $a[$j])  
14.                 {  
15.                     $a[$j+1] = $a[$j];   
16.                     $j = $j-1;  
17.                 }  
18.                 $a[$j+1] = $temp;  
19.             }  
20.             for($i=0;$i<10;$i++)  
21.             {  
22.                 echo $a[$i];  
23.                 echo "\n";  
24.             }  
25. ?>  
26. </body>  
27. </html>  

Output:

printing sorted elements ...
7
9
10
12
23
23
34
44
78
101