Write QuickSelect. Read n and n integers, then values of k (1 = smallest). For each k, find the k-th smallest element with quickselect: partition with the Lomuto scheme and the last element as pivot; if the pivot lands at index k − 1 it is the answer, otherwise continue in one side only. Work on a fresh copy of the input for each k. Print each pivot and where it lands, the answer and the number of comparisons; finish with the median (element at sorted index (n − 1)/2).
For the input
7
9 3 7 1 8 2 5
4 1 7
the program prints
k = 4:
pivot 5 lands at index 3
answer 5 (6 comparisons, check ok)
k = 1:
pivot 5 lands at index 3
pivot 2 lands at index 1
answer 1 (8 comparisons, check ok)
k = 7:
pivot 5 lands at index 3
pivot 9 lands at index 6
answer 9 (8 comparisons, check ok)
Median: 5