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 ______.
Answer
0
Explanation
The array is already sorted. In the first partition the pivot is 100 and every other element is smaller, so they all already sit on the left side and the pivot is already in its final place. Each later call looks the same: on 60 70 80 90 the pivot 90 is the largest, then 80, then 70.
A Lomuto-style partition would only ever swap an element with itself here, because its two indices are always equal, and such a step moves nothing and can be skipped. No element ever has to change place, so the minimum number of swaps is 0.
Answer: 0