Insertion Sort in JAVA

This tutorial will focus on Insertion Sort in Java and the implementation of insertion sort.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

‘Insertion Sort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,8,2,4}

  1. Compare the 2nd element with the 1st element and change their positions to sort in ascending (or descending) order if the 1st element is lesser (or greater) than the 2nd element
    1<8, hence no swappingso array ->{1,8,2,4}
  2. Compare the 3rd element with the elements before it and change its position with the element that is greater (or smaller) than it and closest to the beginning of the array
    2<8 but 1<2, hence 2 and 8 are swapped, so array -> {1,2,8,4}
  3. Compare the ith element with the elements before it and change its position with the element that is greater (or smaller) than it and closest to the beginning of the array (note, ‘i’ takes values up till the length of the array)
    4<8 but 4<2, hence 4 and 8 are swapped, so array -> {1,2,4,8}
    Hence, the sorted array is -> {1,2,4,8}

Code to implement insertion sort in Java

import java.util.Scanner;
class InsertionSort{
void inputArray(int array[],int length)
 {
     Scanner scan=new Scanner(System.in);
     System.out.print("Input "+length+" (integer) elements: ");
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        array[length]=scan.nextInt();
     }
 }
void printArray(int array[],int length)
 {
     System.out.print("The elements of the given array are: ");
     for(int i=0;i<length;i++)System.out.print(array[i]+" ");
 }
//logic for insertion sort - treat the array like a deck of cards and place every element at position 'i' after comparing it with all the elements before it
 void insertionSort(int array[],int length)
  {
    for(int i=1;i<length;i++){
      int temporary=array[i];
      int j;
//note, at every 'i' iteration of the first for loop, all successive elements before position 'i' which are greater than the element at position 'i' are being  pushed forward by one position and the gap which is created, then contains the element at position 'i'
      for(j=i-1;j>=0 && array[j]>temporary;j--){
        array[j+1]=array[j];
      }
      array[j+1]=temporary;
    }
  }
public static void main(String args[])
{
    InsertionSort ob = new InsertionSort();
    int array[]=new int[4];//creating an integer array
    ob.inputArray(array,4);//taking input in the array
    ob.insertionSort(array,4);//sorting the array with the desired sorting algorithm
    ob.printArray(array,4);//printing the array after sorting
}
}//class ends

Output:

Input 4 (integer) elements: 1 8 2 4
The elements of the given array are: 1 2 4 8

Explanation of insertion sort program

  • an object ‘ob’ of the class is created to call the required functions
  • an array ‘array[]’ is initialized with length 4
  • ob.inputArray(int[],int) is called to take input integer elements from the user and store them in the array
  • ob.insertionSort(int[],int) is called to sort the elements of the array with the algorithm explained above
  • ob.printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

  • the value ‘4’ can be changed to any other value in order to get the desired array-length
  • since (in JAVA) arrays are passed by reference, therefore the changes made in insertionSort(int[],int) stay permanently
  • to sort in descending order, just change the sign from ‘>’ to ‘<‘ in the second logical condition of the 2nd for loop

You may also learn:

Leave a Reply

Your email address will not be published. Required fields are marked *