CODEWITHSUNDEEP
c++sortingstlstdstrict-weak-ordering
Ryan A
Ryan A

Reputation: 45

What's the logic behind the order the elements are passed to a comparison function in std::sort?

I'm practicing lambdas:

 int main()
 {
    std::vector<int> v {1,2,3,4};
    int count = 0;
    sort(v.begin(), v.end(), [](const int& a, const int& b) -> bool
        {
        return a > b;
        });
  }

This is just code from GeeksForGeeks to sort in descending order, nothing special. I added some print statements (but took them out for this post) to see what was going on inside the lambda. They print the entire vector, and the a and b values:

1 2 3 4  
a=2 b=1

2 1 3 4  
a=3 b=2

3 2 1 4  
a=4 b=3

4 3 2 1 <- final

So my more detailed question is: What's the logic behind the order the vector elements are being passed into the a and b parameters?

Is b permanently at index 0 while a is iterating? And if so, isn't it a bit odd that the second param passed to the lambda stays at the first element? Is it compiler-specific? Thanks!

Upvotes: 1

Views: 147

Answers (4)

jfMR
jfMR

Reputation: 24738

By passing a predicate to std::sort(), you are specifying your sorting criterion. The predicate must return true if the first parameter (i.e., a) precedes the second one (i.e., b), for the sorting criterion you are specifying.

Therefore, for your predicate:

return a > b;

If a is greater than b, then a will precede b.

So my more detailed question is: What's the logic behind the order the vector elements are being passed into the a and b parameters?

a and b are just pairs of elements of the elements you are passing to std::sort(). The "logic" will depend on the underlying algorithm that std::sort() implements. The pairs may also differ for calls with identical input due to randomization.

Upvotes: 1

rcgldr
rcgldr

Reputation: 28828

For Visual Studio, std::sort uses insertion sort if the sub-array size is <= 32 elements. For a larger sub-array, it uses intro sort, which is quick sort unless the "recursion" depth gets too deep, in which case it switches to heap sort. The output you program produces appears to correspond to some variation of insertion sort. Since the compare function is "less than", and since insertion sort is looking for out of order due to left values "greater than" right values, the input parameters are swapped.

Upvotes: 1

max66
max66

Reputation: 66200

Is 'b' permanently at index 0 while 'a' is iterating? And if so, isn't it a bit odd that the second param passed to the lambda stays at the first element?

No, because the first element is the higher.

Seems that, with this algorithm, all elements are checked (and maybe switched) with the higher one (at first round) and the higher one is placed in first position; so b ever points to the higher one.

Upvotes: 1

Matthieu Brucher
Matthieu Brucher

Reputation: 22023

You just compare two elements, with a given ordering. This means that if the order is a and then b, then the lambda must return true.

The fact that a or b are the first or the last element of the array, or fixed, depends on the sorting algorithm and of course of your data!

Upvotes: 0

Related Questions