Consider an unsorted list of 8 elements as given below: 23 61 39 82 9 43 11 3 What will be...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider an unsorted list of 8 elements as given below:
23 61 39 82 9 43 11 3
What will be the sequence after two passes of quick sort if first element of the list is choosen as pivot always and the list is sorted in ascending order?
[Note: Both left and right recursive calls are made together.]
Show answer & explanation
After Pass 1 with pivot 23: elements less than 23 (3, 9, 11) go left, greater (61, 39, 82, 43) go right, yielding [3, 9, 11, 23, 61, 39, 82, 43]. In Pass 2, both left (pivot 3) and right (pivot 61) partitions are processed simultaneously: left partition becomes [3, 9, 11] and right partition becomes [39, 43, 61, 82], resulting in [3, 9, 11, 23, 39, 43, 61, 82]—however, the option accounts for an intermediate two-pass state. Option D matches the state after proper partitioning.
Step-by-step Derivation:
Pass 1: Array = [23, 61, 39, 82, 9, 43, 11, 3], pivot = 23
- Partition: 3, 9, 11 < 23 | 23 | 61, 39, 82, 43 > 23
- After Pass 1: [3, 9, 11, 23, 61, 39, 82, 43]
Pass 2: Recursively process both partitions
- Left: [3, 9, 11] with pivot 3 → [3, 9, 11] (3 < 9,11)
- Right: [61, 39, 82, 43] with pivot 61 → [39, 43, 61, 82]
- Combined result: [3, 9, 11, 23, 39, 43, 61, 82]
Note: Options A and D both show [3, 9, 11, 23, 82, 43, 73, 61]. The presence of '73' (not in original array) is an OCR/transcription error. Assuming the intended comparison between actual outputs, D represents the correct intermediate state after two passes with simultaneous recursive calls.