Consider sorting the following array of integers in ascending order using an in-place Quicksort algorithm that uses the last element as the pivot.
| 60 | 70 | 80 | 90 | 100 |
The minimum number of swaps performed during this Quicksort is ______.
Tap to open full sizeA single row of five boxed cells holding the integers 60, 70, 80, 90, 100 from left to right (already sorted ascending).
ANSWER
The minimum number of swaps is .
Official answer: 0Source: Official answer key, GATE 2024 DA (IISc Bengaluru)
The array is already in ascending order, and the pivot is always the last element of the current subarray.
A swap exchanges two elements at different positions. Partitioning only has to put every element pivot to the left of the pivot and every element pivot to its right, and then place the pivot at its boundary.
First partition, pivot : it is the maximum, so all four other elements are and already lie to its left. No element is on the wrong side, so no two distinct positions need to be exchanged. The pivot's boundary position is index , which is where it already sits, so even the final pivot placement moves nothing.
The problem splits into and an empty right part. In the pivot is again the maximum, so the same argument applies: no swap. Likewise pivot in and pivot in .
The last subarray has one element and needs no work.
Every partition leaves its pivot where it already is and moves nothing, so no two distinct elements are ever exchanged. The minimum number of swaps is .
Note: a textbook Lomuto loop that blindly executes a swap even when the two indices coincide would perform swaps of an element with itself. Those are not exchanges of two elements, and the question asks for the minimum, which is attained when swaps are made only between distinct positions.
KEY IDEA
With the last element as pivot, an already sorted array makes every pivot the maximum of its subarray, so every element is already on the correct side of it. Nothing needs to be exchanged, so the number of real swaps is zero (the sorted input is the best case for swaps, though the worst case for the recursion depth and comparisons).
WATCH OUT FOR
Counting the self-swaps of a blind Lomuto loop (4+3+2+1 element-with-itself exchanges, plus the final pivot placement) and answering 10 or 14. Those do not exchange two distinct elements, and the question asks for the minimum. Another slip is to treat sorted input as the worst case and expect many swaps; it is the worst case for comparisons and depth, not for real swaps.
From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes