Understanding Insertion Sorting Using Pseudo Codes and Examples In Java

Insertion Sorting Algorithm -

This sorting algorithm is better then Bubble sort, It reduces number of comparisons that's why its space complexity is less. 

Insertion sort compares data element with its right and start swapping between them.

Each new element start comparing with already sorted list so that its faster then Bubble sort.


Time complexity of insertion sort is O(n) where n is number of data values being sorted but worst case complexity is O(n2). 


Same as Bubble sort this sort is also not advisable for large amount of data.


Assuming that i have list of unsorted array.

20, 55, 2, 71, 10

Let's start with the process ...


As List having 5 elements to be sorted, there would be 4 cycles for comparisons. Insertion sort compare element with its right elements in the list so that we will start with 2nd element of list.



(i)     1st Cycle

Compare 2nd element with right elements, this time only 1st element is available in right. (comparison between array index 1 and 0). 


55 compares with 20.

55 > 20 here swapping is not required.


(ii)     2nd Cycle

Compare 3rd element with its all right elements, this time 2nd and 1st both will be compared with 3rd element.

2 compares with 55.

2 < 55 here 2 will be swapped with 55.

Updated List -  20, 2, 55, 71, 10

next comparison ...

            3rd element has been shifted to 2nd  

            position, again compare element with 
            next right element.

2 compares with 20.

2 < 20 here 2 will be swapped with 20.

Updated List -  2, 20, 55, 71, 10


(iii)     3rd Cycle

Compare 4th element with its all right elements, this time 3rd, 2nd and 1st elements will be compared with 4th element.


71 compares with 55.


71 > 55 here swapping is not required.

next comparison ...

71 compares with 20.


71 > 20 here swapping not required.


next comparison ...


71 compares with 2.


71 > 2 here swapping not required.


In this cycle list would remain same.

List -  2, 20, 55, 71, 10


(iv)     4th Cycle

Compare 5th element with its all right elements, this time 4th, 3rd, 2nd and 1st elements will be compared with 4th element. element is available in right.

10 compares with 71.

10 < 71 here 10 will be swapped with 71.


Updated List -  2, 20, 55, 10, 71


next comparison ...


5th element has been shifted to 4th position, again compare element with next right element.


10 compares with 55.

10 < 55 here 10 will be swapped with 55.

Updated List -  2, 20, 10, 55, 71

next comparison ...

4th element has been shifted to 3rd position, again compare element with next right element.

10 compares with 20.


10 < 20 here 10 will be swapped with 20.


Updated List -  2, 10, 20, 55, 71


next comparison ...


3rd element has been shifted to 2nd position, again compare element with next right element.

10 compares with 2.


10 > 2 here swapping not required.

List would remain same.
List -  2, 10, 20, 55, 71


   Insertion Sort Implementation In Java –

public class InsertionSortExample {


   public static void main(String []args) {
     

     System.out.println("Insertion sort example ...\n");

        
     int size = 5;

     int temp =0;

     int arrayList[] = {20,55,2,71,10};


     for (int i = 1; i0; j--) {


        System.out.println ("Comparing "+arrayList [j]  

        +" and "+arrayList [j-1] +"\n" );

       

        if (arrayList [j] < arrayList [j-1]) {
          

            // swapping process

            temp = arrayList[j-1];                

            arrayList[j-1] = arrayList[j];

            arrayList[j] = temp;

                   
         }

         else {


           System.out.println( "Swapping not required.\n ");        


         }

         System.out.println( "Updated list ");

         printList(arrayList,size);
 
         System.out.println ("----------------------------------\n"); 

  }               

} // end of main method


  public static void printList (int arrayList[], int size) {


    for (int k =0; k<size; k++) {


      System.out.print (arrayList[k] +"  ");
                   

    }

    System.out.println("\n");


    }// end of print method


}// end of class





Output - 



Insertion sort example ...

1 - cycle list
20  55  2  71  10 

Comparing 55 and 20

Swapping not required.

Updated list
20  55  2  71  10 

----------------------------------

2 - cycle list
20  55  2  71  10 

Comparing 2 and 55

Updated list
20  2  55  71  10 

Comparing 2 and 20

Updated list
2  20  55  71  10 

----------------------------------

3 - cycle list
2  20  55  71  10 

Comparing 71 and 55

Swapping not required.

Updated list
2  20  55  71  10 

Comparing 71 and 20

Swapping not required.

Updated list
2  20  55  71  10 

Comparing 71 and 2

Swapping not required.

Updated list
2  20  55  71  10 

----------------------------------

4 - cycle list
2  20  55  71  10 

Comparing 10 and 71

Updated list
2  20  55  10  71 

Comparing 10 and 55

Updated list
2  20  10  55  71 

Comparing 10 and 20

Updated list
2  10  20  55  71 

Comparing 10 and 2

Swapping not required.

Updated list
2  10  20  55  71 


No comments

Powered by Blogger.