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:
- Start from the second element and iterate to the end of array.
- Slide all greater elements to the right by one position.
- 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:
- Compare with Selection Sort