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

  1. Modify bubble_sort to count and print the total number of swaps.
  2. Sort a list of student names alphabetically with insertion sort.
  3. 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