Bubble Sort

Mechanism

Bubble Sort repeatedly steps through the array, comparing each pair of adjacent elements and swapping them if they're in the wrong order. Each full pass "bubbles" the largest remaining unsorted element up to its correct position at the end of the array. The process repeats for n−1 passes, or stops early the moment a full pass makes zero swaps (a clear sign the array is already sorted).

Pseudocode

BUBBLE_SORT(arr, n):
  FOR i = 0 TO n-2:
    swapped = FALSE
    FOR j = 0 TO n-2-i:              // unsorted region shrinks by 1 each pass
      IF arr[j] > arr[j+1]:
        SWAP(arr[j], arr[j+1])
        swapped = TRUE
    IF NOT swapped: BREAK             // early-exit optimization — already sorted

Complexity

Space: O(1) (in-place, only a temp variable for swapping). Stable: yes — equal elements never cross past each other, since a swap only happens on strict >.

Exam Angle

Bubble Sort's O(n²) worst/average case is why it's the textbook example of an inefficient sort — but its O(n) best case (with early exit) and O(1) space make it a fair answer for "which sort would you use on a tiny or nearly-sorted array." The exam format is almost always a pass-by-pass trace: write out the array after every single pass, not just the final sorted result — examiners award marks per pass shown.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: Full Pass-by-Pass Trace

2017, Paper I, Q5(c) (6 marks) — Describe the process of Bubble Sorting. Write down the output after each pass of the Bubble Sort algorithm for sorting the sequence (3, 8, 2, 6, 1, 10).

Starting array: [3, 8, 2, 6, 1, 10], n = 6

Pass 1 (compare positions 0↔1, 1↔2, 2↔3, 3↔4, 4↔5):

3,8→no swap · 8,2→swap · 8,6→swap · 8,1→swap · 8,10→no swap

After Pass 1: [3, 2, 6, 1, 8, 10] — the largest remaining element (8, among the first 5) has bubbled into position 4.

Pass 2: 3,2→swap · 3,6→no swap · 6,1→swap · 6,8→no swap

After Pass 2: [2, 3, 1, 6, 8, 10]

Pass 3: 2,3→no swap · 3,1→swap · 3,6→no swap

After Pass 3: [2, 1, 3, 6, 8, 10]

Pass 4: 2,1→swap · 2,3→no swap

After Pass 4: [1, 2, 3, 6, 8, 10]

Pass 5: 1,2→no swap — zero swaps this pass, so the array is confirmed sorted and the algorithm can terminate early.

Final sorted array: [1, 2, 3, 6, 8, 10]

Key reasoning points: each pass is guaranteed to correctly place at least one more element at the end of the unsorted region (the maximum of what remains), which is why n−1 passes always suffice in the worst case — and why the swapped-flag check on Pass 5 is what allows early termination the moment no more work is needed, giving Bubble Sort its O(n) best case on nearly-sorted input.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q5(c) · 6 marks

Q. Describe bubble sort. Write the output after each pass for the sequence (3, 8, 2, 6, 1, 10).

Ans.

• Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass the largest remaining element "bubbles" to the end. It stops when a pass makes no swaps. Time O(n²) worst case, O(n) best case with the early-stop check.