Talk:Quickselect

Overlap with selection algorithm

Some overlap with this and selection algorithm, in particular the section describing this algorithm. Merge out? Dcoetzee 00:04, 18 August 2007 (UTC)

Precise analysis of the expected time of this algorithm

The expected number of comparisons made by this algorithm, when used (with random pivots) to compute the median, is $n(2+2\log 2+o(1))$; see http://11011110.livejournal.com/119720.html. (Perhaps it would be too much of a conflict of interest for me to add this link myself.) Probably somewhere we should mention the related but more complicated algorithm that finds a sample of about square root of the input size, recurses in the sample, and uses the result as a pivot, getting $n+\min(k,n-k)+O(n^{1/2})$ comparisons in expectation. —David Eppstein (talk) 23:35, 22 August 2013 (UTC)

Thanks!

Added in this edit.

I’ve also added a brief note about the more complicated algorithm, but it needs elaboration and a reference.

—Nils von Barth (nbarth) (talk) 10:59, 25 August 2013 (UTC)

I did a bit of digging and found the algorithm you were talking about, which I’ve made a brief article for at Floyd–Rivest algorithm. I plan to expand and incorporate it into selection algorithm by and by.

—Nils von Barth (nbarth) (talk) 13:49, 1 September 2013 (UTC)

Returning a range

A common and natural variant of this algorithm returns a range of values, usually in sorted order. E.g. qselect ([5,2,3,9,0,1,5], 1, 4) would return [1,2,3]. This runs in O(n) + O(k log k). — Preceding unsigned comment added by 188.126.200.132 (talk) 06:32, 13 August 2014 (UTC)