std::sort not sorting vector properly

Question

I want to sort my vector of pairs by the ratio of the first to the second value of the pair. I am using C++ STL sort function but, I don't know, It is not sorting the vector properly here is my code:

comparator

bool comparator(const std::pair<int, int> &item1, const std::pair<int, int> &item2)
{
    return (item1.first / item1.second) < (item2.first / item2.second);
}

sort function call

int main()
{
    std::vector<std::pair<int, int>> items = {{4, 5}, {1, 4}, {3, 5}, {6, 7}, {8, 8}};
    std::sort(items.begin(), items.end(), comparator);
    for (auto item : items)
        std::cout << item.first << ", " << item.second << "\n";
    
    return 0;
}

my output

8, 8
4, 5
1, 4
3, 5
6, 7

expected output

8, 8
6, 7
4, 5
3, 5
1, 4

I also tried

return (double)(item1.first / item1.second) > (double)(item2.first / item2.second);

but it is also giving me another output

4, 5
1, 4
3, 5
6, 7
8, 8

Your comparator is doing integer divisions, which produce an `int` with rounding toward zero. That probably explains your concern. (It's also possible - although I haven't checked - that it doesn't meet the mandatory requirement of a comparator to define a strict-weak ordering - which would cause undefined behaviour). In any event, to avoid the concern with integer division, try `return item1.first*item2.second < item2.first*item1.second` which is mathematically equivalent except for effects of integer division (although there is potential for integer overflow, depending on values provided) — Peter, Jul 24 '22 at 13:05

Vlad from Moscow · Accepted Answer · 2022-07-24T13:05:47.763

1

It seems you want to compare float results like

 return (static_cast<double>( item1.first ) / item1.second) < 
        (static_cast<double>( item2.first ) / item2.second);

In this case the vector will be sorted in the ascending order and the result will be

1, 4
3, 5
4, 5
6, 7
8, 8

If you want to sort the vector in the descending order then use this return statement

return (static_cast<double>( item2.first ) / item2.second) < 
        (static_cast<double>( item1.first ) / item1.second);

In this case the output will be

8, 8
6, 7
4, 5
3, 5
1, 4

As for this return statement

return (double)(item1.first / item1.second) > (double)(item2.first / item2.second);

then in parentheses there is used the integer arithmetic

(item1.first / item1.second)

So casting to double has no effect for the comparison.

edited Jul 24 '22 at 13:05

answered Jul 24 '22 at 12:52

Vlad from Moscow

301,070
26
186
335

I have a question I tried ` return (double)(item1.first / item1.second) < (double)(item2.first / item2.second);`, But why it does not worked? also, why it didn't type-casted? – Sidharth Mudgil Jul 24 '22 at 12:57
@SidharthMudgil It does not work because in the parentheses (item1.first / item1.second) there is used the integer arithmetic. – Vlad from Moscow Jul 24 '22 at 13:00
Another option is to replace `/` with `*` (to avoid floating-point arithmetic). – HolyBlackCat Jul 24 '22 at 13:34

std::sort not sorting vector properly

1 Answers1