What is the number of swaps required in the first pass of bubble sort if the elements given...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
What is the number of swaps required in the first pass of bubble sort if the elements given below are sorted in descending order?
22 71 10 93 61 43 9
Show answer & explanation
In the first pass of bubble sort (descending order), we compare adjacent elements from left to right and swap if the left element is smaller than the right. The swaps occur at positions: (22, 71)→swap, (71, 10)→no swap, (71, 93)→swap, (93, 61)→no swap, (93, 43)→no swap, (93, 9)→no swap. However, recalculating: 22<71 (swap), 71>10 (no), 71<93 (swap), 93>61 (no), 93>43 (no), 93>9 (no) = 2 swaps. Re-examining with correct logic: comparing pairs left-to-right for descending: (22,71) swap, (71,10) no, (71,93) swap, (93,61) no, (93,43) no, (93,9) no gives 2 swaps. The correct answer is 4 swaps based on standard bubble sort implementation counting all necessary comparisons and repositioning.
Step-by-step Derivation:
Initial array: [22, 71, 10, 93, 61, 43, 9]
First pass (descending order - larger elements move right):
Step 1: Compare 22 and 71 → 22 < 71, SWAP → [71, 22, 10, 93, 61, 43, 9] (Swap 1)
Step 2: Compare 22 and 10 → 22 > 10, NO SWAP → [71, 22, 10, 93, 61, 43, 9]
Step 3: Compare 10 and 93 → 10 < 93, SWAP → [71, 22, 93, 10, 61, 43, 9] (Swap 2)
Step 4: Compare 10 and 61 → 10 < 61, SWAP → [71, 22, 93, 61, 10, 43, 9] (Swap 3)
Step 5: Compare 10 and 43 → 10 < 43, SWAP → [71, 22, 93, 61, 43, 10, 9] (Swap 4)
Step 6: Compare 10 and 9 → 10 > 9, NO SWAP → [71, 22, 93, 61, 43, 10, 9]
Total swaps in first pass: 4