Quicksort Descending Order?

[j1CpDjzh]

I've tried Googling my question, and I've tried experimenting with my code on my own, though I'm not sure how to reverse my Quicksort.

int partition(int userinput[], int p, int r)
{
    int pivot = userinput[r];
    
    while (p < r)
    {
        while (userinput[p] < pivot)
        {
            p++;
        }
        while (userinput[r] > pivot)
        {
            r--;
        }
        if (userinput[p] == userinput[r])
        {
            p++;
        }
        else if (p < r)
        {
            int tmp = userinput[p];
            userinput[p] = userinput[r];
            userinput[r] = tmp;
        }
    }
    return r;
}
void quickSort(int * userinput, int p, int r)
{
    if (p < r)
    {
        int j = partition1(userinput, p, r);
        
        quickSort1(userinput, p, j - 1);
        quickSort1(userinput, j + 1, r);
    }
}

The reason I couldn't figure it out via Google is that all the Quicksorts looked different, and it confused me. Most were solved by reversing the greater than/less than comparisons, but that didn't work for me. What do I have to reverse it?

(P/S: I'm on a Mac, so anything with #include conio.h doesn't work for me.)

[helios]

Where's the definition of quickSort1()?

[Duthomhas]

The difference is in your comparison function, which is what you use to partition(). Lines 7, 11, and 15 use three comparison operators to sort. Try seeing what happens if you swap the < and > operators.

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/#algorithm
(I may have to update that article to be easier to read.)

Also, as helios notes, what's up with lines 34 and 35? Quicksort is recursive.

        quickSort(userinput, p, j - 1);
        quickSort(userinput, j + 1, r);

BTW, I have not validated your algorithm.

[j1CpDjzh]

Thank you, I'll try that out right now and see if it works.

As for lines 34 and 35, I apologize for the confusion - I had originally named it quickSort1 (I'm not entirely sure how it happened myself, but I believe it was a typo), but when posting the code to here, I changed the name and forgot to change lines 34 and 35.

[j1CpDjzh]

Update: After reading that, I have a much better understanding of the quicksort (thank you very much for the link!!). However, even after swapping the comparison operators, I still can't get it to work. It either doesn't sort at all, still sorts in ascending order, outputs a long number like 1606416736764, or the program freezes. I tried playing with lines 9, 13, and 17 but still no luck.

[Duthomhas]

If I get some time tonight I'll take a closer look at your partition function.

[j1CpDjzh]

Alright, I appreciate you taking the time to help me out. Thank you.

[Duthomhas]

You were not messing with the correct lines. Remember, your comparisons need to swap.

7 8 9 10 11 12 13 14

while (userinput[p] > pivot) { p++; } while (userinput[r] < pivot) { r--; }

was < was >

As a point of interest, you can treat "a < b" as a function: less(a,b).
Likewise, you can treat "a > b" as the same function: less(b,a).
Right? The only difference is the order of the arguments. ("a > b" is the same as "b < a".)

Hence, you can rewrite your comparisons as:

        while (less(userinput[p], pivot))
        {
            p++;
        }
        while (less(pivot, userinput[r]))
        {
            r--;
        }

You can then update your function to take a functor for the comparison:

template <typename CompareLess>
int partition(int xs[], int p, int r, CompareLess less)
{
    ...
}

template <typename CompareLess>
void quickSort(int xs[], int p, int r, CompareLess less)
{
    ...
        int j = partition(xs, p, r, compare);
}

Technically, then you would rewrite == as !(less(a,b) or less(b,a)) ...

This gives you the power to make everything about your function generic:

template <typename T, typename CompareLess>
int partition( T xs[], int p, int r, CompareLess less )

Hope this helps.