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. This sort can be fast when used with smaller arrays. Given an array of elements, let’s sort them in increasing order.

Also read – merge sort java

So let’s look at sample list of integer elements. We have an array of six elements that we want to sort.

Insertion sort algorithm:

Insertion sort iteration starts 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 the key value, that is, 50.

insertion sort java

Now, is x < 50? In other words, is 80 < 50? No. So, 80 is going to stay where it is.

Then we will look at index 2 in the array which is 10. We will assign key value x = 10. Now, 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. Swap 50 and 10.

So we are going to jump our pointer to index 3 which is 30.

So, we set our key value x = 30. Now, is x < 80? Yes it is, swap 30 and 80. Next comparison, is 30 < 50? Yes, swap those two numbers.

Next comparison, is 30 < 10? No it’s not, so we are done sorting upto index 2.

Also read – selection sort java

So the values to the left of 80 are all smaller. Our next element in the array is 90, we set x = 90.

Now, is x < 80? No. Here all the elements to the left of number 80 are smaller than 80 and sorted.

So we move on to index 5 which is 60. We set key value x = 60. Now, is 60 < 90? Yes it is, swap them. Next comparison, is 60 < 80? Yes it is, swap 60 and 80.

We have our sorted array (as shown in above figure). Here’s the java program for insertion sort.

Insertion program

public class InsertionSortExample
{
   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[] arrNum)
   {
      int num = arrNum.length;
      for(int a = 0; a < num; ++a)
      {
         System.out.print(arrNum[a] + " ");
      }
      System.out.println();
   }
   public static void main(String[] args)
   {
      int[] arrInput = { 50, 80, 10, 30, 90, 60 };
      InsertionSortExample obj = new InsertionSortExample();
      obj.sort(arrInput);
      displayArray(arrInput);
   }
}


Output:

10 30 50 60 80 90


Time complexity

It’s O(n*2). Insertion sort 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 InsertionSortDescendingOrder
{
   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.

To sort array of strings using string array with insertion sort we are creating sortStringArray() method. Let’s see java program.

public class InsertionSortString
{
   public static void main(String[] args)
   {
      String[] arrFruits = {"Orange","Mango","Apple","Pineapple","Banana"};
      String[] strSorted = sortStringArray(arrFruits, arrFruits.length);
      for(int a = 0; a < strSorted.length; a++)
      {
         System.out.println(strSorted[a]);
      }
   }
   public static String[] sortStringArray(String[] strArray, int g)
   {
      String temp = "";
      for(int a = 0; a < g; a++)
      {
         for(int b = a + 1; b < g; b++)
         {
            if(strArray[a].compareToIgnoreCase(strArray[b]) > 0)
            {
               temp = strArray[a];
               strArray[a] = strArray[b];
               strArray[b] = temp;
            }
         }
      }
      return strArray;
   }
}


Output:

Apple
Banana
Mango
Orange
Pineapple


insertion sort 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