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.
