Mulungushi University
School of Engineering and Technology
Computer Science Department
ICT102 – Bubble Sort and Selection Sort
Due Date: 23rd April 2026, 23:59
1. Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through
the list, compares adjacent elements, and swaps them if they are in the wrong order.
This process is repeated until the list is fully sorted. With each pass, the largest unsorted
element 'bubbles up' to its correct position at the end of the list.
Key characteristics:
Compares adjacent pairs of elements and swaps if out of order.
After each pass, the largest remaining element is placed in its final position.
Requires n − 1 passes for a list of n elements.
Time complexity: O(n²) in the average and worst case; O(n) in the best case (already
sorted).
In-place algorithm – requires no extra memory.
Example – Sorting [5, 3, 8, 1]:
Pass 1: [5,3,8,1] → swap(5,3) → [3,5,8,1] → no swap → swap(8,1) → [3,5,1,8]
Pass 2: [3,5,1,8] → no swap → swap(5,1) → [3,1,5,8] → 8 in place
Pass 3: [3,1,5,8] → swap(3,1) → [1,3,5,8] → sorted!
2. Selection Sort
Selection Sort works by dividing the list into two parts: a sorted sublist built from left to
right and an unsorted sublist on the right. In each pass, it finds the minimum element in
the unsorted portion and swaps it into the next position of the sorted sublist. This
continues until the entire list is sorted.
Key characteristics:
Selects the smallest element from the unsorted sublist in each pass.
Places the selected minimum at its correct position via a single swap.
Always performs exactly n − 1 swaps regardless of input order.
Time complexity: O(n²) in all cases (best, average, worst).
In-place algorithm – requires no extra memory.
Example – Sorting [5, 3, 8, 1]:
Pass 1: Min of [5,3,8,1] = 1 → swap(5,1) → [1, 3, 8, 5]
Pass 2: Min of [3,8,5] = 3 → already in place → [1, 3, 8, 5]
Pass 3: Min of [8,5] = 5 → swap(8,5) → [1, 3, 5, 8]
Pass 4: One element left → [1, 3, 5, 8] → sorted!
3. Bubble Sort – All Passes for [15, 3, 9, 8, 5]
Starting array: [15, 3, 9, 8, 5] (n = 5, so at most 4 passes needed)
Pass 1:
Compare 15 and 3: 15 > 3 → swap → [3, 15, 9, 8, 5]
Compare 15 and 9: 15 > 9 → swap → [3, 9, 15, 8, 5]
Compare 15 and 8: 15 > 8 → swap → [3, 9, 8, 15, 5]
Compare 15 and 5: 15 > 5 → swap → [3, 9, 8, 5, 15]
Result: [3, 9, 8, 5, 15] — 15 is in its final position. Swaps: 4
Pass 2:
Compare 3 and 9: 3 < 9 → no swap
Compare 9 and 8: 9 > 8 → swap → [3, 8, 9, 5, 15]
Compare 9 and 5: 9 > 5 → swap → [3, 8, 5, 9, 15]
Result: [3, 8, 5, 9, 15] — 9 and 15 in final positions. Swaps: 2
Pass 3:
Compare 3 and 8: 3 < 8 → no swap
Compare 8 and 5: 8 > 5 → swap → [3, 5, 8, 9, 15]
Result: [3, 5, 8, 9, 15] — 8, 9, 15 in final positions. Swaps: 1
Pass 4:
Compare 3 and 5: 3 < 5 → no swap
Result: [3, 5, 8, 9, 15] — No swaps made; array is sorted! Swaps: 0
Final sorted array: [3, 5, 8, 9, 15] Total swaps: 7
4. Selection Sort – All Passes for [15, 3, 9, 8, 5]
Starting array: [15, 3, 9, 8, 5] (n = 5, so 4 passes needed)
Pass 1:
Unsorted: [15, 3, 9, 8, 5] — Scan for minimum.
Compare: 15 vs 3 → min = 3
Compare: 3 vs 9 → min = 3
Compare: 3 vs 8 → min = 3
Compare: 3 vs 5 → min = 3
Minimum is 3 (index 1) → swap(15, 3) → [3, 15, 9, 8, 5]
Result after Pass 1: [3 | 15, 9, 8, 5] Swaps: 1
Pass 2:
Unsorted: [15, 9, 8, 5] — Scan for minimum.
Compare: 15 vs 9 → min = 9
Compare: 9 vs 8 → min = 8
Compare: 8 vs 5 → min = 5
Minimum is 5 (index 4) → swap(15, 5) → [3, 5, 9, 8, 15]
Result after Pass 2: [3, 5 | 9, 8, 15] Swaps: 1
Pass 3:
Unsorted: [9, 8, 15] — Scan for minimum.
Compare: 9 vs 8 → min = 8
Compare: 8 vs 15 → min = 8
Minimum is 8 (index 3) → swap(9, 8) → [3, 5, 8, 9, 15]
Result after Pass 3: [3, 5, 8 | 9, 15] Swaps: 1
Pass 4:
Unsorted: [9, 15] — Scan for minimum.
Compare: 9 vs 15 → min = 9
Minimum is 9 (index 3) → already in position → no swap.
Result after Pass 4: [3, 5, 8, 9 | 15] Swaps: 0
Final sorted array: [3, 5, 8, 9, 15] Total swaps: 3
5. Comparison: Bubble Sort vs Selection Sort
Criterion Bubble Sort Selection Sort
Method Used Repeatedly compares Finds the minimum element
adjacent elements and swaps in the unsorted portion and
them if they are in the wrong places it at the beginning of
order. The largest element the unsorted sublist via a
bubbles to the end with each single swap per pass.
pass.
Number of Swaps High – can swap many times Low – exactly one swap per
per pass. Worst case: O(n²) pass (or zero if already in
swaps. place). Maximum n−1 swaps.
For [15,3,9,8,5]: 7 swaps For [15,3,9,8,5]: 3 swaps
total. total.
Time Complexity Best case: O(n) (already Best case: O(n²)
sorted with early termination) Average case: O(n²)
Average case: O(n²) Worst case: O(n²)
Worst case: O(n²) (No early termination
possible)
Efficiency Slightly more efficient on More efficient in terms of
nearly sorted data due to write operations (swaps).
early termination. However, Preferred when memory
the large number of swaps writes are costly. Less
makes it slower in practice for efficient than Bubble Sort on
random/large data sets. nearly sorted data since it
cannot terminate early.
In summary, both algorithms have O(n²) average/worst-case time complexity and are
suitable only for small datasets. Bubble Sort has an advantage on nearly sorted data
through early termination, but performs far more swaps. Selection Sort minimises the
number of swaps, making it preferable when write operations are expensive, though it
cannot exploit an already sorted input.