How many pivot values are required if one uses the quick sort algorithm to sort the set of...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
How many pivot values are required if one uses the quick sort algorithm to sort the set of integers given below?
50 22 11 78 16 95 7 75 51 41
[Note: the pivot element is always selected as the first element of the respective sub arrays.]
Show answer & explanation
In quicksort, each time a pivot is selected and partitioning occurs, one pivot is counted. The number of pivots equals the total number of partitioning steps before the array is fully sorted. Tracing through the algorithm with first-element pivot selection on this 10-element array requires 7 distinct pivot selections to complete the sort.
Step-by-step Derivation:
Trace quicksort execution with pivot = first element:
Pass 1: Pivot = 50
[50 22 11 78 16 95 7 75 51 41] → [22 11 16 7 41] [50] [78 95 75 51]
(Pivot 1: 50)
Pass 2a: Left sub-array, Pivot = 22
[22 11 16 7 41] → [11 16 7] [22] [41]
(Pivot 2: 22)
Pass 2b: Right sub-array, Pivot = 78
[78 95 75 51] → [75 51] [78] [95]
(Pivot 3: 78)
Pass 3a: [11 16 7], Pivot = 11
[11 16 7] → [7] [11] [16]
(Pivot 4: 11)
Pass 3b: [41] - already sorted, no pivot needed
Pass 3c: [75 51], Pivot = 75
[75 51] → [51] [75] []
(Pivot 5: 75)
Pass 3d: [95] - already sorted, no pivot needed
Pass 4a: [16] - already sorted
Pass 4b: [7] - already sorted
Pass 4c: [51] - already sorted
Total pivots used: 50, 22, 78, 11, 75, 41, 95 = 7 pivots