Talk:Quicksort

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)

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)

The quicksort algorithm is wrong

The quicksort algorithm on this page doesn't work. The algorithm given under Hoare partition scheme gives incorrect results for some carefully chosen inputs.

For example, it will incorrectly sort these integers: [10 0 5 2 4 7 1 6 3 8 9] (the result will be [0 3 4 2 5 6 1 7 9 8 10]).

It's hard to point to exactly one thing that's wrong with the algorithm, but the basic issue is that a carefully chosen input can "hide" an incorrectly sorted value in between [lo, p-1] and [p+1, hi]. The partitioning function must detect and correct.

A correct version of this algorithm can be found, e.g., in Sedgewick & Wayne: Algorithms 4th Edition. I can reproduce it here, if copyright permits (does it permit?) — Preceding unsigned comment added by 212.51.146.228 (talk) 09:34, 2 January 2021 (UTC)

Not true. I have just implemented the algorithm in C and run it at https://www.onlinegdb.com/online_c_compiler. The result was:

Input:  10  0  5  2  4  7  1  6  3  8  9
Result:  0  1  2  3  4  5  6  7  8  9 10

Probably you've made some mistake in translating the algorithm from pseudocode to your favourite programming language.

Below is my code, feel free to test it at OnlineGDB or elsewhere. --CiaPan (talk) 12:10, 2 January 2021 (UTC)

Source in C by CiaPan

#include <stdio.h>

int partition(int array[], int lo, int hi)
{
    int pivot = array[(hi + lo) / 2];
    int i = lo - 1;
    int j = hi + 1;
    while(1)
    {
        do
            i = i + 1;
        while(array[i] < pivot);
        do
            j = j - 1;
        while(array[j] > pivot);
        if(i >= j)
            return j;
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

void quicksort(int array[], int lo, int hi)
{
    if(lo < hi)
    {
        int p = partition(array, lo, hi);
        quicksort(array, lo, p);
        quicksort(array, p + 1, hi);
    }
}

void printArray(int array[], int len, const char* title)
{
    printf("%s", title);

    for(int i = 0; i < len; i++)
        printf("%3d", array[i]);

    printf("\n");
}

int main()
{
    int array[] = {10, 0, 5, 2, 4, 7, 1, 6, 3, 8, 9};
    printArray(array, 11, "Input: ");   // 11 = length of the array
    
    quicksort(array, 0, 10);            // 10 = last index
    printArray(array, 11, "Result:");

    return 0;
}

After a closer look at the result presented I think you confused sorting with partitioning. What you present as a 'result':

[0 3 4 2 5 6 1 7 9 8 10]

is a result of partitioning – the central element 7 has been chosen from the input array, then the array has been reordered into a lower partition with items 0 through 6 and the higher partition with values 8 through 10. Partitions are separated by the pivot value 7:

[0 3 4 2 5 6 1  7  9 8 10]

That, however, does not complete sorting! Now both partitions: [0 3 4 2 5 6 1] and [9 8 10] need to be independently sorted by recursive calls, so that the whole array gets ordered. --CiaPan (talk) 12:47, 2 January 2021 (UTC)

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)