nl_tokens: Performs an in - place selection to find the element which would appear at a given index in a dataset if it were sorted . The following preconditions should hold :
pl_tokens: private static void selectInPlace ( int required , double [ ] array , int from , int to ) { // If we are looking for the least element in the range, we can just do a linear search for it. // (We will hit this whenever we are doing quantile interpolation: our first selection finds // the lower value, our second one finds the upper value by looking for the next least element.) if ( required == from ) { int <mask> = from ; for ( int index = from + 1 ; index <= to ; index ++ ) { if ( array [ min ] > array [ index ] ) { min = index ; } } if ( min != from ) { swap ( array , min , from ) ; } return ; } // Let's play quickselect! We'll repeatedly partition the range [from, to] containing the // required element, as long as it has more than one element. while ( to > from ) { int partitionPoint = partition ( array , from , to ) ; if ( partitionPoint >= required ) { to = partitionPoint - 1 ; } if ( partitionPoint <= required ) { from = partitionPoint + 1 ; } } }