Insertion Sort Java

Hey guys!! Welcome to flower brackets blog. In this post we are going to learn insertion sort java with an example.

Insertion sort in java

Insertion sort sorts elements the way in which we sort playing cards. Given an array of elements, let’s sort them in increasing order.

For example, the elements will be integers. So let’s look at a sample list of elements. We have a list of six elements that we want to sort and we will number them from 0 to 5.

Also Read – Bubble Sort Java Program

Insertion sort java

First element 50 is already sorted because insertion sort sorts from the left. So the definition of sorted means that all elements to the left of an element are smaller than that element.

So you can see that element 50 at index 0 has no element to the left of it that are larger than 50. Therefore 50 is already in sorted situation.

We will start our insertion sort at index 1 which is 80. So we will set our key value x = 80. Now our first comparison is to the element which is to the left of key value, that is, 50.

And the comparison is x < 50? In other words is 80 < 50? No it’s not. So, 80 is going to stay where it is. 80 is now considered sorted.

Then we will look at index 2 in our list which is 10. We will assign x = 10, our first comparison is x < 80? Yes it is, 10 < 80. So it’s going to swap 80 and 10.

Our key does not change though. Our “x” value is still equal 10. So our next comparison is 10 < 50? Yes it is, so it’s going to swap 50 and 10.

Now we can see that we started at index 2, index 2 is now sorted. So we are going to jump our pointer to index 3 which is 30.

So, we set our key value x = 30. Our first comparison is x < 80? Yes it is, so it’s going to swap 30 and 80. Next comparison is 30 < 50? Yes, it’s going to swap those two.

Next comparison is 30 < 10? No it’s not, so we are done sorting upto index 3. As you can see at this point we have sorted four elements from index 0 through 3 and you can that see each one of values to its left are all smaller.

Also Read – Selection Sort Java

 So the values to the left of 80 are all smaller. Our next element in the list is 90, we set x = 90. Our first comparison is x < 80? Well no it’s not and since we already know that all the elements to the left of 80 are smaller than 80 because the list is sorted.

Then they are also less than 90. So we know that 90 is already done. So we are going to move on to index 5 which is 60.

We set x = 60. Our first comparison is 60 < 90? Yes it is, let’s swap them. Next comparison is 60 < 80? Yes it is, we are going to swap 60 and 80.

Next comparison is 60 < 50? No, it is not so the sort is now finished. That is our sorted array. Here’s the java program for insertion sort,

public class InsertionSort 
{ 
   void sort(int arrNumber[]) 
   { 
      int num = arrNumber.length; 
      for(int a = 1; a < num; ++a) 
      { 
         int key = arrNumber[a]; 
         int b = a - 1; 

         while(b >= 0 && arrNumber[b] > key) 
         { 
            arrNumber[b + 1] = arrNumber[b]; 
            b = b - 1; 
         } 
         arrNumber[b + 1] = key; 
      } 
   }

   static void displayArray(int arrInsert[]) 
   { 
      int n = arrInsert.length; 
      for(int a = 0; a < n; ++a) 
         System.out.print(arrInsert[a] + " ");
      System.out.println(); 
   }

   public static void main(String[] args) 
   { 
      int arrDemo[] = {50, 80, 10, 30, 90, 60};
      InsertionSort obj = new InsertionSort(); 
      obj.sort(arrDemo);
      displayArray(arrDemo);
   }
}

Output:

10 30 50 60 80 90


Conclusion

That’s it guys. This was all about insertion sort algorithm in java with example. I hope you guys have understood the concept.

You can subscribe to my blog flower brackets blog if you haven’t already.

Do share this post if you like.

Related Posts