Courses / Computer Science XI (HSSC-I) – FBISE Complete SLO-Based Course
2.3 Sorting Algorithms: Bubble Sort and Insertion Sort
Unit 2 – Computational Thinking and Algorithms · 70 min read · 9 MCQs to check yourself
Bubble sort algorithm in one minute (animation)
1. Bubble sort
Compare adjacent pairs and swap them if they are in the wrong order. After each pass the largest remaining value "bubbles" to the end. A list of n items needs at most n − 1 passes; if a pass makes no swaps, the list is sorted and we can stop early.
Model paper (6 marks): sort 10, 9, 26, 4, 1, 8, 37, 5 in ascending order using bubble sort.
| Pass | List after the pass | Swaps |
|---|---|---|
| Start | 10, 9, 26, 4, 1, 8, 37, 5 | – |
| 1 | 9, 10, 4, 1, 8, 26, 5, 37 | 5 |
| 2 | 9, 4, 1, 8, 10, 5, 26, 37 | 4 |
| 3 | 4, 1, 8, 9, 5, 10, 26, 37 | 4 |
| 4 | 1, 4, 8, 5, 9, 10, 26, 37 | 2 |
| 5 | 1, 4, 5, 8, 9, 10, 26, 37 | 1 |
| 6 | 1, 4, 5, 8, 9, 10, 26, 37 | 0 → stop, sorted |
Pass 1 in detail: (10, 9) swap → 9, 10 · (10, 26) no swap · (26, 4) swap · (26, 1) swap · (26, 8) swap · (26, 37) no swap · (37, 5) swap → 9, 10, 4, 1, 8, 26, 5, 37.
def bubble_sort(a):
n = len(a)
for p in range(n - 1):
swapped = False
for j in range(n - 1 - p):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
print("Pass", p + 1, a)
if not swapped:
break
return a
bubble_sort([10, 9, 26, 4, 1, 8, 37, 5])
Output:
Pass 1 [9, 10, 4, 1, 8, 26, 5, 37]
Pass 2 [9, 4, 1, 8, 10, 5, 26, 37]
Pass 3 [4, 1, 8, 9, 5, 10, 26, 37]
Pass 4 [1, 4, 8, 5, 9, 10, 26, 37]
Pass 5 [1, 4, 5, 8, 9, 10, 26, 37]
Pass 6 [1, 4, 5, 8, 9, 10, 26, 37]
Pseudocode:
FOR p ← 1 TO n − 1
FOR j ← 0 TO n − 1 − p
IF A[j] > A[j + 1] THEN
SWAP A[j], A[j + 1]
ENDIF
NEXT j
NEXT p
Number of comparisons in the worst case: (n-1) + (n-2) + … + 1 = (n(n-1))/2. For 8 items: 28 comparisons. To sort in descending order change > to <.
Insertion sort explained in 1 minute (visual animation)
2. Insertion sort
Build the sorted list one item at a time – like arranging playing cards in your hand. Take the next item (the key), shift larger items in the sorted part one place right, and insert the key in its correct position.
Example: sort 7, 3, 9, 1, 5
| Step | Key | List after inserting the key (sorted part in bold) |
|---|---|---|
| Start | – | 7, 3, 9, 1, 5 |
| 1 | 3 | 3, 7, 9, 1, 5 |
| 2 | 9 | 3, 7, 9, 1, 5 |
| 3 | 1 | 1, 3, 7, 9, 5 |
| 4 | 5 | 1, 3, 5, 7, 9 |
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
print("Insert", key, "->", a)
return a
insertion_sort([7, 3, 9, 1, 5])
Output:
Insert 3 -> [3, 7, 9, 1, 5]
Insert 9 -> [3, 7, 9, 1, 5]
Insert 1 -> [1, 3, 7, 9, 5]
Insert 5 -> [1, 3, 5, 7, 9]
3. Comparison and when to use each
| Basis | Bubble sort | Insertion sort |
|---|---|---|
| Idea | Swap adjacent items; largest bubbles to the end | Insert each item into the sorted part |
| Worst-case comparisons | about (n²)/2 | about (n²)/2 |
| Best case (already sorted) | n − 1 comparisons with the "no swaps" check | n − 1 comparisons |
| Swaps/moves | Many swaps | Fewer writes (shifts) |
| In practice | Simple to understand and teach; slow on large data | Faster than bubble sort; great for small or nearly sorted lists and for data arriving one item at a time |
Both are fine for small lists (a few hundred items). For large data, faster algorithms such as merge sort or quick sort (about n log₂ n steps) are used; Python's built-in sorted() uses Timsort, a mixture of merge and insertion sort.
Practical (PBA) tasks
- Modify
bubble_sortto count and print the total number of swaps. - Sort a list of student names alphabetically with insertion sort.
- Sort marks in descending order and then use binary search to find whether a mark exists (remember binary search must match the sort order!).
Insertion sort vs bubble sort with analysis
Short and long questions
1. Categorise the scenarios by identifying whether linear or binary search is the more appropriate choice, with a reason: (a) bounded data ranges (b) small data sets (c) large, sorted data sets.
Model answer
| Scenario | Search | Reason |
|---|---|---|
| Bounded data ranges | Binary | Values lie in a known, ordered range (e.g. roll numbers 1–500), so the range can be halved |
| Small data sets | Linear | Simple; the cost of sorting is not worth it for few items |
| Large, sorted data sets | Binary | Needs only about log₂ n comparisons instead of n |
2. Sort 7, 3, 9, 1, 5 using insertion sort, showing the list after every step.
Model answer
Start: 7 | 3, 9, 1, 5 Insert 3 → 3, 7 | 9, 1, 5 Insert 9 → 3, 7, 9 | 1, 5 Insert 1 → 1, 3, 7, 9 | 5 Insert 5 → 1, 3, 5, 7, 9 (sorted)
3. Compare bubble sort and insertion sort.
Model answer
| Bubble sort | Insertion sort |
|---|---|
| Repeatedly swaps adjacent items that are out of order | Takes each item and inserts it into the sorted part |
| Largest item moves to the end after each pass | Sorted part grows from the left |
| Many swaps; slow on large lists | Fewer moves; faster in practice |
| Simple to understand | Best for small or nearly sorted lists |
| Both take about n²/2 comparisons in the worst case. |
4. Sort the following numbers in ascending order using the bubble sort algorithm, showing every pass: 10, 9, 26, 4, 1, 8, 37, 5
Model answer
Bubble sort compares adjacent pairs and swaps them if the left is larger; after each pass the largest unsorted value reaches its final place.
| Pass | Result | Swaps |
|---|---|---|
| 1 | 9, 10, 4, 1, 8, 26, 5, 37 | 5 |
| 2 | 9, 4, 1, 8, 10, 5, 26, 37 | 4 |
| 3 | 4, 1, 8, 9, 5, 10, 26, 37 | 4 |
| 4 | 1, 4, 8, 5, 9, 10, 26, 37 | 2 |
| 5 | 1, 4, 5, 8, 9, 10, 26, 37 | 1 |
| 6 | 1, 4, 5, 8, 9, 10, 26, 37 | 0 – no swaps, stop |
| Pass 1 detail: 10>9 swap; 10<26; 26>4 swap; 26>1 swap; 26>8 swap; 26<37; 37>5 swap. | ||
| Sorted list: 1, 4, 5, 8, 9, 10, 26, 37. |
This lesson ends with a quiz of 9 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 2.2 Computational Thinking and Searching Algorithms · Next: Unit 2 Review, SLO Checklist and Unit Test
All lessons in Computer Science XI (HSSC-I) – FBISE Complete SLO-Based Course