Wouldn't it be easier for the partition_random to return an index (index of the new random pivot) and send it to quicksort?
This is exactly what is currently happening.
D.J. Quavern wrote:I hear you Junilu, this is my fault for not commenting
Nope. It's your fault for not writing clear code. A well written program mostly documents method contracts, and doesn't need a lot of comments in method bodies.
A comment like "
j will run from low to one less than the last element" is really really useless. You're essentially writing the code twice, once in
Java and once in English. Instead of writing comments like that, document your methods like so:
With documentation like this, you can easily see that the return value is not a partition, but the index of the split point. This index is then returned to the
partition_random() method (which should have been called
partitionUsingRandomPivot()), which in turn returns it to the
quicksort() method. The
quicksort() method uses this index to sort the two partitions recursively.