Insertion sort algorithm Java

Selection sort algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.

There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.

To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and implement them in Java.

So far, we have discussed the following sorting algorithms:

Today we will look at insertion sort.

Insertion sort definition

Insertion Sort is a simple and intuitive algorithm for sorting an array or list of elements. It works similarly to the method people use to sort playing cards in their hand. They keep their received cards sorted and put each new card they receive in place to maintain its relative order.

Insertion sort vs selection, quick sort, merge sort

Insertion Sort is often used as part of more complex sorting algorithms (for example, for small subsets in Quick Sort or Merge Sort) because its performance is good for small datasets. Compared to Selection Sort, which we discussed last time, it offers a stable algorithm.

Insertion sort – how it works step by step

The algorithm starts by splitting the input vector into a sorted and unsorted part. The first element of the array is automatically considered to be sorted and the remaining elements still need to be sorted. For each element in the unsorted part (from the second to the last element of the array), that element is selected and inserted at the correct location in the sorted part of the array so that the sorted part is still ordered. This step involves comparing the selected element with the other elements in the sorted part and rearranging the elements to make room for the selected element. Reshuffling can be avoided if we choose a list data type instead of an array.

We will then show a practical example in Java code.

Insertion sort advantages

  • Easy to understand and implement,
  • efficient for small datasets or nearly ordered arrays,
  • suitable for incoming elements that need to be continuously sorted,
  • does not require additional memory for sorting,
  • stable.

Insertion sort disadvantages – time complexity, intensity

  • However, the time complexity is still O(n²), which makes it a slow algorithm for a large dataset.

Insertion sort time intensity

Algorithm Method Time complexity Memory Stable
worst average best
Insertion sort definition embedding O(n²) O(n²) n O(1) Yes

Insertion sort animation, visualization, gif

The visualization of the Insertion sort looks like this:

Visualization of Insertion sort
Swfung8, CC BY-SA 4.0, via Wikimedia Commons
insertion sort visualization
Simpsons contributor, CC BY-SA 4.0, via Wikimedia Commons

Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

You can find an animation of the algorithm on Toptal. There are 8 types of algorithms, you can also play the animation backwards.

On this page you can go through the steps of the algorithm to check the time consumption of the algorithm.

Insertion sort example and Java code implementation

We will now show a simple implementation of the Insertion sort algorithm in Java.

InsertionSort.java

package sorting;

public class InsertionSort {
    private int key, j;

    public void sort(int data[])
    {
        // Start with 2nd element, as 1st is considered to be sorted
        for (int i = 1; i < data.length - 1; i++) {
            System.out.println(i + ". iteration (key = " + data[i] + ")");
            // Element that needs to be inserted into sorted part
            key = data[i];
            j = i - 1;
            // Move all elements > key one position to the right
            while (j >= 0 && key < data[j]) {
                data[j + 1] = data[j];
                j--;
            }
            // Insert the key in its correct spot
            data[j + 1] = key;
            printArray(data);
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

 

Main.java

import sorting.InsertionSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        InsertionSort insertionSort = new InsertionSort();
        System.out.print("Input: ");
        insertionSort.printArray(dataToSort);
        insertionSort.sort(dataToSort);
        System.out.print("Sorted: ");
        insertionSort.printArray(dataToSort);
    }
}

The output of this example is:

The output of this example is:

We have prepared the files with the above example in the form of code that you can run directly in Java. Download Java Insertion Sort code.

If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.

Let us know about you