Talk:Quicksort

Template:Vital article

Blog interview

The new blog post that purported holds an interview with Tony Hoare isn't needed — most of the history contained in it has already been divulged by Hoare in other places. I'll try to find out where so we can get rid of the blog. QVVERTYVS (hm?)

Lomuto partition scheme

In Lomuto partition scheme implementation there is a mistake. In the worst case scenario j grows as i, giving a memory out of bounds error on the last swap. I correct it, see the history. — Preceding unsigned comment added by Dante DDM (talk • contribs) 23:16, 5 August 2020 (UTC)

@Dante DDM: No mistake there. The i variable will not be incremented in the last iteration of the loop, so we have 'i is less or equal hi' after the loop termination. No risk of out-of-bounds swap (unless you make a mistake in translating the algorithm into the code). --CiaPan (talk) 23:59, 5 August 2020 (UTC)

@CiaPan: I've checked out and misunderstood the code. I apologize for bothering. Dante DDM (talk) 11:49, 8 September 2020 (UTC)

@Dante DDM: That's okay. We all learn from our mistakes. Don't let it to discourage you – It's not the mistake that matters. --CiaPan (talk) 12:35, 11 September 2020 (UTC)

I think the Lomuto partition pseudocode is still wrong. If you partition([2,1],0,1) it will set pivot = 1, i = -1, then on the first loop iteration j=0 and it evaluates A[j] <= pivot or A[0] = 2 <= 1, then in the else it will error trying to swap A[-1] and A[0]. If lo > 0 to start then it will change a value outside of the range. — Preceding unsigned comment added by 75.10.161.2 (talk • contribs)

Nope. There is no 'else' there, so after the A[j] <= pivot comparison which results in false there is no 'else' but just another loop iteration. That one ends immediately, because j = hi - 1 already. So, the control goes to the last three lines, where i gets incremented from –1 to 0, then A[0] gets swapped with A[1] and finally the value 1 is returned. --CiaPan (talk) 11:05, 27 July 2022 (UTC)

Wrongly placed reference? & text attribution

1. Reference 16 (at time of writing) is about the Yaroslavskiy algorithm, but it’s placed in the section about the Lomuto implementation. Shouldn’t it be removed there and inserted elsewhere, maybe in the History section?

The reference text (for reference :) Wild, Sebastian (2012). "Java 7's Dual Pivot Quicksort". Technische Universität Kaiserslautern.

2. The algorithm given in the Algorithm section seems to be taken almost verbatim from Yaroslavskiy (Reference 10). Would it be good to attribute it to that paper?

The reference text again: Yaroslavskiy, Vladimir (2009). "Dual-Pivot Quicksort" (PDF). Archived from the original (PDF) on 2 October 2015.

— Preceding unsigned comment added by Geke (talk • contribs) 25 August 2020 (UTC)

Hoare partition scheme does not preserve randomness

The Hoare partition scheme given here is elegant and similar to the one in Hoare's original paper. This algorithm does not swap the pivot element into the "middle" and fix it into its final place. As a result, when sorting a uniformly random permutation, it does not maintain the randomness in the resulting subarrays. As indicated on p. 35 of Sedgewick's PhD thesis "This bias not only makes analysis of the method virtually impossible, it also slows down the sorting process considerably." For example, the average-case analysis given in this article does not apply to this version of quicksort.

If the goal is to show the preferred way to implement a 2-way partition (e.g., fewer exchanges than Lomuto, doesn't go quadratic with all equal keys, provably ~ 2n ln n compares for random permutations), replace Hoare partition scheme with the Sedgewick-Hoare partition scheme, which does swap the pivot element into its final place (and preserve randomness). Alternatively, add a warning in the analysis section that it is not applicable to quicksort with the Hoare partition scheme.

Algorithms4 (talk) 18:20, 7 March 2022 (UTC)

"Quicksort" vs "quicksort"

The article seems to be inconsistent about whether its subject should be capitalised in general usage or not. E.g. currently in the introduction we see the following two usages (my italics): "Efficient implementations of Quicksort are not a stable sort […]", and "Mathematical analysis of quicksort shows that […]". It would be preferable to consistently use one style in the article. — Preceding unsigned comment added by 89.247.165.22 (talk) 13:13, 9 October 2022 (UTC)

Finding pivot - ERROR

There is a an error in finding the mid-point for the pivot.

pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array

This is a problem for large values of hi and/or lo. The hi+lo part may overflow the integer type of hi/lo - so you would get a false value.

This should be:

pivot := A[ floor((hi - lo)/2) + lo ] // The value in the middle of the array

This gives the same result, with no risk of overflowing.

Please update - the former code should not be used. 89.134.22.144 (talk) 10:21, 22 November 2022 (UTC)