BrewlearnSimple sorts in Java
Bubble, selection, insertion sort and when insertion sort wins.
Bubble sort
Bubble sort walks the array and swaps adjacent pairs that are out of order. After one full pass, the largest element has bubbled to the end. Repeat passes until nothing swaps.
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}One bubble pass
One pass of bubble sort. What does this print?
int[] a = {4, 2, 5, 1};
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
System.out.println(Arrays.toString(a));[2, 4, 1, 5][1, 2, 4, 5][2, 1, 4, 5]
Show the answer
Round 1: 4 > 2, swap: [2, 4, 5, 1]. Round 2: 4 < 5, no swap. Round 3: 5 > 1, swap: [2, 4, 1, 5]. The 5 reached the end, but the rest needs more passes.
Selection sort
Selection sort repeatedly finds the minimum of the unsorted rest and swaps it into the next slot. On [3, 4, 1, 2], round 1 finds 1 (index 2) and swaps it with index 0: [1, 4, 3, 2]. It always does about n²/2 comparisons, but at most n - 1 swaps.
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 t = a[i]; a[i] = a[min]; a[min] = t;
}Insertion sort
Insertion sort is how you sort cards in your hand: grow a sorted prefix and shift each new item left into place. Worst case (reverse order) is O(n²). But on already sorted data the inner loop never runs: O(n).
for (int i = 1; i < a.length; i++) {
int x = a[i], j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}Nearly sorted input
How many shifts does insertion sort make here?
int[] a = {1, 2, 4, 3, 5};
int shifts = 0;
for (int i = 1; i < a.length; i++) {
int x = a[i], j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j]; j--; shifts++;
}
a[j + 1] = x;
}
System.out.println(shifts);1410
Show the answer
Only the 3 has to move, sliding past the 4 once. Nearly sorted data means the inner loop barely runs, so it's close to O(n). Selection sort would still do 4 + 3 + 2 + 1 = 10 comparisons, and so would bubble sort without an early-exit check.
Stability
A sort is stable if equal elements keep their original order. Bubble and insertion sort are stable: they only move an item past a strictly greater one. Array selection sort is not: its long-distance swap can jump an item over an equal one. [2a, 2b, 1] becomes [1, 2b, 2a].
Where simple sorts still live
You'll rarely write these at work, but production sorts use insertion sort for small ranges because it's fastest there. Interviewers love asking which simple sort suits nearly sorted data (insertion) or minimizes writes (selection). Next up: merge sort, which sorts halves, then merges them.
Key takeaways
- Bubble and insertion sort are stable; array selection sort isn't
- Insertion sort's best case is O(n) on sorted input
- Selection sort always compares ~n²/2 times but swaps at most n-1
- Library sorts switch to insertion sort for small ranges
💡 Insertion sort is how you sort playing cards in your hand: slide each new card into place.
Donald Knuth wrote that bubble sort seems to have "nothing to recommend it, except a catchy name". It still appears in nearly every algorithms course.
Practice questions
What does this print?
int[] a = {5, 1, 4, 2};
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
System.out.println(Arrays.toString(a));- [1, 2, 4, 5]
- [1, 4, 2, 5]
- [1, 5, 4, 2]
- [4, 1, 2, 5]
Check your answer
[1, 4, 2, 5]. One bubble pass: 5 swaps past 1, then past 4, then past 2, ending at the back. The rest isn't sorted yet; that takes more passes.
What does this print?
int[] a = {4, 3, 1, 2};
int min = 0;
for (int j = 1; j < a.length; j++)
if (a[j] < a[min]) min = j;
int t = a[0]; a[0] = a[min]; a[min] = t;
System.out.println(Arrays.toString(a));- [1, 4, 3, 2]
- [1, 2, 3, 4]
- [3, 4, 1, 2]
- [1, 3, 4, 2]
Check your answer
[1, 3, 4, 2]. This is the first step of selection sort: find the minimum (1 at index 2) and swap it with index 0. The 4 jumps to where the 1 was.