You're viewing a comment by Huh... and its responses.

Huh... Permalink
August 28, 2008, 16:52

The RandomizedPartition algorithm referred to from the previous lecture modifies the source data. This means that in the general case you would need to make a complete copy of the array argument.

Meanwhile, bin sorting at can be accomplished in linear time, which suggests an alternative approach for some cases: perform a bin sort against the list, then find the k-th value from that sorted list (this would be valid work when max(A) - min(A) was not significantly larger than length(A))

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "sandbox_89": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.