private static void quickSort ( int [ ] order , double [ ] values , int start , int end , int limit ) { // the while loop implements tail-recursion to avoid excessive stack calls on nasty cases while ( end - start > limit ) { // pivot by a random element int pivotIndex = start + prng . nextInt ( end - start ) ; double pivotValue = values [ order [ pivotIndex ] ] ; // move pivot to beginning of array swap ( order , start , pivotIndex ) ; // we use a three way partition because many duplicate values is an important case int low = start + 1 ; // low points to first value not known to be equal to pivotValue int high = end ; // high points to first value > pivotValue int i = low ; // i scans the array while ( i < high ) { // invariant: values[order[k]] == pivotValue for k in [0..low) // invariant: values[order[k]] < pivotValue for k in [low..i) // invariant: values[order[k]] > pivotValue for k in [high..end) // in-loop: i < high // in-loop: low < high // in-loop: i >= low double vi = values [ order [ i ] ] ; if ( vi == pivotValue ) { if ( low != i ) { swap ( order , low , i ) ; } else { i ++ ; } low ++ ; } else if ( vi > pivotValue ) { high -- ; swap ( order , i , high ) ; } else { // vi < pivotValue i ++ ; } } // invariant: values[order[k]] == pivotValue for k in [0..low) // invariant: values[order[k]] < pivotValue for k in [low..i) // invariant: values[order[k]] > pivotValue for k in [high..end) // assert i == high || low == high therefore, we are done with partition // at this point, i==high, from [start,low) are == pivot, [low,high) are < and [high,end) are > // we have to move the values equal to the pivot into the middle. To do this, we swap pivot // values into the top end of the [low,high) range stopping when we run out of destinations // or when we run out of values to copy int from = start ; int to = high - 1 ; for ( i = 0 ; from < low && to >= low ; i ++ ) { swap ( order , from ++ , to -- ) ; } if ( from == low ) { // ran out of things to copy. This means that the the last destination is the boundary low = to + 1 ; } else { // ran out of places to copy to. This means that there are uncopied pivots and the // boundary is at the beginning of those low = from ; } // checkPartition(order, values, pivotValue, start, low, high, end); // now recurse, but arrange it so we handle the longer limit by tail recursion if ( low - start < end - high ) { quickSort ( order , values , start , low , limit ) ; // this is really a way to do // quickSort(order, values, high, end, limit); start = high ; } else { quickSort ( order , values , high , end , limit ) ; // this is really a way to do // quickSort(order, values, start, low, limit); end = low ; } } }
Standard quick sort except that sorting is done on an index array rather than the values themselves