Sort using comparator (edition 2)

Programming languages C++
#1

bool compare(int a, int b)
{return a>b}

int arr[n]={1, 3, 2, 2, 7, 5, 4, 6}
sort(arr, arr+n, compare);

What arguments are passed to the compare function by the sort STL function? Is it the 1st and the 2nd element of the array?

What I am really asking is, what is the order in which the comparator function is passed the arguments by the sort function in terms of the range of the array indices? Is it always like:
comparator(a, b) , where ‘a’ will be an element at a lower index than the index of ‘b’? Because there should be some standardization as the order will make a difference.
Or if there is something else to this?

#2

‘a’ will be an element at a lower index than the index of ‘b’ ?

Yes

If you wish the sorting result be in ASC order, write the function like that:

// Comparator Class to compare 2 objects
    class studentcompare {
    public:
        bool operator()(const student& a,
                        const student& b)
        {
            if (a.num < b.num) {
                return true;
            }
            return false;
        }
    };

Change the function to this if you want a DEC order:

if (a.num > b.num) {

2 Likes
#3

I believe that what you’re asking is actually “is std::sort stable?”.

A stable sort is a sort that won’t swap values if they evaluate the same. They’ll be in the same order than before the sort.

std::sort is not guaranteed to be stable, but std::stable_sort is.

You must use a strict comparison in the compare function, though.
For example, if your criteria for higher ranking is a >= b, it won’t preserve the order even if you use std::stable_sort.

1 Like
#4

Is it always (by default) like:
comparator(a, b) , where ‘a’ will be an element at a lower index than the index of ‘b’ ?
Could you answer this for now?

I’ll read about the “stable sort” as well.
And thanks for the explanation. :slight_smile:

#5

So you are saying, the sorting will begin from the
first index onward
for every pair
through the end of the array.

Hence, for compare( a, b),
index of ‘a’ < index of ‘b’ by default i.e. always. Right?

#6

It seems that the first edition was closed by another moderator.
Why did you open this one? Have you sent a private message to this moderator?

#7

When you are just a user of the library, you need not (sometimes should not) care too much how the library is implemented and what algorithm is used.

Is it bubble sort or bisection sort or quick sort or a mixture of them? Irrelevant to your usage. Implementation can change in versions.

Focus on the contract of the functions - what inputs are expected and what outputs are promised.

1 Like
#8

Alrighty. I’ll do that.
Thanks a lot :slight_smile:

#9

Well, it can be interesting to know if the sort is stable or not. It’s part of the contract.
But the implementation doesn’t really matter.

But if you really want to know, std::sort is usually implemented with intro sort, which doesn’t always uses compare(a, b) with a of lower index than b. Hence the potential instability.
And std::stable_sort is usually implemented with merge sort, which always uses compare(a, b) with a of lower index than b. Hence the stability cause if a evaluates the same as b, b won’t be swapped with a so first equally evaluated stays first.

Note for Nicola: he opened a new thread cause his question was misundertood, which I believe is legitimate. It’s a technical question that is not directly answered in cpp doc, especially if you don’t know what sort stability is.

1 Like
#10

Hey!
But if you really want to know, std::sort is usually implemented with intro sort, which doesn’t always uses compare(a, b) with a of lower index than b. Hence the potential instability.

This is interesting! And this was the kinda answer I was looking for.
So thanks a lot for the explanation and for understanding on me opening a new thread! Much appreciated.:slight_smile:

1 Like