CLRS 9-3 Small order statistics

https://github.com/gzc/CLRS/blob/master/C09-Medians-and-Order-Statistics/problem.md

The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small relative to n, we can implement a different procedure that uses SELECT as a subroutine but makes fewer comparisons in the worst case.

a. Describe an algorithm that uses Ui(n) comparisons to find the ith smallest of n elements, where (Hint: Begin with  disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair.)

b. Show that, if i < n/2, then Ui(n) = n + O(T (2i) lg(n/i)).

c. Show that if i is a constant less than n/2, then Ui(n) = n + O(lg n).

d. Show that if i = n/k for k≥2,then Ui(n) = n+O(T(2n/k)lgk).

Answer

a. 1. 如果i ≥ n/2,直接调用SELECT(n, i) 2. 如果i < n/2,那么就两个两个比较，生成了小的一组，同时也记录大的一组（比如可以用map映射起来） 3. 对小的一组递归调用这个函数 4. 当调用回来时，能找到这小的一组的第i个数，这个数左边都是比它小的数字，再从map中找到这i个数字对应的数字，这样总共有2i个数字，再对这2i个数字调用SELECT. 很tricky的一点是为什么最后要调用T(2i),看下面这个数字[1,2,3,4],order-2是2，可是分组完后较小元素是[1,3],所以还要对另外i个数字进行比较.

b. 

c. 

d. 

http://clrs.skanev.com/09/problems/03.html

This is a modified version of SELECT. Not only it finds the ith order statistic, but it also partitions the array, thus finding the i−1 smaller elements.

1. If i≥n/2, we just use SELECT
2. Otherwise, split the array in pairs and compare each pair.
3. We take the smaller elements of each pair, but keep track of the other one.
4. We recursively find the first i elements among the smaller elements
5. The ith order statistic is among the pairs containing the smaller elements we found in the previous step. We call SELECT on those 2i elements. That's the final answer.

Just picking the smaller element of each pair is not enough. For example, if we're looking for the 2nd order statistic and our pairs are 1, 2, 3, 4,5, 6, 7, 8, 9, 10, the answer is in the larger part of the first pair. That's why we need to keep track and later perform SELECT on 2i elements.

Steps 1-4 can be implemented in place by modifying the algorithm to put the larger elements of the pairs on the inactive side of the pivot and modifying PARTITION to swap the elements on the inactive side every time it swaps elements on the active side. More details can be found in the Instructor's Manual.

1. Divide the input as follows. If n is even, divide the input into two parts:

A[p + 1 . . p + m] and A[p + m + 1 . . p + n]. If n is odd, divide the input

into three parts: A[p +1 . . p +m], A[p +m +1 . . p+n −1], and A[p +n]

as a leftover piece.

2. Compare A[p +i ] and A[p +i +m] for i = 1, 2, . . . ,m, putting the smaller

of the the two elements into A[p + i + m] and the larger into A[p + i ].

3. Recursively find the i th smallest element in A[p+m+1 . . p+n], but with an

additional action performed by the partitioning procedure: whenever it exchanges

A[ j ] and A[k] (where p+m+1 ≤ j, k ≤ p+2m), it also exchanges

A[ j−m] and A[k−m]. The idea is that after recursively finding the i th smallest

element in A[p+m+1 . . p+n], the subarray A[p + m + 1 . . p+m+i ]

contains the i smallest elements that had been in A[p + m + 1 . . p + n] and

the subarray A[p +1 . . p +i ] contains their larger counterparts, as found in

step 1. The i th smallest element of A[p + 1 . . p + n] must be either one of

the i smallest, as placed into A[p +m +1 . . p +m +i ], or it must be one of

the larger counterparts, as placed into A[p + 1 . . p + i ].

4. Collect the subarrays A[p + 1 . . p + i ] and A[p + m + 1 . . p + m + i ] into

a single array B[1 . . 2i ], call SELECT to find the i th smallest element of B,

and return the result of this call to SELECT.