Java Programming Tutorials

Java programming tutorials with many code examples!

Insertion Sort in Java

Insertion Sort in Java

Insertion Sort is another simple to understand and implement algorithm. Unlike Selection Sort it can work faster with certain data.

How it works

The algorithm is very simple:

  1. Start from the second element and iterate to the end of array.
  2. Slide all greater elements to the right by one position.
  3. Insert the element from #1 into empty space made by #2.

Insertion Sort properties

  • the worst case (array sorted in reverse order) running time is ϴ(n²) (Big Theta n²)
  • the best case (sorted array) running time is ϴ(n) (Big Theta n²)
  • memory complexity in O(1), because the algorithm reuses the same array.

Insertion Sort implementation

package com.farenda.tutorials.algorithms.sorting;

public class InsertionSorter {

    public void sort(int[] values) {
        for (int i = 1; i < values.length; ++i) {
            insert(values, i-1, values[i]);
        }
    }

    private void insert(int[] array, int rightIndex, int value) {
        while (0 <= rightIndex && value < array[rightIndex]) {
            array[rightIndex+1] = array[rightIndex];
            --rightIndex;
        }
        array[rightIndex+1] = value;
    }
}

Unit tests

Let’s verify the implementation with a few JUnit tests:

package com.farenda.tutorials.algorithms.sorting;

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class InsertionSortTest {

    private InsertionSorter sorter = new InsertionSorter();

    @Test
    public void shouldDoNothingWithEmptyArray() {
        int[] values = {};

        sorter.sort(values);
    }

    @Test
    public void shouldDoNothingWithOneElementArray() {
        int[] values = {42};

        sorter.sort(values);

        assertArrayEquals(new int[] {42}, values);
    }

    @Test
    public void shouldSortValues() {
        int[] values = { 9, -3, 5, 0, 1};
        int[] expectedOrder = { -3, 0, 1, 5, 9};

        sorter.sort(values);

        assertArrayEquals(expectedOrder, values);
    }
}

References:

Share with the World!