Quicksort partitions the range, then sorts the two sides. Using Lomuto's scheme with the last element of each range as the pivot, count the swaps the whole sort performs. A swap of a position with itself moves nothing and is not counted.
Write quicksort_swaps(nums) returning that count. The list itself need not be returned.
Examples
Input: nums = [7, 2, 9, 1, 5]
Output: 4
Input: nums = [1, 2, 3]
Output: 0
Explanation: every element is already at most the pivot and already in place.
Constraints
0 <= len(nums) <= 2000,-10**9 <= nums[i] <= 10**9- Sort a copy if you like; the caller's list may be left alone.
Goals
- Drive the recursion from a partition that reports where the pivot landed
- Count only the swaps that actually move something
- See that an already sorted list costs no swaps at all