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 sorts elements the way in which we sort (playing) cards. It is useful when number of elements is small. Given an array of elements, let’s sort them in increasing order.

Also read – bubble sort java program

So let’s look at sample list of integer elements. We have a list of six elements that we want to sort and we will number them from 0 to 5.

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 element 50 at index 0 has no element to the left of it that is larger than 50. Therefore 50 is already sorted.

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 swap 80 and 10.

Key does not change though. “x” value is still 10. So our next comparison, is 10 < 50? Yes it is, so swap 50 and 10.

Now we can see that we started at index 2 and 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 in 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 since 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, swap them. Next comparison, is 60 < 80? Yes it is, swap 60 and 80.

Next comparison, is 60 < 50? No, it is not. So sorting is now finished. We have our sorted array (as shown in above figure). Here’s the java program for insertion sort,

public class InsertionSort 
{ 
   public void sort(int arrNum[])
   {
      int number = arrNum.length; 
      for(int a = 1; a < number; ++a) 
      { 
         int keyValue = arrNum[a]; 
         int b = a - 1;
         while(b >= 0 && arrNum[b] > keyValue) 
         { 
            arrNum[b + 1] = arrNum[b]; 
            b = b - 1; 
         } 
         arrNum[b + 1] = keyValue; 
      } 
   }

   // printing array
   static void displayArray(int arr[]) 
   { 
      int num = arr.length; 
      for(int a = 0; a < num; ++a)
      {
         System.out.print(arr[a] + " ");
      }
      System.out.println(); 
   }

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

Output:

10 30 50 60 80 90


What is time complexity of insertion sort?

It’s O(n*2). This sorting algorithm takes more time if elements in the array is in reverse order.

Auxiliary space : O(1)

Best performance : O(n) comparison and O(1) swap.

Worst performance : O(n²) comparison and swap.

Average performance : O(n²) comparison and swap.

Related Posts