Insertion Sort In Java

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

Insertion Sort

Insertion sort is a sorting algorithm that forms final sorted array ( one each at a time).

It is one of the simplest sorting algorithm compared to advanced sorting algorithms, namely heapsort and quicksort.

Also Read – Bubble Sort Java Program

Java insertion sort is useful for small sets. Also it is not a fast algorithm, because it uses nested loop to shift items into place.

Let’s see insertion sort algorithm java,

INSERTION SORT IN JAVA EXAMPLE

Here we are going to learn insertion sort java algorithm using scanner class,

import java.util.Scanner;

public class InsertionSort
{
   public static void sortInsertion(int arr[])
   {
      int a = arr.length;
      int x;
      int y;
      int temp;

      for(x = 1; x < a; x++)
      {
         y = x;
         temp = arr[x];

         while(y > 0 && temp < arr[y - 1])
         {
            arr[y] = arr[y - 1];
            y = y - 1;
         }
         arr[y] = temp;
      }
   }

   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      System.out.println("Insertion Sort in Java");
      int b;
      int c;

      System.out.println("Please enter number of integer elements: ");
      b = sc.nextInt();
      int arr[] = new int[b];
      System.out.println("Please enter " + b + " integer elements");

      for(c = 0; c < b; c++)
         arr[c] = sc.nextInt();

      sortInsertion(arr);

      System.out.println("Integer elements after sorting");

      for(c = 0; c < b; c++)
         System.out.print(arr[c] + " ");
         System.out.println();
   }
}

Output:

Insertion Sort In Java

As you can see in the above example in every iteration insertionsort java separates an element from input and inserts it into the correct position until all elements are sorted.

In the above example the selection of which element to remove from input is random.


without using scanner class

Let’s learn insertion sort implementation without using scanner class,

public class InsertionSort
{
   public static void main(String[] args)
   {
      int[] arr = { 5, 3, 10, 7, 24, 13, 35, 0, 2 };
      sortInsertion(arr);
   }
 
   private static void printSorted(int[] data)
   { 
      for(int i = 0; i < data.length; i++)
      {
         System.out.print(data[i] + " , ");
      }
      System.out.println("\n");
   }
 
   public static void sortInsertion(int array[])
   {
      int a = array.length;
      for(int b = 1; b < a; b++)
      {
         int temp = array[b];
         int c = b - 1;
         while ( (c > -1) && ( array [c] > temp ) )
         {
            array [c + 1] = array [c];
            c--;
         }
         array[c + 1] = temp;
         printSorted(array);
      }
   }
}

Output:

3 , 5 , 10 , 7 , 24 , 13 , 35 , 0 , 2 ,

3 , 5 , 10 , 7 , 24 , 13 , 35 , 0 , 2 ,

3 , 5 , 7 , 10 , 24 , 13 , 35 , 0 , 2 ,

3 , 5 , 7 , 10 , 24 , 13 , 35 , 0 , 2 ,

3 , 5 , 7 , 10 , 13 , 24 , 35 , 0 , 2 ,

3 , 5 , 7 , 10 , 13 , 24 , 35 , 0 , 2 ,

0 , 3 , 5 , 7 , 10 , 13 , 24 , 35 , 2 ,

0 , 2 , 3 , 5 , 7 , 10 , 13 , 24 , 35 ,


using objects

Here we will learn how to implement insertion sort in java using objects,

public class InsertionSortDemo
{
   void sortInsertion(int arr[])
   {
      int x = arr.length;
      for(int a = 1; a < x; ++a)
      {
         int key = arr[a];
         int b = a - 1;
 
         while (b >= 0 && arr[b] > key)
         {
            arr[b + 1] = arr[b];
            b = b - 1;
         }
         arr[b + 1] = key;
      }
   }
 
   static void printArray(int arr[])
   {
      int y = arr.length;
      for(int m = 0; m < y; ++m)
         System.out.print(arr[m] + " ");
 
      System.out.println();
   }
 
   public static void main(String[] args)
   {
      int arr[] = { 5, 3, 10, 7, 24 }; 
      InsertionSortDemo isd = new InsertionSortDemo(); 
      isd.sortInsertion(arr); 
      printArray(arr);
   }
}

Output:

3 5 7 10 24


using recursion

Now we will see how insertion sort works using recursion,

import java.util.Arrays;

public class InsertionSortRecursion
{
   static void sortInsertion(int arr[], int a)
   {
      if(a <= 1)
         return;
 
      // Here we are sorting first a - 1 elements
      sortInsertion( arr, a - 1 );
 
      int last = arr[a - 1];
      int b = a - 2;
 
      while(b >= 0 && arr[b] > last)
      {
         arr[b + 1] = arr[b];
         b--;
      }
      arr[b + 1] = last;
   }
 
   public static void main(String[] args)
   {
      int arr[] = { 5, 3, 10, 7, 24 }; 
      sortInsertion(arr, arr.length); 
      System.out.println(Arrays.toString(arr));
   }
}

Output:

[3, 5, 7, 10, 24]


conclusion

That’s it guys. This was all about insertion sort java code with example of insertion sort.

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.

You May Also Like