What Is a Sorting Algorithm?
A sorting algorithm is a set of instructions that rearranges a list of items into a specific order ā typically ascending (smallest to largest) or descending (largest to smallest). Sorting is one of the most fundamental operations in computing, and being able to sort data efficiently is crucial for tasks ranging from displaying contacts in alphabetical order to organising millions of search results in milliseconds.
For KCSE Computer Studies, you need to understand three sorting algorithms in detail: Bubble Sort, Selection Sort and Insertion Sort. Each works differently, has different performance characteristics, and suits different situations.
Key terminology: A comparison is when two elements are checked to see which is larger. A swap is when two elements exchange positions. The number of comparisons and swaps determines how efficient a sorting algorithm is.
Bubble Sort
Bubble Sort is the simplest sorting algorithm to understand. It works by repeatedly stepping through the list, comparing adjacent pairs of elements and swapping them if they are in the wrong order. After each complete pass through the list, the largest unsorted element "bubbles up" to its correct position at the end.
The algorithm repeats this process, each time ignoring the last element (which is now sorted), until no swaps are needed in a complete pass ā at which point the list is fully sorted.
Bubble Sort ā Worked Example
Sort the array: [64, 34, 25, 12, 22]
Pass 1 (comparing all 5 elements)
Compare 64 and 34 ā 64 > 34, swap:
Compare 64 and 25 ā 64 > 25, swap:
Compare 64 and 12 ā 64 > 12, swap:
Compare 64 and 22 ā 64 > 22, swap:
After Pass 1: [34, 25, 12, 22, 64] ā 4 comparisons, 4 swaps
After Pass 2: [25, 12, 22, 34, 64]
After Pass 3: [12, 22, 25, 34, 64]
After Pass 4: [12, 22, 25, 34, 64] ā fully sorted!
Time complexity: O(nĀ²) in the worst and average case. For 5 elements, the maximum number of comparisons is 4+3+2+1 = 10. For n elements it is n(n-1)/2 comparisons.
Selection Sort
Selection Sort works by dividing the list into a sorted portion (initially empty, on the left) and an unsorted portion (initially the whole list). In each pass, it selects the smallest element from the unsorted portion and places it at the end of the sorted portion. Unlike Bubble Sort, Selection Sort makes at most one swap per pass.
Selection Sort ā Array: [64, 25, 12, 22, 11]
Pass 1: Find minimum of [64,25,12,22,11] ā 11. Swap 11 with 64:
Pass 2: Find minimum of [25,12,22,64] ā 12. Swap 12 with 25:
Pass 3: Find minimum of [25,22,64] ā 22. Swap 22 with 25:
Pass 4: Find minimum of [25,64] ā 25. Already in place, no swap needed.
Result: [11, 12, 22, 25, 64] ā 10 comparisons, only 3 swaps
Key advantage of Selection Sort over Bubble Sort: fewer swaps. This is important when swapping items is expensive (e.g. swapping large records in a database).
Insertion Sort
Insertion Sort works the way most people sort playing cards in their hand. It takes one element at a time from the unsorted portion and inserts it into its correct position in the already-sorted portion, shifting other elements along to make room.
Insertion Sort is particularly efficient when the list is already nearly sorted ā it can sort such a list in close to O(n) time.
Insertion Sort ā Array: [5, 3, 8, 1, 4]
Start: Treat first element [5] as sorted.
Step 1: Take 3. Compare with 5 ā 3 < 5, shift 5 right, insert 3:
Step 2: Take 8. Compare with 5 ā 8 > 5, insert after 5:
Step 3: Take 1. Shift 8, 5, 3 right, insert 1 at start:
Step 4: Take 4. Shift 8, 5 right, insert 4 after 3:
Result: [1, 3, 4, 5, 8] ā
Comparing the Three Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Swaps |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(nĀ²) | O(nĀ²) | Up to O(nĀ²) |
| Selection Sort | O(nĀ²) | O(nĀ²) | O(nĀ²) | O(n) ā at most 1 per pass |
| Insertion Sort | O(n) | O(nĀ²) | O(nĀ²) | Up to O(nĀ²) |
All three algorithms have O(nĀ²) worst-case performance, which makes them inefficient for large datasets. More advanced algorithms like Merge Sort and Quick Sort achieve O(n log n), but those are university-level topics.
For the KCSE syllabus, the key points are: Bubble Sort is simplest but makes many swaps; Selection Sort makes fewer swaps; Insertion Sort is best when data is nearly sorted.
KCSE Examination Tips
- When tracing a sort, always show each pass clearly with the array state after each swap or comparison.
- Count comparisons and swaps separately ā examiners often ask for one or both.
- Know which algorithm is most efficient for nearly-sorted data (Insertion Sort) and which makes the fewest swaps (Selection Sort).
- Bubble Sort's optimised version stops early if no swaps occur in a pass ā mention this if asked about efficiency improvements.
ā Watch Sorting in Action
Our Sorting Visualiser lets you step through Bubble, Selection and Insertion sort with live bar animations.
Open Sorting Visualiser ā