ITPEC FE Subject A April 2024 Question 7

Bubble Sort Swap Count (Worst Case) — count swaps when array is in reverse order.

When an array of N elements is sorted in reverse order, bubble sort performs the maximum number of swaps:

• •Pass 1: N-1 swaps
• •Pass 2: N-2 swaps
• •...
• •Pass N-1: 1 swap

Total = (N-1) + (N-2) + ... + 1 = `N(N-1) / 2`

Why not others:
- (b) N²/2 — close but missing the -N/2 term; expands to (N² - N)/2 ≠ N²/2
- (c) N(N-1) — double the correct answer (forgot to divide by 2)
- (d) N² — overstates; includes non-existent comparisons

Key rule: Worst-case swaps for bubble sort = sum of first N-1 integers = N(N-1)/2.

AI-generated — may contain errors