Write PivotChoice, which sorts the same data twice with quick sort (Lomuto-style partition around the element at low) and counts the comparisons of elements and the depth of the recursion:
- the pivot is the first element of the range;
- the pivot is the median of three — of the first, middle and last elements — which is first moved to position
low.
Read n, then n integers. Print the first 12 sorted values, then the two counts and depths. For the input
10
5 2 9 4 7 6 1 3 8 10
the program prints
Sorted: 1 2 3 4 5 6 7 8 9 10
First element as pivot: 21 comparisons, recursion depth 4
Median of three as pivot: 34 comparisons, recursion depth 3
Both sorted correctly: true
Try an already sorted input of 500 values. Explain the two depths.