Selection Sort and Insertion Sort

Selection sort: pick the smallest

Find the smallest item and put it first. Find the smallest of the rest and put it second. And so on.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {29, 10, 14, 37, 13};
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) min = j;
            }
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
            System.out.println("place " + i + ": " + Arrays.toString(a));
        }
    }
}

Output

place 0: [10, 29, 14, 37, 13]
place 1: [10, 13, 14, 37, 29]
place 2: [10, 13, 14, 37, 29]
place 3: [10, 13, 14, 29, 37]

Always O(n²) comparisons, but at most n − 1 swaps – useful when swapping is expensive.

Insertion sort: like sorting cards in your hand

Pick up cards one at a time. Each new card slides left past the bigger cards until it's in the right place.

Think of it like this: Holding 3, 7, 9 and drawing a 5: the 9 and 7 shift right, and the 5 drops into the gap after the 3.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {7, 3, 9, 5, 1};
        for (int i = 1; i < a.length; i++) {
            int card = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > card) {   // shift bigger cards right
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = card;                  // drop the card into the gap
            System.out.println("insert " + card + ": " + Arrays.toString(a));
        }
    }
}

Output

insert 3: [3, 7, 9, 5, 1]
insert 9: [3, 7, 9, 5, 1]
insert 5: [3, 5, 7, 9, 1]
insert 1: [1, 3, 5, 7, 9]

Tip: Insertion sort is genuinely used in real life: Java's own sort switches to it for tiny pieces of an array, because for a handful of items it's the fastest.