A quicksort's behaviour is decided by how it picks the pivot. Count the comparisons each of four rules makes on the same list.
Every rule chooses an index inside the current range, swaps that element to the end of the range, and then runs Lomuto's partition as usual, so they differ only in the choice:
"last"— the last element of the range;"first"— the first element;"middle"— the element at(lo + hi) // 2;"median3"— of the first, middle and last elements, the one whose value is the median; ties are broken by the smaller index.
A comparison is one test of an element against the pivot inside the partition sweep, so partitioning a range of k elements costs k - 1 of them. Choosing the pivot is free.
Write pivot_comparisons(nums, rules) returning a list with one count per rule, in the order given.
Examples
Input: nums = [1, 2, 3, 4, 5], rules = ["last", "first", "middle", "median3"]
Output: [10, 10, 6, 6]
Explanation: on sorted input the first two rules degenerate to 4 + 3 + 2 + 1 comparisons; the other two halve the range each time.
Input: nums = [3, 1, 4, 1, 5], rules = ["last", "median3"]
Output: [8, 6]
Constraints
0 <= len(nums) <= 2000,-10**9 <= nums[i] <= 10**91 <= len(rules) <= 4, each rule is one of the four names and may repeat- Each rule sorts its own copy of the list.
Goals
- Compare pivot rules by counting comparisons rather than by argument
- Reuse one partition for every rule by swapping the chosen pivot to the end
- See median-of-three rescue the input that defeats the naive rules