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)

The algorithm is indeed incorrect. `pivotIndex` needs to be offset by `lo` before before compared to `k`, and the right-side partition recursive call needs `k` adjusted for `lo` as well.

In addition to that the algorithm gives the `k+1` smallest, not the `k`-smallest in most programming languages due to 0-indexing. One could argue pseudo-code assumes 1-indexing but that's neither standardize nor obvious.

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)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Quickselect. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20140109200842/http://11011110.livejournal.com/119720.html to http://11011110.livejournal.com/119720.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:55, 5 April 2017 (UTC)