Describe an in-place version of the quick-select algorithm in pseudo-code, assuming that you are allowed to modify the order of elements.   Show how to use a deterministic O ( n )-time selection...

Describe an in-place version of the quick-select algorithm in pseudo-code,

assuming that you are allowed to modify the order of elements.

Show how to use a deterministic
O(n)-time selection algorithm to sort a

sequence of
n
elements in
O(nlog
n)

worst-case

time.

Given an unsorted sequence
S
of
n
comparable elements, and an integer
k,

give an
O(nlog
k) expected-time algorithm for finding the
O(k) elements

that have rank
n/k_, 2n/k_, 3n/k_, and so on.