Which one of the sorting algorithm given in options will perform sorting of the array 8 9...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Which one of the sorting algorithm given in options will perform sorting of the array 8 9 10 2 4 in ascending order?
If the result of 1st pass is = 8 9 2 4 10
If the result of 2nd pass is= 8 2 4 9 10 and so on..
Show answer & explanation
Bubble sort repeatedly compares adjacent elements and swaps them if they're in the wrong order, moving the largest unsorted element to its correct position each pass. After pass 1, the largest element (10) moves to the end: [8, 9, 2, 4, 10]. After pass 2, the next largest (9) reaches its position: [8, 2, 4, 9, 10]. This matches the given pass results exactly. Merge sort, heap sort, and quick sort have different behavior patterns and don't produce these intermediate results.
Step-by-step Derivation:
Trace bubble sort on [8, 9, 10, 2, 4]:
Pass 1 (compare and swap adjacent elements):
- Compare 8, 9: no swap → [8, 9, 10, 2, 4]
- Compare 9, 10: no swap → [8, 9, 10, 2, 4]
- Compare 10, 2: swap → [8, 9, 2, 10, 4]
- Compare 10, 4: swap → [8, 9, 2, 4, 10]
Result after pass 1: [8, 9, 2, 4, 10] ✓ matches given
Pass 2 (largest element already positioned, continue with rest):
- Compare 8, 9: no swap → [8, 9, 2, 4, 10]
- Compare 9, 2: swap → [8, 2, 9, 4, 10]
- Compare 9, 4: swap → [8, 2, 4, 9, 10]
Result after pass 2: [8, 2, 4, 9, 10] ✓ matches given
This step-by-step behavior is characteristic of bubble sort, where the largest elements bubble to the end in successive passes.