Finding the kth smallest out of an unsorted array of n elements

gistfile1.txt

The following Randomized solution can be found anywhere.

  QuickSelect: Given array A of size n and integer k ≤ n,
  1. Pick a pivot element p at random from A.
  2. Split A into subarrays LESS and GREATER by comparing each element to p as in
  Quicksort. While we are at it, count the number L of elements going in to LESS.
  3. (a) If L = k − 1, then output p.
     (b) If L > k − 1, output QuickSelect(LESS, k).
     (c) If L < k − 1, output QuickSelect(GREATER, k − L − 1)

But it fails on the case that A[i] is constant for 0 ≤ i < n. The (a) should be as follows:

If L = k − 1 or L + G < k, then output p.