Talk:Quickselect

Is recursion correct?

As far as I am aware, the algorithm as presented is incorrect, specifically the recursive case:

    else if n < pivotIndex
        return select(list, left, pivotIndex - 1, n)
    else
        return select(list, pivotIndex + 1, right, n)

If we n > pivotIndex, then we only need to search for the (n - pivotIndex) element in the right-hand side. A quick look at some other implementations online (e.g., here) back this up. --Nels Beckman (talk) 10:25, 27 January 2015 (UTC)

Replacing n by n-pivotindex is appropriate for versions of the algorithm that pass in the whole array recursively, because when we do that the position of the element we're looking for is offset by the number of elements earlier than it that are omitted from the recursive call. But in this version, we pass in the left and right bounds of a subarray, and the position of the element we're looking for does not change. So it is correct, and changing n would be a mistake. Try running a few hand simulations and see for yourself! —David Eppstein (talk) 17:24, 27 January 2015 (UTC)

Interesting. Took me several minutes two realize the algorithm. I want to add that replacing n by n-pivotindex is also appropriate for version of the algorithm that only pass parts of the array recursively. E.g. passing the part, which contains all elements of the array, which are smaller/greater or equal than some pivot.--77.3.0.85 (talk) 17:17, 11 April 2015 (UTC)

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)