How does sorting in descending order works in c++?

Question

I was searching how to sort a vector in a descending order then I found this code

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

It works but I just want to know how it works

Answer 1

The std::sort function expects you^† to give it a function that tells it how to sort a range in ascending order, so by default it'll use something like std::less<int>().

By providing a function with the opposite effect (i.e. std::greater<int>()) you are turning that expectation literally on its head, resulting in a completely legal "mirror-image" of the default behaviour. That is, a reverse sort.

A different way of explaining it is that, at each step of its algorithm, when it wants to know whether one element A should go "before" another element B, it will ask std::greater<int>(), which will tell it: yes, one element A should go "before" another element B if A > B, and there you go.

 5   3   2   1
   >   >   >

This is contrary to the default behaviour which uses something like < instead:

 1   2   3   5
   <   <   <

_{^† Of course, you can actually give it a function that defines any other order you like (subject to certain constraints), so there are plenty more options. Here I explore only the two most obvious sorting methodologies.}

Answer 2

The third argument to std::sort is a functor/function that returns true if the first argument is to be placed before the second element in the sort order.

std::greater<int>::operator()(...) returns true if the first argument is greater than the second argument.

Consequently, use of std::greater<int>() as the third argument to std::sort results in the collection of objects to be sorted in descending order.

Answer 3

The documentation for std::sort (here amongst other places) says things like

Sorts the elements in the range [first, last) in ascending order.

This is a convenient simplification, but it's confusing when you don't want ascending order.

It's more useful to think that sort rearranges your range according so some function - let's call it pre - which says for any pair of elements, which one should come before (precede) the other.

That is, the function looks something like

bool pre(int a, int b); // return true if a should precede b

The default behaviour, if you don't specify something else, is to use std::less, which will do roughly this:

bool less(int a, int b) { return a<b; }

and this default (where the smaller value always precedes the larger) gives you a result sorted in ascending order.

If you specify std::greater, you're saying the larger value should always precede the smaller (because if greater(a,b)==true, that means both that a>b and also that a will precede b in the output).

So, this is the same as saying the result is sorted in descending order.

---

NB. I called the comparison pre both because it tells you which elements should precede which, and also because it is a predicate (specifically a BinaryPredicate and even more specifically a Comparison).