Order statistic

In a set of $n$ elements:

• Order statistic: the $i$th smallest element
• Median:
  • if $n$ is odd $\Rightarrow$ $i = \frac{n+1}{2}$
  • if $n$ is even $\Rightarrow$ two medians (lower and upper median)

Fast min/max #

Time complexity is still $O(n)$ but uses $3 \lfloor n/2 \rfloor$ comparisons at most

algorithm minmax(a):
    min = infinity
    max = -infinity
    for i from 1 to n (incrementing by 2):
        if a[i] < a[i - 1]:
            if a[i] < min:
                set min to a[i]
            if a[i - 1] > max:
                set max to a[i - 1]
        else:
            if a[i - 1] < min:
                set min to a[i - 1]
            if a[i] > max:
                set max to a[i]

Quickselect #

To find the $i$th smallest element, uses the same partition algorithm as quicksort.

algorithm quickselect(a, min, max, i):
    if min = max:
        return a[min]
        
    p = partition(a, min, max)
    k = p - min + 1
    if i == k:
        return q[p]
    else if i < p:
        return quickselect(a, min, p - 1, i)
    else:
        return quickselect(a, p + 1, max, i-k)