The quick select selects the largest x fraction of the elements
of an array in O(n) time for an array of size n. Here
x is a number between 0 and 1. Now, suppose there are k such
numbers
and we want to move the elements of the array a so that the
fraction comes first, then the
, and so on. For example, suppose k=9,
,
, and so on. We want the array reordered so that the top
of the numbers come first, then the second
, and so on. Within these
groups, the numbers need not be sorted. Find an algorithm based on the
quick select idea that is better than sorting if 1 << k <<
n.
2.
(from CLR, page 151) Give an
algorithm to merge k sorted lists into a single sorted list of length
n. Hint: Make a heap of the largest element of each of the
k sublists not yet merged into the final list.
3.
Given an array of length n, not in order, we want to determine
whether any two elements are the same. The algorithm must use only binary
comparisons. Is it possible to do this using fewer than
comparisons or equality tests? We know that it is not possible to sort
this list in fewer than
comparisons.