how to sort an array in descending order using a boolean function?

Question

Since I am new in competitive programming so I am finding this a bit difficult. I encountered a code and I am not able to figure it out, need some help to understand it.

#include<iostream>
#include<algorithm>

using namespace std;
bool mycompare(int a ,int b){

    return a>b;
}

int main(){

    int a[]={5,4,3,1,2,6,7};
    int n =sizeof(a)/sizeof(int);

    sort(a,a+n,mycompare);

    for(int i=0; i<n;i++){
    cout<<a[i]<<"";
    }
    return 0;
}

output:
7 6 5 4 3 2 1 

How does this code work more specifically what does the mycompare function do in the code?

My doubt is that why haven't we passed any arguments in the mycompare() function inside the main() function since the prototype of the function is

bool mycompare(int a, int b);

Answer 1

A comparison-based sorting algorithm sorts the elements solely by pair-wise comparison, i.e., if a < b holds, then a has to be placed before b.

This is a fine approach, but if you limit yourself to using <, it only allows you to sort elements in an ascending order. What if you want to have them in descending order, or any other ordering? This is where the concept of a Comparator (or a Compare callable in the context of the C++ standard) comes into play: It is a binary predicate bool compare(element a, element b) that is supposed to replace the < operator, i.e., a < b becomes compare(a, b) instead. This generalization allows you to encapsulate all types of orderings, in your question you already provided an example where the comparison uses a greater-than operator >, which gives you the aforementioned descending sorted order.

As for how this works internally in C++, the details can be rather complicated, but you can look at it as this:

mycompare without any parameters is a function pointer, i.e. a pointer to the memory address where the machine code for mycompare starts. You can do something like

auto func_pointer = mycompare;
func_pointer(1, 2); // calls mycompare(1, 2)

By giving this function pointer as a parameter to std::sort, you replace the default < comparison function by your own. The way C++ works internally gives the additional advantage that this function call can most likely be inlined, i.e., the compiler avoids the function call can be avoided by copying the code from mycompare into the std::sort invocation, which can speed up your code significantly.

Answer 2

std::sort takes a RandomIt (random iterator) as the first and second arguments that must satisfy the requirements of ValueSwappable and LegacyRandomAccessIterator. Instead of using a Plain-Old-Array of int, you want to use std::array which can then provide the iterators with the member functions .begin() and .end().

Using a proper container from the C++ standard template library makes sorting with std::sort trivial. You need not even provide a custom compare function to sort in descending order as std::less<int>() is provided for you (though your purpose may be to provide the compare function)

Your prototype for mycompare will work fine as is, but preferably the parameters are const type rather than just type, e.g.

bool mycompare(const int a, const int b)
{
    return a > b;
}

The implementation using the array container is quite trivial. Simply declare/initialize your array a and then call std::sort (a.begin(), a.end(), mycompare); A complete working example would be:

#include <iostream>
#include <algorithm>
#include <array>

bool mycompare(const int a, const int b)
{
    return a > b;
}

int main (void) {

    std::array<int, 7> a = { 5, 4, 3, 1, 2, 6, 7 };

    std::sort (a.begin(), a.end(), mycompare);

    for (auto& i : a)
        std::cout << " " << i;
    std::cout << '\n';
}

Example Use/Output

$ ./bin/array_sort
 7 6 5 4 3 2 1

Sorting the Plain Old Array*

If you must use a Plain-Old-Array, then you can use plain-old-pointers as your random iterrators. While not a modern C++ approach, you can handle the plain-old-array with std::sort. You can make use of the builtin std::greater<type>() for a descending sort or std::less<type>() for an ascending sort.

An implementation using pointers would simply be:

#include <iostream>
#include <algorithm>

int main (void) {

    int a[] = { 5, 4, 3, 1, 2, 6, 7 };
    size_t n = sizeof a / sizeof *a;

#if defined (ASCEND)
    std::sort (a, a + n, std::less<int>());
#else
    std::sort (a, a + n, std::greater<int>());
#endif

    for (size_t i = 0; i < n; i++)
        std::cout << " " << a[i];
    std::cout << '\n';
}

(same output unless -DASCEND is added as a define on the commandline, and then an ascending sort will result from the use of std::less<int>())

Look things over and let me know if you have further questions.