Skip to content

Instantly share code, notes, and snippets.

@ylegall
Created November 8, 2013 04:17
Show Gist options
  • Save ylegall/7366207 to your computer and use it in GitHub Desktop.
Save ylegall/7366207 to your computer and use it in GitHub Desktop.
Use order statistics to select the median of an array in linear time without sorting.
import std.stdio;
auto swap(T)(ref T a, ref T b) {
T tmp = a;
a = b;
b = tmp;
}
auto part(T)(T[] array, int low, int high) {
auto size = low-1;
auto pivot = array[high-1];
foreach (i; low .. high) {
if (array[i] < pivot) {
++size;
swap(array[i], array[size]);
}
}
swap(array[size+1], array[high-1]);
return size + 1;
}
auto select(T)(T[] array, int low, int high, int k) {
while (true) {
auto pivotIndex = part(array, low, high);
auto len = pivotIndex - low;
if (k == len) {
return array[pivotIndex];
} else if (k < len) {
high = pivotIndex;
} else {
k -= len;
low = pivotIndex + 1;
}
}
}
void main() {
auto array = [5,1,6,2,7,4,8,3,10];
writeln(select(array, 0, array.length, array.length/2));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment