Insertion sort java

Let’s learn insertion sort java with an example.

Insertion sort java

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 – merge sort in java

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

Insertion sort algorithm:

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,

Insertion program

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; 
      } 
   }

   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


Time complexity

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.


Insertion sort java descending order

Now let’s learn to sort numbers in reverse order. That is, insertion sort java descending order.

import java.util.Arrays;

public class InsertionSortDemo
{
   public static void main(String[] args) 
   {
      int[] arrInput = { 50, 80, 10, 30, 90, 60 };
      System.out.println("Before Sorting: ");
      displayArray(arrInput);
      insertionSort(arrInput);
      System.out.println("\nAfter Sorting: ");
      displayArray(arrInput);
   }

   private static void insertionSort(int[] arrNumber) 
   {
      for(int a = 1; a < arrNumber.length; a++)
      {
         int toSort = arrNumber[a];
         int b = a;
         while(b > 0 && arrNumber[b - 1] < toSort) 
         {
            arrNumber[b] = arrNumber[b - 1];
            b--;
         }
         arrNumber[b] = toSort;
      }
   }

   public static void displayArray(int[] arrPrint) 
   {
      System.out.println(Arrays.toString(arrPrint));
   }
}



Output:

Before Sorting:
[50, 80, 10, 30, 90, 60]

After Sorting:
[90, 80, 60, 50, 30, 10]


Insertion sort string java

Here we are going to learn java insertion sort with string array. Here we are going to create method to sort string array using insertion sort.

In sorting string array using insertion sort we are using Comparable interface. Let’s see java program,

import java.util.Arrays;

public class InsertionSortString 
{
   public static void main(String[] args) 
   {
      String[] fruits = {"Lemon", "Pineapple", "Tangerine", "NanceFruit", "Cherry"};
      System.out.println("String array before sorting : " + Arrays.toString(fruits));
      insertionSort(fruits);
      System.out.println("String array after sorting : " + Arrays.toString(fruits));
   }

   public static void insertionSort(Comparable[] objArray) 
   {
      // insertion sort starts from second element
      for(int a = 1; a < objArray.length; a++)
      {
         Comparable toSort = objArray[a];
         int b = a;
         while(b > 0 && objArray[b - 1].compareTo(toSort) > 1) 
         {
            objArray[b] = objArray[b - 1];
            b--;
         }
         objArray[b] = toSort;
      }
   }
}


Output:

String array before sorting : [Lemon, Pineapple, Tangerine, NanceFruit, Cherry]
String array after sorting : [Cherry, Lemon, NanceFruit, Pineapple, Tangerine]


insertion sort java arraylist

Here’s the interstion sort arraylist,

import java.util.ArrayList;

public class SortArrayList
{
   private static ArrayList<Integer> arrInput = new ArrayList<Integer>();
   public static ArrayList<Integer> getInputArray()
   {
      return arrInput;
   }

   // print array
   public SortArrayList(ArrayList<Integer> inputArray)
   {
      SortArrayList.arrInput = inputArray;
   }

   public void sortArray()
   {
      for(int a = 1; a < arrInput.size(); a++)
      {
         int key = arrInput.get(a);
         for(int b = a - 1; b >= 0; b--)
         {
            if(key < arrInput.get(b))
            {
               arrInput.set(b + 1, arrInput.get(b));
               if(b == 0)
               {
                  arrInput.set(0, key);
               }
            }
            else
            {
               arrInput.set(b + 1, key);
               break;
            }
         }
      }
   }
}

import java.util.ArrayList;
public class InsertionSortArrayList
{
   public static void main(String[] args)
   {
      ArrayList<Integer> al = new ArrayList<Integer>();
      al.add(9);
      al.add(5);
      al.add(2);
      al.add(8);
      al.add(3);
      al.add(1);
      al.add(7);
      SortArrayList sal = new SortArrayList(al);
      System.out.println("Given array: ");
      for(int a : SortArrayList.getInputArray())
      {
         System.out.print(a + " ");
      }
      sal.sortArray();
      System.out.println("\nSorted array: ");
      for(int a : SortArrayList.getInputArray())
      {
         System.out.print(a + " ");
      }
   }
}


Output:

Given array:
9 5 2 8 3 1 7
Sorted array:
1 2 3 5 7 8 9