Consider the following sorting algorithm that is based on the randomized increme
ID: 3572542 • Letter: C
Question
Consider the following sorting algorithm that is based on the randomized incremental construction framework. We first randomly permute all the n elements to be sorted, and then insert them into a sorted list (which is initially empty) one by one. Of course, if we build a binary search tree on this list, then we can insert each element in O(log n) time, and the total running time is O(n log n). But this is not a randomized algorithm and we do not actually need the random permutation at all. Here we consider a different way to perform each insertion. For each element x yet to be inserted, we maintain a pointer to the element y in the list such that x should be inserted after y. Then for each element y, we maintain a list of pointers pointing to all such x’s. Give the details on how to maintain these pointers after an element has been inserted into the list, and analyze the expected running time of this algorithm.
Explanation / Answer
Algorithm randomized select
Input: An array A[1..n] of n elements and an integer k, 1 kn.
Output: The kth smallest element inA.
1. rselect(A, 1, n, k)
Procedure rselect(A, low, high, k)
1. v random(low, high)
2. x A[v].
3. Partition A[low..high] into three arrays:
A1 = {a | a<x}
A2 = {a | a = x}
A3 = {a | a>x}
4. case
|A1| k: return rselect(A1, 1, |A1|, k)
|A1| + |A2| k: return x
|A1| + |A2| < k: return rselect(A3, 1, |A3|, k |A1||A2|)
5. end case