# Order statistics without sorting in expected linear time in Java

Given an unsorted array of integers $A$, the $i$th order statistic of $A$ is the $i$th smallest element of $A$. For example, $0$th order statistics of $A$ is the minimum of $A$; $(|A| - 1)$th order statistics of $A$ is the maximum of $A$; $1$th order statistics is the second smallest element, and so on.

OrderStatistics.java

package net.coderodde.stat;

import java.util.Random;

public final class OrderStatistics {

private OrderStatistics() {}

/**
* Returns the {@code order}th order statistics of the array {@code array}.
* If {@code order == 0}, returns the minimum element; if
* {@code order == 1}, returns the second smallest element, and so on.
*
* @param array the array to search.
* @param order the order of the element to search.
* @return the <code>order</code>th smallest element.
*/
public static int randomizedSelect(int[] array, int order) {
checkOrder(order, array);
Random random = new Random();
return randomizedSelect(array, 0, array.length - 1, order + 1, random);
}

/**
* Checks that the requested order is within array bounds.
*
* @param order the order to check.
* @param array the array to search.
*/
private static void checkOrder(int order, int[] array) {
if (order < 0) {
throw new IndexOutOfBoundsException("Negative order: " + order);
}

if (order >= array.length) {
throw new IndexOutOfBoundsException(
"Order is too large (" + order + "). Must be at most " +
(array.length - 1) + ".");
}
}

/**
* Performs a randomized selection of an element with order {@code order}.
*
* @param array      the array holding the range to search.
* @param startIndex the index of the leftmost element of the array range.
* @param endIndex   the index of the rightmost element of the array range.
* @param order      the requested order.
* @param random     the random number generator.
*
* @return the <code>order</code>th smallest element.
*/
private static int randomizedSelect(int[] array,
int startIndex,
int endIndex,
int order,
Random random) {
if (startIndex == endIndex) {
return array[startIndex];
}

int pivotIndex = randomizedPartition(array,
startIndex,
endIndex,
random);
int k = pivotIndex - startIndex + 1;

if (order == k) {
return array[pivotIndex];
} else if (order < k) {
return randomizedSelect(array,
startIndex,
pivotIndex - 1,
order,
random);
} else {
return randomizedSelect(array,
pivotIndex + 1,
endIndex,
order - k,
random);
}
}

private static int randomizedPartition(int[] array,
int startIndex,
int endIndex,
Random random) {
int rangeLength = endIndex - startIndex + 1;
int i = startIndex + random.nextInt(rangeLength);
swap(array, endIndex, i);
return partition(array, startIndex, endIndex);
}

private static int partition(int[] array, int startIndex, int endIndex) {
int pivot = array[endIndex];
int i = startIndex - 1;

for (int j = startIndex; j < endIndex; ++j) {
if (array[j] <= pivot) {
i++;
swap(array, i, j);
}
}

swap(array, i + 1, endIndex);
return i + 1;
}

private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}


Demo.java

package net.coderodde.stat;

import java.util.Arrays;
import java.util.Random;

public class Demo {

private static final int WARMUP_LENGTH = 100_000;
private static final int WARMUP_ITERATIONS = 500;
private static final int ARRAY_LENGTH = 50_000_000;

public static void main(String[] args) {
long seed = System.currentTimeMillis();
Random random = new Random(seed);

warmup(random);

int[] array = getRandomIntArray(ARRAY_LENGTH, random);
System.out.println("Seed = " + seed);

long startTime = System.currentTimeMillis();
int median1 = OrderStatistics.randomizedSelect(array, ARRAY_LENGTH / 2);
long endTime = System.currentTimeMillis();

System.out.println("OrderStatistics.randomizedSelect() in " +
(endTime - startTime) + " milliseconds.");

startTime = System.currentTimeMillis();
Arrays.sort(array);
int median2 = array[ARRAY_LENGTH / 2];
endTime = System.currentTimeMillis();

System.out.println("Selection via sorting in " + (endTime - startTime) +
" milliseconds.");

if (median1 != median2) {
System.err.println("Algorithms disagree: " + median1 + " vs. " +
median2);
} else {
System.out.println("Algorithms agree: " + median1);
}
}

private static void warmup(Random random) {
System.out.println("Warming up...");

for (int iteration = 0; iteration < WARMUP_ITERATIONS; ++iteration) {
int[] array = getRandomIntArray(WARMUP_LENGTH, random);
OrderStatistics.randomizedSelect(array,
random.nextInt(WARMUP_LENGTH));
Arrays.sort(array);
}

System.out.println("Warming up done!");
}

private static int[] getRandomIntArray(int length, Random random) {
int[] array = new int[length];

for (int i = 0; i < array.length; ++i) {
array[i] = random.nextInt(1_000_000);
}

return array;
}
}


Performance figures

Upon running the demonstration, I get something like:

Seed = 1483720011710
OrderStatistics.randomizedSelect() in 862 milliseconds.
Selection via sorting in 5292 milliseconds.
Algorithms agree: 500129


Critique request

Please tell me anything that comes to mind.