ith Order Statistic

The ith order statistic of a set of n elements is the element which would be in the ith position if the set were sorted. For example, the minimum is the 1st order statistic, while the maximum is the nth order statistic.

Java example - Finding ith statistic:

1
2
3
4
5
6
7
8

int ithOrderStatistic(int[] arr, int i) {
  Arrays.sort(arr);
  return arr[i-1]; 
}

// Find 3rd largest element
int[] arr = {5, 2, 8, 3, 9};
int thirdLargest = ithOrderStatistic(arr, arr.length - 3 + 1);

C++ example - Select algorithm:

1
2
3
4
5
6
7
8
9

int select(vector<int> arr, int k) {
  // Use quickselect algorithm
  return selectUtil(arr, 0, arr.size()-1, k-1);
}

int selectUtil(vector<int>& arr, int low, int high, int k) {
  // Partition and recursively select
  return arr[k];
}

Python example - Kth smallest element:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import random 

def kth_smallest(arr, k):

  # Use quickselect based on random pivot
  pos = random_partition(arr, low, high)
  
  if pos == k-1:
    return arr[pos]
  if pos > k-1: 
    return kth_smallest(arr, k, low, pos-1)
  else:  
    return kth_smallest(arr, k, pos+1, high)

Order statistics provide rank-based insights into data distributions. Efficient algorithms can compute them in O(n) time.

The ith order statistic of a set is its ith-smallest element. For example, the 1st order statistic is the minimum element, and the nth order statistic is the maximum for a set of size n. Order statistics are foundational in algorithms, statistics, and data structures like heaps. Finding the ith order statistic is a well-studied problem with various algorithms, such as Quickselect, to solve it efficiently. The key takeaway is that ith order statistics provide a structured way to query sets for specific elements based on their size.

Java Code

In Java, Quickselect can be used to find the ith order statistic. The function quickSelect is used for this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.Random;

public class QuickSelect {
    public static int quickSelect(int[] arr, int k) {
        return quickSelect(arr, 0, arr.length - 1, k - 1);
    }

    private static int quickSelect(int[] arr, int left, int right, int k) {
        if (left == right) {
            return arr[left];
        }

        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        pivotIndex = partition(arr, left, right, pivotIndex);

        if (k == pivotIndex) {
            return arr[k];
        } else if (k < pivotIndex) {
            return quickSelect(arr, left, pivotIndex - 1, k);
        } else {
            return quickSelect(arr, pivotIndex + 1, right, k);
        }
    }

    private static int partition(int[] arr, int left, int right, int pivotIndex) {
        int pivotValue = arr[pivotIndex];
        swap(arr, pivotIndex, right);
        int storeIndex = left;

        for (int i = left; i < right; i++) {
            if (arr[i] < pivotValue) {
                swap(arr, storeIndex, i);
                storeIndex++;
            }
        }

        swap(arr, right, storeIndex);
        return storeIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
  1. quickSelect is a wrapper function that calls a recursive function to perform Quickselect.
  2. The partition function rearranges elements based on a randomly chosen pivot.

C++ Code

In C++, the Quickselect algorithm is implemented as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <algorithm>
#include <random>

int quickSelect(std::vector<int>& arr, int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distr(left, right);
    int pivotIndex = distr(gen);

    std::swap(arr[pivotIndex], arr[right]);
    int storeIndex = left;

    for (int i = left; i < right; ++i) {
        if (arr[i] < arr[right]) {
            std::swap(arr[i], arr[storeIndex]);
            storeIndex++;
        }
    }

    std::swap(arr[right], arr[storeIndex]);

    if (k == storeIndex) {
        return arr[k];
    } else if (k < storeIndex) {
        return quickSelect(arr, left, storeIndex - 1, k);
    } else {
        return quickSelect(arr, storeIndex + 1, right, k);
    }
}
  1. Similar to the Java version, a recursive function quickSelect performs the task.
  2. std::swap is used for element swapping.

Python Code

In Python, Quickselect can be implemented as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import random

def quick_select(arr, k):
    return _quick_select(arr, 0, len(arr) - 1, k - 1)

def _quick_select(arr, left, right, k):
    if left == right:
        return arr[left]

    pivot_index = random.randint(left, right)
    pivot_index = _partition(arr, left, right, pivot_index)

    if k == pivot_index:
        return arr[k]
    elif k < pivot_index:
        return _quick_select(arr, left, pivot_index - 1, k)
    else:
        return _quick_select(arr, pivot_index + 1, right, k)

def _partition(arr, left, right, pivot_index):
    arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
    store_index = left

    for i in range(left, right):
        if arr[i] < arr[right]:
            arr[store_index], arr[i] = arr[i], arr[store_index]
            store_index += 1

    arr[right], arr[store_index] = arr[store_index], arr[right]
    return store_index
  1. _quick_select is the recursive function for Quickselect.
  2. The _partition function rearranges elements, similar to the Java and C++ versions.

By understanding these implementations, you can effectively find the ith order statistic in a set of elements using Quickselect in Java, C++, and Python.