MIT's Introduction to Algorithms, Lecture 6: Order Statistics

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

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

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