JAVA-205 · Lesson 3 of 12 · 18 min
Simple sorts and their costs
▶ Video coming soon A video version of this lesson is on the way.
Binary search needs sorted data, and Java will sort for you with one call. So why learn to sort by hand? Ingrid's answer on Tuesday, September 28, 2027 is that sorting is the best laboratory there is for algorithm analysis. The simple sorts are short enough to trace on paper, they show clearly why some algorithms are quadratic, and the ideas they introduce, such as comparisons, swaps, stability and nearly sorted input, come back in every faster method. Tonight Hamza sorts the shop's parts by count by hand, three ways, and counts every comparison.
The sorting problem
To sort a list is to rearrange its elements into order by some comparison, here from the smallest count to the largest. A sort is judged by how many comparisons it makes, how many times it moves or swaps elements, how much extra memory it uses, and whether it is stable, keeping equal elements in their original order. A sort that works inside the array, using only a few extra variables, is called in-place. All three sorts in this lesson are in-place and O(n²) in the worst case.
Selection sort
Selection sort works like this: find the smallest element in the whole array and swap it into position 0. Then find the smallest of the rest and swap it into position 1, and so on. After pass i, the first i + 1 positions hold the smallest elements in order, and they never move again. Finding the smallest of k elements takes k − 1 comparisons, so the passes take (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparisons, whatever the input. It makes at most n − 1 swaps, which is its one strength.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] counts = {14, 9, 22, 6, 9, 3};
int comparisons = 0, swaps = 0;
for (int i = 0; i < counts.length - 1; i++) {
int min = i;
for (int j = i + 1; j < counts.length; j++) {
comparisons++;
if (counts[j] < counts[min]) min = j;
}
if (min != i) {
int t = counts[i]; counts[i] = counts[min]; counts[min] = t;
swaps++;
}
System.out.println("after pass " + (i + 1) + ": " + Arrays.toString(counts));
}
System.out.println("comparisons " + comparisons + ", swaps " + swaps);
}
}after pass 1: [3, 9, 22, 6, 9, 14] after pass 2: [3, 6, 22, 9, 9, 14] after pass 3: [3, 6, 9, 22, 9, 14] after pass 4: [3, 6, 9, 9, 22, 14] after pass 5: [3, 6, 9, 9, 14, 22] comparisons 15, swaps 5
What this code does
Each pass scans the unsorted part for the smallest count and swaps it to the front of that part. After the first pass the 3 has moved to position 0, and the sorted prefix grows by one each time. Six counts always take 15 comparisons, and here 5 swaps were needed.
Selection sort is not stable. A long-distance swap can jump an element over another one equal to it. With parts sorted by count, two parts that both have 9 left may end up in the opposite order from the one they started in, which matters if the list was already sorted by code and Kofi expects that order to survive within each count.
Insertion sort
Insertion sort is how many people sort a hand of cards. Keep a sorted section at the left, starting with just the first element. Take the next element, and slide it left past every larger element in the sorted section until it reaches its place, shifting those larger elements one step right to make room. Repeat until every element has been inserted.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] counts = {14, 9, 22, 6, 9, 3};
int comparisons = 0, shifts = 0;
for (int i = 1; i < counts.length; i++) {
int key = counts[i];
int j = i - 1;
while (j >= 0) {
comparisons++;
if (counts[j] <= key) break;
counts[j + 1] = counts[j];
shifts++;
j--;
}
counts[j + 1] = key;
System.out.println("inserted " + key + ": " + Arrays.toString(counts));
}
System.out.println("comparisons " + comparisons + ", shifts " + shifts);
}
}inserted 9: [9, 14, 22, 6, 9, 3] inserted 22: [9, 14, 22, 6, 9, 3] inserted 6: [6, 9, 14, 22, 9, 3] inserted 9: [6, 9, 9, 14, 22, 3] inserted 3: [3, 6, 9, 9, 14, 22] comparisons 13, shifts 11
What this code does
Each element is taken out as key and the larger elements to its left shift one place right until a smaller or equal one is found. Stopping at an equal element, with less than or equal, keeps the second 9 after the first, so the sort is stable. This input needs 13 comparisons and 11 shifts.
The cost of insertion sort depends on the input. In the worst case, a list in reverse order, every key slides all the way to the front, and the total is again about n²/2 comparisons. But in the best case, a list that is already sorted, each key is compared once with its left neighbour and stays put: n − 1 comparisons, O(n). And on a nearly sorted list, where each element is only a few places from where it belongs, the work stays close to linear. That makes insertion sort the method of choice for small or nearly sorted lists, and Java's own sort switches to it for short runs.
public class Main {
static int comparisons(int[] a) {
int count = 0;
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0) {
count++;
if (a[j] <= key) break;
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return count;
}
public static void main(String[] args) {
int n = 1000;
int[] sorted = new int[n], reversed = new int[n], nearly = new int[n];
for (int i = 0; i < n; i++) {
sorted[i] = i;
reversed[i] = n - i;
nearly[i] = i;
}
for (int i = 0; i + 1 < n; i += 50) {
int t = nearly[i]; nearly[i] = nearly[i + 1]; nearly[i + 1] = t;
}
System.out.println("already sorted: " + comparisons(sorted));
System.out.println("nearly sorted: " + comparisons(nearly));
System.out.println("reversed: " + comparisons(reversed));
}
}already sorted: 999 nearly sorted: 1018 reversed: 499500
What this code does
The same insertion sort is run on three lists of 1,000 numbers and counts its comparisons. A sorted list needs 999, one per element, and a list with 20 neighbouring pairs swapped needs only 19 more. A reversed list needs 499,500, which is n(n-1)/2.
Bubble sort
Bubble sort walks through the array comparing each pair of neighbours and swapping them when they are in the wrong order. After the first pass the largest element has bubbled to the end. Each later pass can stop one position earlier. A useful improvement is to stop as soon as a pass makes no swaps, because then the array is sorted. With that check, bubble sort takes O(n) on sorted input, but in general it is O(n²) and does far more swaps than insertion sort, so it is mainly taught, not used.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] counts = {14, 9, 22, 6, 9, 3};
int comparisons = 0, swaps = 0, passes = 0;
boolean swapped = true;
for (int end = counts.length - 1; end > 0 && swapped; end--) {
swapped = false;
passes++;
for (int i = 0; i < end; i++) {
comparisons++;
if (counts[i] > counts[i + 1]) {
int t = counts[i]; counts[i] = counts[i + 1]; counts[i + 1] = t;
swaps++;
swapped = true;
}
}
}
System.out.println(Arrays.toString(counts));
System.out.println("passes " + passes + ", comparisons " + comparisons + ", swaps " + swaps);
}
}[3, 6, 9, 9, 14, 22] passes 5, comparisons 15, swaps 11
What this code does
Each pass compares neighbours and swaps any pair that is out of order, so the largest remaining count moves to the end. The swapped flag stops the loop early once a whole pass makes no swaps. This input needs 5 passes, 15 comparisons and 11 swaps.
Comparing the three
| Sort | Best case | Worst case | Swaps or shifts | Stable? | Good for |
|---|---|---|---|---|---|
| Selection | O(n²) | O(n²) | At most n − 1 swaps | No | When writes are very expensive |
| Insertion | O(n), sorted input | O(n²) | Up to n²/2 shifts | Yes | Small or nearly sorted lists |
| Bubble with early exit | O(n), sorted input | O(n²) | Up to n²/2 swaps | Yes | Teaching |
For Second Gear's 612 parts, any of these is fast enough in practice: 612²/2 is about 187,000 comparisons. For 61,200 lines it is 1.87 billion, and that is where the O(n log n) sorts of the next lesson take over. In real programs you call Arrays.sort or List.sort, which already combine a fast general method with insertion sort for small pieces. Knowing the simple sorts helps you read that library code, choose between methods, and recognize a quadratic loop when you write one.
Stability in practice
Stability matters most when you sort records by one field after they are already in a useful order by another. Kofi's list arrives sorted by code. If he sorts it by count with a stable sort, parts with the same count stay in code order, so the printout reads naturally. JAVA-201 showed that List.sort on objects is stable. The next example sorts records by count with insertion sort, which is stable, and with selection sort, which is not.
import java.util.Arrays;
public class Main {
record Part(String code, int count) {
public String toString() { return code + ":" + count; }
}
public static void main(String[] args) {
Part[] byCode = {new Part("BELL", 9), new Part("CHAIN-11", 9), new Part("GRIPS", 4), new Part("PAD-ROAD", 2)};
Part[] a = byCode.clone();
for (int i = 1; i < a.length; i++) {
Part key = a[i]; int j = i - 1;
while (j >= 0 && a[j].count() > key.count()) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
System.out.println("insertion: " + Arrays.toString(a));
Part[] b = byCode.clone();
for (int i = 0; i < b.length - 1; i++) {
int min = i;
for (int j = i + 1; j < b.length; j++) if (b[j].count() < b[min].count()) min = j;
Part t = b[i]; b[i] = b[min]; b[min] = t;
}
System.out.println("selection: " + Arrays.toString(b));
}
}insertion: [PAD-ROAD:2, GRIPS:4, BELL:9, CHAIN-11:9] selection: [PAD-ROAD:2, GRIPS:4, CHAIN-11:9, BELL:9]
What this code does
Both sorts order the four parts by count. Insertion sort keeps BELL before CHAIN-11, as they were in the code order. Selection sort's first swap moves BELL from the front to where PAD-ROAD was, past CHAIN-11, so the two parts with 9 come out in the wrong code order.
Try it yourself
Count the shifts
The starter sorts with insertion sort but does not count anything. Add a counter so the program prints the number of **shifts** (moves of an element one place to the right) after sorting.
For the counts {5, 1, 4, 2, 3} the program should print [1, 2, 3, 4, 5] and then shifts: 6.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 3};
int shifts = 0;
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
System.out.println(Arrays.toString(a));
System.out.println("shifts: " + shifts);
}
}Try it yourself
Bubble sort that stops early
Complete the bubble sort so that it stops as soon as a pass makes no swaps, and prints how many passes it made.
For {2, 1, 3, 4, 5} it should print [1, 2, 3, 4, 5] and passes: 2.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a = {2, 1, 3, 4, 5};
int passes = 0;
for (int end = a.length - 1; end > 0; end--) {
passes++;
for (int i = 0; i < end; i++) {
if (a[i] > a[i + 1]) {
int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
}
}
}
System.out.println(Arrays.toString(a));
System.out.println("passes: " + passes);
}
}Common mistakes
MistakeAssuming a sort that is fast on test data is fast in general.
InsteadCheck its worst case; insertion sort is linear on sorted input but quadratic on reversed input.
MistakeUsing selection sort when equal elements must keep their order.
InsteadUse a stable sort such as insertion sort or List.sort.
MistakeWriting a simple sort for a large list in production code.
InsteadCall Arrays.sort or List.sort, which are O(n log n).
MistakeForgetting the early exit in bubble sort.
InsteadStop when a pass makes no swaps.
MistakeUsing < instead of <= when insertion sort compares with the key.
InsteadStopping at equal elements keeps the sort stable.
Summary and key terms
- Sorting rearranges elements into order, and sorts are judged by comparisons, moves, extra memory and stability.
- Selection sort repeatedly selects the smallest remaining element and swaps it into place; it always makes n(n − 1)/2 comparisons, at most n − 1 swaps, and is not stable.
- Insertion sort grows a sorted section by sliding each new key left past larger elements; it is stable, O(n²) in the worst case but O(n) on sorted input and close to linear on nearly sorted input, so it is used for small and nearly sorted lists.
- Bubble sort swaps neighbouring pairs and, with an early exit, stops when a pass makes no swaps, but it does many swaps and is mainly a teaching example.
- For large lists use the O(n log n) library sorts.
- Sort
- To rearrange elements into order by a comparison.
- Comparison
- A single test of whether one element should come before another.
- Swap
- Exchanging the positions of two elements.
- In-place sort
- A sort that needs only a constant amount of extra memory.
- Stable sort
- A sort that keeps equal elements in their original relative order.
- Selection sort
- A sort that repeatedly moves the smallest remaining element to the front.
- Insertion sort
- A sort that inserts each element into a growing sorted section.
- Bubble sort
- A sort that repeatedly swaps neighbouring elements that are out of order.
- Nearly sorted
- A list in which each element is only a few places from its sorted position.
Practice problems
Work each problem on paper first, then reveal the answer to check.
How many comparisons does selection sort make on 10 elements?
Show answer
45, which is 10 × 9 / 2.
How many comparisons does insertion sort make on 10 elements that are already sorted?
Show answer
9.
Which of the three simple sorts is not stable?
Show answer
Selection sort.
Why is insertion sort used inside Java's library sort?
Show answer
It is fast for small and nearly sorted pieces.
What lets bubble sort stop early?
Show answer
A pass that makes no swaps means the array is sorted.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.