No mention of median-of-medians for pivot selection? Someone needs to re-read CLRS...
Quickselect Algorithm
11–15 of 15 posts
Re: Quickselect Algorithm
#12No mention of median-of-medians for pivot selection? Someone needs to re-read CLRS...
They have mentioned Introselect which is a hybrid of quickselect and median of medians.
Re: Quickselect Algorithm
#13Re: Quickselect Algorithm
#14A JS implementation for fun [tests-not-yet-implemented]:
https://github.com/cristiancavalli/quick-select
Re: Quickselect Algorithm
#15Earlier quoted context omitted.
True. This is what I meant by confusing, without properly defining the variables at play, in this context, k is the index of the element of the ordered list, and not the kth smallest element. Semantics, I agree, but confusing nonetheless. Or in other words, how do we define k?
I have emailed them. post should be updated soon.
Post has been updated.