Sorting Algorithms
IB Syllabus: B2.4.3: Construct and trace algorithms to implement a bubble sort and a selection sort, evaluating their time and space complexities. Evaluate the advantages and disadvantages of each sorting algorithm across various data sets.
Table of Contents
- Key Concepts
- Bubble Sort
- Selection Sort
- Sorting Strings with .compareTo()
- Bubble Sort vs Selection Sort
- Combined Exercises
- GitHub Classroom
- Connections
Key Concepts
A sorting algorithm rearranges elements in an array into a specific order (ascending or descending). The two sorting algorithms required for IB are:
| Bubble Sort | Selection Sort | |
|---|---|---|
| Strategy | Repeatedly swap adjacent elements that are out of order | Find the smallest element and move it to the correct position |
| Passes | Up to n−1 passes over the array | Exactly n−1 passes |
| Can stop early? | Yes, with optimisation flag | No, always does all passes |
| Time complexity | O(n²) worst/average, O(n) best (optimised) | O(n²) in all cases |
| Space complexity | O(1) — sorts in place | O(1) — sorts in place |
Both algorithms sort in place, meaning they rearrange the original array without creating a new one. This gives them O(1) space complexity — they only need a few extra variables regardless of array size.
Quick String Reminder: The examples on this page sort
intarrays with<and>. When sortingStringarrays, use.compareTo()instead: it returns a negative number if the first string comes before the second alphabetically, zero if equal, and a positive number if it comes after. See the Sorting Strings section below, or the full reference in Strings.
Bubble Sort
How It Works
Bubble sort compares adjacent elements and swaps them if they are in the wrong order. After each complete pass through the array, the largest unsorted element “bubbles up” to its correct position at the end.
Pass 1 — the largest value (8) bubbles to the end:
[5, 3, 8, 1, 2]
↕ ↕ 5 > 3? Yes → swap
[3, 5, 8, 1, 2]
↕ ↕ 5 > 8? No
[3, 5, 8, 1, 2]
↕ ↕ 8 > 1? Yes → swap
[3, 5, 1, 8, 2]
↕ ↕ 8 > 2? Yes → swap
[3, 5, 1, 2, 8] ✓ 8 is now in its final position
Each pass places one more element in its final position, so each subsequent pass has one fewer element to check.
Key observations:
- After pass 1, the largest element is at the end
- After pass 2, the two largest elements are in place
- After pass k, the k largest elements are in place
- Maximum n−1 passes needed for n elements
Java Code (Inline in Main)
int[] arr = {64, 34, 25, 12, 22, 11, 90};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// Print sorted array
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
Output:
11 12 22 25 34 64 90
The inner loop goes to
n - 1 - i, notn - 1. After each pass, the lastielements are already sorted, so there is no need to compare them again. This is an important optimisation that students often miss.
Optimised Bubble Sort (Early Exit)
If no swaps occur during a pass, the array is already sorted and we can stop early. This is achieved with a boolean flag:
int[] arr = {64, 34, 25, 12, 22, 11, 90};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break; // Array is sorted, no need to continue
}
}
The
swappedflag makes bubble sort’s best case O(n) — if the array is already sorted, only one pass is needed with zero swaps, and the algorithm stops. Without the flag, bubble sort always makes n−1 passes even on sorted data.
Trace: Bubble Sort {5, 3, 8, 1, 2}
| Pass | Comparisons | Swaps | Array After Pass |
|---|---|---|---|
| 1 | (5,3) (5,8) (8,1) (8,2) | 5↔3, 8↔1, 8↔2 | [3, 5, 1, 2, 8] |
| 2 | (3,5) (5,1) (5,2) | 5↔1, 5↔2 | [3, 1, 2, 5, 8] |
| 3 | (3,1) (3,2) | 3↔1, 3↔2 | [1, 2, 3, 5, 8] |
| 4 | (1,2) | None | [1, 2, 3, 5, 8] ✓ |
Total comparisons: 4 + 3 + 2 + 1 = 10. Total swaps: 7.
Complexity Analysis
| Case | Time | When it happens |
|---|---|---|
| Best | O(n) | Array already sorted (with swapped flag — one pass, no swaps) |
| Average | O(n²) | Random order |
| Worst | O(n²) | Reverse sorted — every pair must be swapped |
| Space | O(1) | Only uses temp, i, j, swapped — constant extra memory |
The number of comparisons in the worst case is n(n−1)/2. For example, with 5 elements: 4 + 3 + 2 + 1 = 10 comparisons. This is because the outer loop runs n−1 times, and the inner loop runs n−1−i times for each pass. The sum 1 + 2 + … + (n−1) = n(n−1)/2, which simplifies to O(n²).
Bubble Sort Quick Check
Q1. What does bubble sort compare on each step?
Q2. After the first pass of bubble sort on {7, 2, 5, 1, 9, 3}, which element is guaranteed to be in its correct position?
Q3. What is the purpose of the swapped flag in optimised bubble sort?
Q4. What is the space complexity of bubble sort?
Bubble Sort Trace Exercise
Trace bubble sort on {6, 3, 8, 2}. Fill in the array state after each pass.
| Pass | Position 0 | Position 1 | Position 2 | Position 3 | Swaps made |
|---|---|---|---|---|---|
| Start | 6 | 3 | 8 | 2 | — |
| 1 | |||||
| 2 | 8 | ||||
| 3 | 6 | 8 |
Bubble Sort Code Completion
Complete the bubble sort code that sorts an array in ascending order.
This algorithm makes multiple passes through the array, swapping adjacent elements that are out of order. The inner loop shrinks each pass because the largest elements accumulate at the end.
int[] arr = {42, 15, 8, 23, 4};
int n = arr.length;
for (int i = 0; i < ; i++) {
for (int j = 0; j < ; j++) {
if (arr[j] > ) {
int temp = arr[j];
arr[j] = arr[j + 1];
;
}
}
}
Bubble Sort Spot the Bug
This bubble sort runs but is inefficient — it re-checks elements that are already sorted. Click the buggy line, then pick the fix.
Pick the correct fix for line 4:
Bubble Sort Output Prediction
This optimised bubble sort counts how many passes it takes. What is the exact output?
int[] arr = {4, 1, 3, 2};
int n = arr.length;
int passes = 0;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
passes++;
if (!swapped) { break; }
}
System.out.println("Passes: " + passes);Type your answer:
Bubble Sort Practice
-
Trace on Paper. Trace bubble sort on
{9, 5, 1, 4, 3}. For each pass, write the array state and count the number of swaps. How many total passes are needed? -
Already Sorted. Run the optimised bubble sort (with
swappedflag) on{1, 2, 3, 4, 5}. How many passes does it make? How many comparisons? Explain why this is the best case. -
Reverse Sorted. Trace bubble sort on
{5, 4, 3, 2, 1}. Count the total number of comparisons and swaps. This is the worst case — explain why. -
Descending Order. Modify the bubble sort code so it sorts in descending order (largest to smallest). Only one character needs to change.
Selection Sort
How It Works
Selection sort divides the array into a sorted part (left) and an unsorted part (right). On each pass, it finds the smallest element in the unsorted part and swaps it with the first unsorted element.
Pass 1 — find the smallest in the whole array, swap with position 0:
[5, 3, 8, 1, 2] min = 1 (index 3)
↕ ↕ swap arr[0] with arr[3]
[1, 3, 8, 5, 2] ✓ Position 0 is final
─
Pass 2 — find the smallest in positions 1–4, swap with position 1:
[1, 3, 8, 5, 2] min = 2 (index 4)
↕ ↕ swap arr[1] with arr[4]
[1, 2, 8, 5, 3] ✓ Positions 0–1 are final
─ ─
Pass 3 — find the smallest in positions 2–4, swap with position 2:
[1, 2, 8, 5, 3] min = 3 (index 4)
↕ ↕ swap arr[2] with arr[4]
[1, 2, 3, 5, 8] ✓ Positions 0–2 are final
─ ─ ─
Pass 4 — find the smallest in positions 3–4:
[1, 2, 3, 5, 8] min = 5 (index 3), already in place
─ ─ ─ ─ ─ ✓ Done!
Key observations:
- Each pass makes exactly one swap (or none if the minimum is already in position)
- After k passes, the first k elements are in their final sorted positions
- Always requires exactly n−1 passes — cannot stop early
Java Code (Inline in Main)
int[] arr = {64, 25, 12, 22, 11};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum with the first unsorted element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
// Print sorted array
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
Output:
11 12 22 25 64
The inner loop starts at
i + 1, not0. We only search the unsorted portion of the array — everything before indexiis already sorted and in its final position.
Trace: Selection Sort {64, 25, 12, 22, 11}
| Pass (i) | Unsorted portion | Min value | Min index | Swap | Array after |
|---|---|---|---|---|---|
| 0 | [64, 25, 12, 22, 11] | 11 | 4 | arr[0] ↔ arr[4] | [11, 25, 12, 22, 64] |
| 1 | [25, 12, 22, 64] | 12 | 2 | arr[1] ↔ arr[2] | [11, 12, 25, 22, 64] |
| 2 | [25, 22, 64] | 22 | 3 | arr[2] ↔ arr[3] | [11, 12, 22, 25, 64] |
| 3 | [25, 64] | 25 | 3 | arr[3] ↔ arr[3] | [11, 12, 22, 25, 64] |
Total comparisons: 4 + 3 + 2 + 1 = 10. Total swaps: 4 (one per pass).
Complexity Analysis
| Case | Time | When it happens |
|---|---|---|
| Best | O(n²) | Always — still scans the entire unsorted portion |
| Average | O(n²) | Random order |
| Worst | O(n²) | Reverse sorted (same number of comparisons) |
| Space | O(1) | Only uses minIndex, temp, i, j — constant extra memory |
Unlike bubble sort, selection sort has no best case improvement. Even if the array is already sorted, it still makes n(n−1)/2 comparisons to verify. However, it makes at most n−1 swaps (one per pass), compared to bubble sort’s potential O(n²) swaps. This makes selection sort better when swaps are expensive (e.g., moving large records).
Selection Sort Quick Check
Q1. What does selection sort do on each pass?
Q2. What is the best-case time complexity of selection sort?
Q3. After 3 passes of selection sort on an array of 8 elements, how many elements are in their final position?
Q4. Why might selection sort be preferred over bubble sort when sorting large records (objects with many fields)?
Selection Sort Trace Exercise
Trace selection sort on {7, 4, 10, 3}. Fill in the minimum found and the array state after each pass.
| Pass (i) | Min value | Min index | Pos 0 | Pos 1 | Pos 2 | Pos 3 |
|---|---|---|---|---|---|---|
| Start | — | — | 7 | 4 | 10 | 3 |
| 0 | ||||||
| 1 | 3 | |||||
| 2 | 3 | 4 |
Selection Sort Code Completion
Complete the selection sort code that sorts an array in ascending order.
This algorithm finds the minimum element in the unsorted portion and swaps it into the correct position. The variable minIndex tracks where the smallest unsorted element is found.
int[] arr = {38, 27, 43, 3, 9};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = ;
for (int j = ; j < n; j++) {
if (arr[j] < ) {
minIndex = ;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
Selection Sort Spot the Bug
This selection sort produces a sorted result but contains an error in its search range. Click the buggy line, then pick the fix.
Pick the correct fix for line 5:
Selection Sort Output Prediction
This code counts the number of actual swaps (where the minimum was not already in position). What is the exact output?
int[] arr = {8, 3, 6, 1};
int n = arr.length;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
swaps++;
}
}
System.out.println("Swaps: " + swaps);Type your answer:
Selection Sort Practice
-
Trace on Paper. Trace selection sort on
{29, 10, 14, 37, 13}. For each pass, record the minimum found, its index, and the array state after the swap. -
Count Comparisons. Add a comparison counter to the selection sort code and run it on an array of 6 elements. Verify that the total is n(n−1)/2 = 15 comparisons.
-
Swap Counter. Modify selection sort to count and print the number of swaps. Run it on
{1, 2, 3, 4, 5}(already sorted) and{5, 4, 3, 2, 1}(reverse sorted). How do the swap counts compare? Why? -
Find Maximum Instead. Modify selection sort to find the maximum element on each pass and place it at the end of the unsorted portion (sorting from right to left instead of left to right).
Sorting Strings with .compareTo()
When sorting String arrays, you cannot use < or > — these only work with primitive types. Instead, use .compareTo():
a.compareTo(b) > 0meansacomes afterbalphabetically (equivalent toa > bfor numbers)a.compareTo(b) < 0meansacomes beforeba.compareTo(b) == 0means they are equal
String[] names = {"Charlie", "Alice", "Eve", "Bob", "Diana"};
int n = names.length;
// Bubble sort for Strings
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (names[j].compareTo(names[j + 1]) > 0) {
String temp = names[j];
names[j] = names[j + 1];
names[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
System.out.print(names[i] + " ");
}
Output:
Alice Bob Charlie Diana Eve
The only change from sorting integers is replacing
arr[j] > arr[j + 1]withnames[j].compareTo(names[j + 1]) > 0. The swap logic stays exactly the same. This applies to both bubble sort and selection sort.
For a full reference on .compareTo() and other String methods, see Strings.
Bubble Sort vs Selection Sort
| Feature | Bubble Sort | Selection Sort |
|---|---|---|
| Strategy | Swap adjacent pairs | Find minimum, place it |
| Comparisons (worst) | n(n−1)/2 | n(n−1)/2 |
| Swaps (worst) | n(n−1)/2 | n−1 |
| Best-case time | O(n) with flag | O(n²) — no improvement |
| Worst-case time | O(n²) | O(n²) |
| Space | O(1) | O(1) |
| Adaptive? | Yes — faster on nearly sorted data | No — same work regardless |
| Stable? | Yes — equal elements keep original order | No — swapping can change order of equals |
When to choose bubble sort:
- Data is nearly sorted or already sorted (benefits from early exit)
- Stability matters (preserving relative order of equal elements)
When to choose selection sort:
- Swaps are expensive (e.g., large records) — at most n−1 swaps
- Consistent performance is preferred over best-case optimisation
Both algorithms have O(n²) worst-case time, which makes them impractical for large datasets. For large data, algorithms like quicksort (O(n log n) average) are far more efficient — covered in the HL section on Quicksort.
Combined Exercises
These exercises require you to compare or use both sorting algorithms.
Combined Quick Check
Q1. Which sorting algorithm performs better on an already sorted array?
Q2. A developer needs to sort 1,000,000 records. Why are bubble sort and selection sort poor choices?
Q3. Sorting an array of large student record objects (name, grades, address, etc.). Which algorithm is likely faster and why?
Combined Practice
-
Sort and Compare. Write a program that creates the array
{50, 23, 9, 18, 61, 32}. Sort a copy with bubble sort and another copy with selection sort. For each, count and print the number of comparisons and swaps. Which algorithm made more swaps? - Nearly Sorted vs Random. Test both algorithms on these two arrays:
- Nearly sorted:
{1, 2, 4, 3, 5, 6, 8, 7} - Random:
{45, 12, 78, 3, 56, 22, 91, 8}Count comparisons and swaps for each. Which algorithm benefits more from nearly sorted data?
- Nearly sorted:
-
Sort Strings. Given
String[] fruits = {"Mango", "Apple", "Cherry", "Banana", "Date"}, use selection sort with.compareTo()to sort alphabetically. Trace the first two passes on paper before coding. - Algorithm Choice. For each scenario, choose bubble sort or selection sort and justify:
- (a) Sorting 10 nearly-sorted quiz scores
- (b) Sorting 100 student records (each record is a large object)
- (c) Sorting an array that is completely reversed
- (d) Sorting a small array of 5 elements
-
Scaling Comparison. Fill in this table:
Array size (n) Worst-case comparisons Time for bubble sort (O(n²)) Time for quicksort (O(n log n)) 10 ? ? ? 100 ? ? ? 1,000 ? ? ? 1,000,000 ? ? ? Assume each comparison takes 1 microsecond. Express answers in appropriate units (microseconds, milliseconds, seconds, minutes).
GitHub Classroom
Codespace Setup Instructions (click to expand)
First Time Setup
- Click “Open in GitHub” above, then click the green “Accept this assignment” button
- Wait for your repository to be created, then click “Open in Codespace”
- Wait for the Codespace to finish loading (you’ll see VS Code in your browser)
Important: Switch to Standard Mode
- Look at the bottom status bar. If it says
Java: Lightweight Mode, click on it and select Standard - Wait for Java to finish loading (status bar will say
Java: Ready) - Without Standard Mode, the Run button won’t work and you’ll get “Main method not found” errors
Dismiss Popups
You’ll see two notification popups. Dismiss them both:
- “Would you like VS Code to periodically run git fetch?” → Click No
- “There’s a pull request associated with main” → Click Don’t Show Again
These are housekeeping popups, not part of the assignment.
How to Code
- Open
src/Sorting.java. This is the only file you need to edit - Complete each
// TODOsection - Click the Run button (▶ above
main) to test your output - Compare your output with the expected output written in the comments above each task
How to Check Your Code
You can check your work in two ways:
Option A: Run your code directly
- Click the Run button (▶) above
maininSorting.java - Compare your printed output with the expected output shown in the comments above each task
Option B: Run the autograder tests
- Open the Terminal (Menu → Terminal → New Terminal)
- Type
bash run-tests.shand press Enter - Green ✓ = test passed, Red ✗ = test failed
- Each test tells you what it expected. Read the error message to fix your code
How to Submit
- Click the Source Control icon (branch icon) in the left sidebar
- Type a message like
completed tasksin the message box - Click the green Commit button
- If asked “stage all changes?” → click Always
- Click Sync Changes → if asked about push/pull → click OK, Don’t Show Again
- Done! Autograding runs automatically. Your teacher can see your results in the GitHub Classroom dashboard
How to Review Feedback
- Go to your repository on GitHub
- Click the “Pull requests” tab at the top
- Open the pull request called “Feedback”
- Click the “Files changed” tab. You’ll see your teacher’s comments on specific lines of your code
- Read through each comment carefully, then fix your code in Codespaces
- Run
bash run-tests.shin your Codespaces Terminal to check your fixes - Commit and push again (repeat steps 11-16). The autograder will re-run automatically
Connections
- Prerequisites: 1D Arrays (the data structure being sorted), Iteration (nested loops drive both algorithms), Selection (if statements for comparisons)
- Related: Searching Algorithms (binary search requires sorted data — sorting enables faster searching)
- Forward: After covering Methods (B2.3.4), both sort algorithms will be refactored into reusable methods
- HL: Quicksort — an O(n log n) average-case algorithm that is far more efficient than O(n²) sorts on large data
- Big O Notation will formalise the complexity analysis introduced here