Bubble, insertion and selection sort
Plain-English, exam-focused notes on Bubble sort, Insertion sort, and Selection sort: ideas, invariants, step-counts, stability, code, and pitfalls.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Simple sorting algorithms are the first tools you use to order small datasets, to teach program reasoning, and to compare time complexities. Engineers use them for educational baselines, for tiny inputs embedded in bigger systems (e.g., sorting a handful of sensor values), and to understand ideas like stability, loop invariants, and step-counts before learning Quick sort and Merge sort.
Key ideas
- Comparison sort: A sorting algorithm that determines order only by comparing pairs of keys using a comparison operator (like <, >, or comparator).
- Stable sort (definition): A sorting algorithm is stable if it preserves the relative order of records with equal keys. Exact statement: For any i < j with A[i].key = A[j].key, after sorting, the record originally at i appears before the record originally at j.
- In-place algorithm (definition): Uses only O(1) extra memory beyond the input array (ignoring recursion stack). Bubble, insertion, and selection sorts are in-place.
- Loop invariant (definition): A condition that is true before and after every iteration of a loop; used to prove correctness.
Bubble sort
- Idea: Repeatedly compare adjacent pairs and swap if out of order so that after each pass, the largest remaining element "bubbles up" to its final position at the end.
- Invariant (outer pass k): After pass k (1-based), the last k elements of the array are in correct non-decreasing order and are the k largest elements.
- Early-exit optimization: If a full pass makes no swaps, the array is already sorted.
- Stability: Adjacent swaps only; equal elements are never reordered, so Bubble sort is stable.
- Worst-case comparisons: n(n−1)/2. Worst-case swaps: n(n−1)/2.
Insertion sort
- Idea: Build the sorted array one element at a time by inserting the next element into its correct position among the already sorted left part.
- Invariant (at start of iteration i, 1-based indexing of positions): The subarray A[0..i−1] is sorted and consists of the original elements but in non-decreasing order.
- Mechanism: Store the key A[i], shift larger elements in A[0..i−1] one position to the right until the correct hole is found, and place the key there.
- Stability: When inserting, use a strict comparison (while A[j] > key); equal elements are not crossed, so Insertion sort is stable.
- Worst-case comparisons and moves: About n(n−1)/2 comparisons and n(n−1)/2 shifts (when the input is in reverse order). Best-case O(n) when the input is already sorted.
Selection sort
- Idea: Repeatedly select the minimum from the unsorted suffix and swap it with the first element of that suffix. After i iterations, the first i elements are in their final positions.
- Invariant (after i iterations): The prefix A[0..i−1] is sorted and consists of the i smallest elements in correct order.
- Swaps: At most n−1 swaps (swap only once per iteration, and sometimes the min is already in place so you can skip the swap).
- Comparisons: Exactly n(n−1)/2 comparisons in the classical implementation, independent of input order.
- Stability: Not stable by default, because selecting a later equal key and swapping can move it before an earlier equal key. (Stable selection sort variants exist; one approach keeps it in-place by shifting the minimum into position i instead of swapping, which preserves order but increases moves to O(n^2).)
Time complexity (asymptotic overview; see Algorithm analysis topic for proofs):
- Bubble sort: Best O(n) with early-exit; Average O(n^2); Worst O(n^2); space O(1); stable yes.
- Insertion sort: Best O(n); Average O(n^2); Worst O(n^2); space O(1); stable yes.
- Selection sort: Best O(n^2); Average O(n^2); Worst O(n^2); space O(1); stable no (default).
Step-count style derivations (commonly asked):
- Bubble sort worst-case comparisons: On pass 1, (n−1) comparisons; pass 2, (n−2); …; pass (n−1), 1. Sum = (n−1)n/2.
- Selection sort comparisons: For position 0, compare to (n−1) others; for position 1, to (n−2); …; for position (n−2), to 1. Sum = (n−1)n/2, independent of input.
- Insertion sort worst-case comparisons: For i from 1 to n−1, compare key with all i earlier elements. Sum = 1+2+…+(n−1) = (n−1)n/2.
What to draw for diagrams in exams:
- Bubble sort pass illustration: Draw a row of boxes for array elements. Above consecutive pairs, draw small bidirectional arrows showing comparisons (i.e., between box 0 and 1, 1 and 2, etc.). At the end of the row, circle the last element and label it “max after pass 1.” For pass 2, cross out the last element (now fixed), repeat arrows on the remaining unsorted prefix, circle the new last element. Label passes 1..k clearly.
- Insertion sort insertion step: Draw sorted left region [0..i−1] boxed with a bracket and labeled “sorted,” the key at position i lifted above the row, an empty “hole” at i, and backward arrows from positions j to j+1 showing shifts until the correct hole for key. Finally draw the key dropped into the hole. Label j, i, and the condition “while A[j] > key”.
- Selection sort minimum selection: Bracket the unsorted suffix [i..n−1], draw arrows from A[i] scanning right to find the min; circle the min value, and draw a swap arrow between A[i] and A[min_index]. Label i, min_index.
Assumptions behind definitions and proofs:
- Keys are from a totally ordered set; comparisons are transitive, antisymmetric, and total. Costs of comparisons and swaps/moves are considered constant (unit cost model). No duplicate-handling complications except for stability discussions.
Formulas
a[i], a[j] = a[j], a[i]— Python tuple-swap of elements at indices i and j (unitless; use in-place swaps).for i in range(n-1):— Loop for i = 0..n−2 (unitless; controls passes in bubble/selection).for j in range(0, n-1-i):— Inner loop for adjacent comparisons in bubble sort’s i-th pass.for i in range(1, n):— Outer loop for insertion sort where i is the key’s index.while j >= 0 and a[j] > key:— Insertion sort’s shift condition to ensure stability (strict >).min_index = iand update withif a[j] < a[min_index]: min_index = j— Selection of minimum in selection sort.n = int(input())anda = list(map(int, input().split()))— Read n and n space-separated integers from stdin.print(" ".join(map(str, a)))— Print the list as space-separated values.
Worked examples
- Bubble sort with early-exit flag (stable, in-place)
# Bubble sort (stable) with early-exit optimization
# Reads: n, then n integers on next line
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(0, n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
if __name__ == "__main__":
n = int(input())
a = list(map(int, input().split()))
# Optional safety: trim/extend to n
a = a[:n]
bubble_sort(a)
print("Sorted:", " ".join(map(str, a)))
Sample input
8
5 2 9 1 5 6 7 2
Exact output
Sorted: 1 2 2 5 5 6 7 9
- Insertion sort (stable, in-place)
# Insertion sort (stable)
# Reads: n, then n integers on next line
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
if __name__ == "__main__":
n = int(input())
a = list(map(int, input().split()))
a = a[:n]
insertion_sort(a)
print("Sorted:", " ".join(map(str, a)))
Sample input
8
5 2 9 1 5 6 7 2
Exact output
Sorted: 1 2 2 5 5 6 7 9
- Selection sort (default is not stable, in-place, few swaps)
# Selection sort (not stable by default)
# Reads: n, then n integers on next line
def selection_sort(a):
n = len(a)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if a[j] < a[min_index]:
min_index = j
if min_index != i:
a[i], a[min_index] = a[min_index], a[i]
if __name__ == "__main__":
n = int(input())
a = list(map(int, input().split()))
a = a[:n]
selection_sort(a)
print("Sorted:", " ".join(map(str, a)))
Sample input
8
5 2 9 1 5 6 7 2
Exact output
Sorted: 1 2 2 5 5 6 7 9
Note on stability demonstration (optional classroom check): Use records like (key, id) = [(2, 'A'), (2, 'B'), (1, 'C')]. Bubble and insertion keep A before B after sorting by key; selection may place B before A depending on swaps.
Common mistakes
- Wrong inner-loop bounds in bubble sort: using range(0, n - i) instead of range(0, n - 1 - i), leading to index out of range when accessing a[j+1].
- Using non-strict comparison in insertion sort while-shift (a[j] >= key) which breaks stability by moving equal keys past each other.
- Forgetting the early-exit flag in bubble sort’s best case, so reporting best-case time as O(n^2) instead of O(n).
- Counting swaps vs. comparisons incorrectly: selection sort has Θ(n^2) comparisons but at most n−1 swaps; bubble sort can have up to Θ(n^2) swaps; insertion sort uses shifts (moves), not swaps, so “swaps” is not the right term.
- Off-by-one at array ends: not placing key at j+1 in insertion sort after the while loop.
- Not handling n=0 or n=1 cases; loops should naturally handle them (zero passes).
For your exam
- Short notes: Compare bubble, insertion, selection sorts on time, space, and stability. Include a small 3×3 table or a neat bullet list; mention best/average/worst cases and stability.
- Derivations (step-count): Show summations for comparisons and swaps/moves. Write the series 1+2+…+(n−1) = n(n−1)/2 and justify using arithmetic progression formula.
- Programs: Write Python (or C/C++) code for any of the three. Include correct bounds, swap or shift logic, and early-exit for bubble sort if asked.
- Diagrams: For each algorithm, draw array boxes and label passes/insertions/selections as described above; neat labeled arrows and clear regions (sorted vs. unsorted) earn marks.
- Reasoning: State loop invariants and use them to argue partial correctness and termination in 4–6 lines.
Quick check
- Which of the three is not stable by default, and why?
- How many comparisons does selection sort perform in the worst case as a function of n? How many swaps at most?
- What change gives bubble sort O(n) best-case time, and what input achieves it?
Answers: (1) Selection sort, because swapping the selected minimum with position i can move a later equal key before an earlier equal key. (2) n(n−1)/2 comparisons; at most n−1 swaps. (3) Add an early-exit (swapped) flag; when the input is already sorted, it terminates after one pass.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?