Sorting Algorithms
Sorting is the process of arranging data in a specific order (ascending or descending). It is one of the most studied topics in computer science because sorted data enables faster searching, easier analysis, and better presentation. You need to know two algorithms in detail: Bubble Sort and Insertion Sort.
Learning Objectives
- 11.5.2.4 Apply Bubble sort and Insertion sort algorithms
Conceptual Anchor
The Playing Cards Analogy
Imagine you're holding a hand of playing cards that are out of order. Bubble Sort is like repeatedly scanning your hand from left to right, swapping any two adjacent cards that are out of order, until no more swaps are needed. Insertion Sort is like picking up one card at a time from a pile and inserting it into the correct position in your already-sorted hand.
Bubble Sort
How it works: Compare adjacent elements and swap them if they are in the wrong order. Repeat this process for the entire array. After each full pass, the largest unsorted element "bubbles up" to its correct position at the end. The algorithm stops when a complete pass is made with no swaps.
| Property | Value |
|---|---|
| Time Complexity (Best) | O(n) — already sorted, one pass with no swaps |
| Time Complexity (Worst/Average) | O(n²) — reversed array |
| Space Complexity | O(1) — in-place, only needs a temp variable |
| Stable? | Yes — equal elements maintain their relative order |
| Adaptive? | Yes — if optimized with a "swapped" flag |
Pseudocode:
PROCEDURE BubbleSort(arr : ARRAY, n : INTEGER)
DECLARE swapped : BOOLEAN
FOR i ← 0 TO n - 2
swapped ← FALSE
FOR j ← 0 TO n - 2 - i
IF arr[j] > arr[j + 1] THEN
// Swap adjacent elements
DECLARE temp : INTEGER ← arr[j]
arr[j] ← arr[j + 1]
arr[j + 1] ← temp
swapped ← TRUE
ENDIF
NEXT j
// If no swaps occurred, array is sorted
IF swapped = FALSE THEN
RETURN
ENDIF
NEXT i
ENDPROCEDUREC++:
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // Already sorted
}
}
int main() {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int n = 7;
bubbleSort(data, n);
cout << "Sorted: ";
for (int i = 0; i < n; i++) {
cout << data[i] << " ";
}
cout << endl;
return 0;
}T Trace Table — Bubble Sort on [5, 3, 8, 1, 2]
| Pass | Comparisons & Swaps | Array after pass |
|---|---|---|
| 1 | (5,3)→swap, (5,8)→no, (8,1)→swap, (8,2)→swap | [3, 5, 1, 2, 8] |
| 2 | (3,5)→no, (5,1)→swap, (5,2)→swap | [3, 1, 2, 5, 8] |
| 3 | (3,1)→swap, (3,2)→swap | [1, 2, 3, 5, 8] |
| 4 | (1,2)→no → swapped=false → STOP | [1, 2, 3, 5, 8] ✓ |
Insertion Sort
How it works: Divide the array into a "sorted" portion (initially just the first element) and an "unsorted" portion. Take the first element from the unsorted portion and insert it into its correct position in the sorted portion by shifting elements to the right.
| Property | Value |
|---|---|
| Time Complexity (Best) | O(n) — already sorted |
| Time Complexity (Worst/Average) | O(n²) — reversed array |
| Space Complexity | O(1) — in-place |
| Stable? | Yes |
| Better for | Small or nearly-sorted datasets |
Pseudocode:
PROCEDURE InsertionSort(arr : ARRAY, n : INTEGER)
FOR i ← 1 TO n - 1
DECLARE key : INTEGER ← arr[i]
DECLARE j : INTEGER ← i - 1
// Shift elements greater than key to the right
WHILE j >= 0 AND arr[j] > key
arr[j + 1] ← arr[j]
j ← j - 1
ENDWHILE
arr[j + 1] ← key
NEXT i
ENDPROCEDUREC++:
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements greater than key to the right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int n = 7;
insertionSort(data, n);
cout << "Sorted: ";
for (int i = 0; i < n; i++) {
cout << data[i] << " ";
}
cout << endl;
return 0;
}T Trace Table — Insertion Sort on [5, 3, 8, 1, 2]
| Step | Key | Action | Array |
|---|---|---|---|
| i=1 | 3 | 3 < 5 → shift 5 right, insert 3 at [0] | [3, 5, 8, 1, 2] |
| i=2 | 8 | 8 > 5 → no shift needed | [3, 5, 8, 1, 2] |
| i=3 | 1 | 1 < 8 → shift 8; 1 < 5 → shift 5; 1 < 3 → shift 3; insert 1 at [0] | [1, 3, 5, 8, 2] |
| i=4 | 2 | 2 < 8 → shift 8; 2 < 5 → shift 5; 2 < 3 → shift 3; insert 2 at [1] | [1, 2, 3, 5, 8] ✓ |
Comparison: Bubble vs Insertion
| Criterion | Bubble Sort | Insertion Sort |
|---|---|---|
| Strategy | Repeatedly swap adjacent elements | Build sorted portion by inserting |
| Best Case | O(n) with flag | O(n) |
| Worst Case | O(n²) | O(n²) |
| Swaps | Many (swap every comparison) | Fewer (shifts instead of swaps) |
| Nearly sorted data | Good (with flag) | Excellent — fewer shifts needed |
| Simplicity | Simplest to understand | Slightly more complex |
| Practical use | Teaching only | Good for small/nearly-sorted data |
Pitfalls & Common Errors
Forgetting the Optimisation Flag (Bubble Sort)
Without the swapped flag, Bubble Sort always runs O(n²) passes even if the array
becomes sorted early. In an exam, always include the flag to show you understand the
optimisation.
Inner Loop Bound in Bubble Sort
The inner loop should go to n - 1 - i, not n - 1. After each pass, the
last i elements are already in their final position, so comparing them is wasted
work.
Insertion Sort — Starting at Index 1
The outer loop must start at i = 1, not i = 0. The first element (index
0) is considered already "sorted" by itself.
Confusing Ascending vs Descending
For ascending order: swap when arr[j] > arr[j+1]. For descending: swap when
arr[j] < arr[j+1]. Read the question carefully!
Pro-Tips for Exams
How to Get Full Marks on Trace Tables
- Show every comparison and its result (swap or no swap)
- Write the complete array state after each pass
- Bold or underline the element that just moved to its final position
- State clearly when the algorithm terminates and why
Identifying the Algorithm from Code
- Two nested FOR loops with
arr[j] > arr[j+1]swap → Bubble Sort - A FOR loop with an inner WHILE loop that shifts and inserts → Insertion Sort
- If asked "which sort is this?" — look for the key variable (Insertion) vs adjacent swap (Bubble)
Graded Tasks
State the time complexity (best, worst, average) and space complexity of both Bubble Sort and Insertion Sort.
Explain why Bubble Sort is called "bubble" sort. What exactly "bubbles" and in which direction?
Perform a complete trace of Bubble Sort on the array [7, 2, 4, 1, 9, 3]. Show the array state after each full pass.
Perform a complete trace of Insertion Sort on the same array [7, 2, 4, 1, 9, 3]. Show key, shifts, and array state at each step.
A student says "Bubble Sort and Insertion Sort are essentially the same because they have the same time complexity." Argue why this statement is misleading.
Write a C++ program that implements both Bubble Sort and Insertion Sort, allows the user to choose which one to use, counts the number of comparisons and swaps performed, and displays the result.