CODEWITHSUNDEEP
c++stl
Ahmed A
Ahmed A

Reputation: 3652

Custom compare function for stable_sort

I want to sort an array of int32_t, such that all positive numbers (including zero) appears first, followed by all negative number. The relative order of +ve and -ve numbers in the output should be in the same relative order as the input. E.g. 

Input  : 9, 4, -2, -1, 5, 0, -5, -3, 2 <br>
Expected Output : 9, 4, 5, 0, 2, -2, -1, -5, -3

However, I am getting the following output: 

Actual output : 2 0 5 4 9 -3 -5 -1 -2 <br>

The output is partially accurate, +ve then -ve, but the list of +ve and -ve numbers are reversed. Can someone please help.

#include <iostream>
#include <algorithm>
using namespace std;


bool comp(int32_t lhs, int32_t rhs)
{
    if ( (lhs < 0) && (rhs >= 0) )
        return false;
    else
        return true;
}


int main()
{
    vector<int32_t> input{9, 4, -2, -1, 5, 0, -5, -3, 2};

    // sort +ve, then -ve
    stable_sort(input.begin(), input.end(), comp);
    for (int32_t i : input)
        cout << i << " ";
    cout << endl;

    return 0;
}

Thank you, Ahmed.

Upvotes: 2

Views: 2563

Answers (2)

Benjamin Lindley
Benjamin Lindley

Reputation: 103733

Your comparison function does not meet the requirements of a strict weak ordering. Specifically, irreflexivity. That is, for all a,

comp(a, a) == false

In your function, for example, comp(0, 0) would return true. Try this:

bool comp(int32_t lhs, int32_t rhs)
{
    if (lhs < 0)
        return false;
    return rhs < 0;
}

But really, the operation you're describing is a partition. You would be better suited to use std::stable_partition with a predicate that checks if values are >= 0.

auto ge_0 = [](int A) { return A >= 0; };
std::stable_parition(input.begin(), input.end(), ge_0);

Upvotes: 5

Shreevardhan
Shreevardhan

Reputation: 12641

Change your comparator function to this

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool comp(int32_t lhs, int32_t rhs) {
    if ((lhs ^ rhs) >= 0)    // same sign: don't change
        return false;
    else
        return lhs > rhs;
}

int main() {
    vector<int32_t> input{9, 4, -2, -1, 5, 0, -5, -3, 2};
    stable_sort(input.begin(), input.end(), comp);
    for (int32_t i : input)
        cout << i << " ";
    cout << endl;
    return 0;
}

Ideone DEMO

Upvotes: 0

Related Questions