Randomized Select

Randomized Select, or often called Quickselect, is a selection algorithm that uses the fact that the partition subroutine of Quicksort returns lesser and greater elements on each side of the pivot element. This means we can use a Binary Search-like procedure to find the -th smallest element in the array. Using the partition subroutine, the algorithm is as follows:

1. Pick a pivot element from the array. In our case we will use a random element as we saw in Randomized Quicksort.
2. Partition the array around said pivot element.
3. If the pivot element is the -th smallest element, then we are done, otherwise recurse down the left or right side of the array.

Time complexity analysis

The expected time complexity of Randomized Select is because we only ever recurse down half of the array. In recurrence form, this is expressed as with a base case of .

From a first glance, one might assume the complexity to be because Quicksort takes time, and we may have a computation tree of height . The difference here is that we are not traversing down the entire tree, but only half of it.

As with the Randomized Quicksort algorithm, the worst case time scenario will also apply to Randomized Select because we use the same partition strategy. For the same reasons, the worst case time complexity of Randomized Select is also .

Space complexity analysis

As the algorithm doesn’t require any additional space, and only reads from the input array, the space complexity is constant .

Implementation

This sample uses code from the Quicksort article.

Java Implementation

package jun.codes.interviews.select;

import jun.codes.interviews.sort.RandomizedQuicksort;

public class RandomizedSelect {
  public static <T extends Comparable<T>> T select(T[] xs, int k) {
    return select(xs, k, 0, xs.length - 1);
  }

  public static <T extends Comparable<T>> T select(T[] xs, int k, int low, int high) {
    // If there's only one element, it's the one
    if (high == low) {
      return xs[low];
    } else {
      // Partition the array around some pivot element using the Quicksort
      // partition subroutine
      Integer pivot = RandomizedQuicksort.partition(xs, low, high);
      // Pick the element if we hit directly, or recurse down the left or right
      // accordingly
      return switch (pivot) {
        case Integer x when x == k -> xs[k];
        case Integer x when x < k -> select(xs, k, low + 1, high);
        default -> select(xs, k, low, pivot - 1);
      };
    }
  }
}

Further reading

The relevant material in Introduction to Algorithms 4th edition can be found starting on page 230.

• Wikipedia: Quickselect