Insertion sort in Java
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- File
InsertionSort.java, 33 lines- Level
- Toolchain
- JDK 25, JUnit 5
- Test framework
- JUnit 5
- Run the tests
javac and the JUnit console launcher
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
/** Insertion sort. */
public final class InsertionSort {
private InsertionSort() {}
/** Sorts a in place, in non-decreasing order. */
public static void sort(long[] a) {
for (int i = 1; i < a.length; i++) { // @line L1
long key = a[i]; // @line L2
int j = i - 1; // @line L3
while (j >= 0 && a[j] > key) { // @line L4
a[j + 1] = a[j]; // @line L5
j--; // @line L6
}
a[j + 1] = key; // @line L7
}
}
/** Sorts a in place by the natural order of its items. The sort is stable. */
public static <T extends Comparable<? super T>> void sort(T[] a) {
for (int i = 1; i < a.length; i++) {
T key = a[i];
int j = i - 1;
while (j >= 0 && a[j].compareTo(key) > 0) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
}
InsertionSortTest.java 40 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;
class InsertionSortTest {
@Test
void example() {
long[] a = {5, 2, 4, 6, 1, 3};
InsertionSort.sort(a);
assertArrayEquals(new long[] {1, 2, 3, 4, 5, 6}, a);
}
@Test
void edges() {
long[] e = {};
InsertionSort.sort(e);
assertArrayEquals(new long[] {}, e);
String[] w = {"pear", "fig", "apple"};
InsertionSort.sort(w);
assertArrayEquals(new String[] {"apple", "fig", "pear"}, w);
}
@Test
void randomAgainstArraysSort() {
Random rng = new Random(2150);
for (int t = 0; t < 500; t++) {
long[] a = new long[rng.nextInt(41)];
for (int i = 0; i < a.length; i++) a[i] = rng.nextInt(101) - 50;
long[] want = a.clone();
Arrays.sort(want);
InsertionSort.sort(a);
assertArrayEquals(want, a);
}
}
}
What the next level needs
- the native tests did not run in this build
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work