Consider an array given below.
Micron technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider an array given below.
A: 43 23 87 56 98
How many swaps are required to sort array A in ascending order using bubble sort in 1st pass?
Show answer & explanation
In the first pass of bubble sort, we compare adjacent elements and swap them if they're out of order. Starting with [43, 23, 87, 56, 98], we perform 3 swaps: (43, 23)→[23, 43, 87, 56, 98], (87, 56)→[23, 43, 56, 87, 98], and (87, 98) requires no swap. Actually, the correct count is 3 swaps total in pass 1.
Step-by-step Derivation:
Bubble Sort 1st Pass Trace:
Initial: [43, 23, 87, 56, 98]
Step 1: Compare 43 and 23 → 43 > 23, SWAP → [23, 43, 87, 56, 98] (Swap 1)
Step 2: Compare 43 and 87 → 43 < 87, no swap → [23, 43, 87, 56, 98]
Step 3: Compare 87 and 56 → 87 > 56, SWAP → [23, 43, 56, 87, 98] (Swap 2)
Step 4: Compare 87 and 98 → 87 < 98, no swap → [23, 43, 56, 87, 98] (Swap 3)
Wait, re-tracing: In one pass we do n-1 comparisons for n elements.
With 5 elements, we make 4 comparisons:
- Compare 43 and 23 → SWAP (Swap 1) → [23, 43, 87, 56, 98]
- Compare 43 and 87 → no swap → [23, 43, 87, 56, 98]
- Compare 87 and 56 → SWAP (Swap 2) → [23, 43, 56, 87, 98]
- Compare 87 and 98 → no swap → [23, 43, 56, 87, 98]
Total swaps in 1st pass: 2
Actually, let me recount carefully:
Comparison 1: 43 > 23 → SWAP
Comparison 2: 43 < 87 → no swap
Comparison 3: 87 > 56 → SWAP
Comparison 4: 87 < 98 → no swap
Total: 2 swaps. The correct answer is A) 2, not B) 3.