Talk:Quicksort/Archive 3

Archive 1

Archive 2

Archive 3

Shouldn't we change the big-O notation to Theta?

In the right box we say that best, worst and average performances are a big-O of something, but can be proven that they're actually Thetas of "something". For example, the average case performance is a $O(n\log _{2}n)$ but actually it is a $\Theta (n\log _{2}n)$ which is a better analysis.— Preceding unsigned comment added by 62.98.214.57 (talk)

The article Big O notation has some context on that, specifically #Use in computer science: "So while all three statements are true, progressively more information is contained in each. In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above)". Does this help? -- Evilninja (talk) 10:39, 11 August 2021 (UTC)

@Evilninja: I've replaced an URL with a wikilink. --CiaPan (talk) 20:49, 11 August 2021 (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)

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)

"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)

Adding a Tradeoffs section

Hello, I am thinking about adding a Tradeoffs section to this article to discuss some of the disadvantages of Quicksort. Some of the topics I am thinking about discussing is its lack stability, and what situations where its performance can degrade to O(n^2), and a few other topics. KaiXuanWen (talk) 20:22, 12 March 2023 (UTC)