B2.4.3 · Programming algorithms
Sorting algorithms
By the end you can
Trace bubble sort, selection sort, and insertion sort, tracking comparisons, passes, and swap counts.
Sorting arranges elements into ascending or descending sequence. A sorted dataset enables rapid binary searching ($O(\log n)$), deduplication, and efficient rendering. The IB syllabus focuses on three fundamental comparison sorts: Bubble Sort, Selection Sort, and Insertion Sort.
1. Bubble sort#
works by repeatedly stepping through the list, comparing adjacent items (arr[j] and arr[j+1]), and swapping them if they are out of order:
- On pass 1, the largest element “bubbles up” to the last index ($n-1$).
- On pass 2, the second-largest element bubbles up to index $n-2$.
- After $n-1$ passes, the entire array is sorted.
- Optimization: If a full pass occurs without a single swap, an early exit flag terminates the algorithm in $O(n)$ time.
2. Selection sort#
divides the array into a sorted subarray on the left and an unsorted subarray on the right:
- Find the index of the minimum element in the unsorted portion.
- Swap that minimum element with the first unsorted element.
- Advance the boundary between sorted and unsorted sections by one position.
- Repeat until all elements have been selected into place.
Unlike Bubble Sort, Selection Sort performs at most $n-1$ swaps, making it advantageous when writing to memory is physically slow or expensive.
3. Insertion sort#
mimics how people sort playing cards in their hands:
- Considers the first element as a sorted sub-list of length 1.
- Takes the next unsorted element (the
key). - Compares the key with elements in the sorted sub-list from right to left, shifting larger elements one position to the right.
- Inserts the key into its correct vacant position.
- High efficiency on nearly-sorted data: Runs in linear time ($O(n)$) when data is already mostly in order.
Check yourself
Sorting algorithms
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Compare Bubble Sort, Selection Sort, and Insertion Sort by describing the core comparison mechanism and worst-case time complexity of each.
[4]Compare: Similarities and differences, about both things, point by point.
2.Explain how a boolean flag 'swapped' optimizes Bubble Sort on an already sorted array.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.Describe why insertion sort performs well on lists that are already nearly sorted.
[2]Describe: A detailed account: say what happens, step by step if it is a process.
In a nutshell
- Bubble sort repeatedly compares adjacent pairs and swaps them if out of order, bubbling the largest item to the end (O(n²)).
- Selection sort finds the minimum unsorted item and swaps it into the sorted portion, performing at most n - 1 swaps (O(n²)).
- Insertion sort inserts each element into its correct sorted position in the preceding subarray; runs in O(n) time on nearly-sorted data.
- An early-exit flag allows bubble sort to terminate in O(n) time when no adjacent swaps occur on a pass.