Why does std::sort not working with my comp function?

Question

Can someone explain why the 2 last sort function in main does not work while the first one works fine.

The program build with no error. Here is the code:

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

bool comp (int a, int b) {
    if (a % 2 == 0) { return 1; }
    else { return 0; }
}

int main()  {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+n, comp);
    int pos;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 1) {
            pos = i;
            break;
        }
    }
    vector<int> un_sorted;
    for (int i = 0; i < n; i++)
    {
        un_sorted.push_back(arr[i]);
    }
    //7
    //5 9 2 8 6 4 7
    //4 6 8 2 5 9 7
    sort(un_sorted.begin(), un_sorted.begin()+pos-1);
    sort(un_sorted.begin()+pos, un_sorted.end(), greater<int>());
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}

I was trying to separate an array into 2 part: the odds and the evens and then the even are sort ascending and the odds are sorted descending

your function doesn't meet the requirements for a `std::sort` comparator — Alan Birtles, Jan 10 '21 at 16:42
`std::partition` is how you separate a sequence into two parts. `sort(arr, arr+n,comp)` exhibits undefined behavior, since `comp` doesn't meet the requirements of a strict weak ordering. — Igor Tandetnik, Jan 10 '21 at 16:43
@AlanBirtles: Your comment is valid, but I wouldn't mark this question as a dupe. — einpoklum, Jan 10 '21 at 16:44
As a concrete example for the dupe link, `comp(4, 4)` says that 4 should come before 4. It also says 2 should come before 4 in `comp(2, 4)` but that 4 should come before 2 in `comp(4, 2)`. — chris, Jan 10 '21 at 16:44
@einpoklum the behaviour of the program is undefined, that problems only happen later is not surprising, some `std::sort` implementations make go out of bounds of the container with invalid comparators — Alan Birtles, Jan 10 '21 at 16:45
There are multiple bugs in the shown code. Variable length arrays are not standard C++. All even numbers result in undefined behavior because the broken logic will end up using an uninitialized variable. The end sequence iterator parameter to one of the calls to `sort()` is obviously wrong. You will need to fix all these bugs, in addition to the one you asked about, before your program will work correctly, when compiled by any compliant C++ compiler. — Sam Varshavchik, Jan 10 '21 at 16:49
@AlanBirtles: Indeed, but it's still not a dupe IMHO. Have provided an answer. — einpoklum, Jan 10 '21 at 16:50
Your last two `sort` calls sort `un_sorted` vector - but you are printing `arr`, which was not affected by those `sort` calls. You are not actually using `un_sorted` in any way, so it's unclear why you bother to create, populate and sort it. — Igor Tandetnik, Jan 10 '21 at 16:53

einpoklum · Answer 1 · 2021-01-10T19:49:42.137

Problems with your `comp()` function

As @AlanBirtles notes, your comp() function does not induce an order over the elements of your un_sorted array - which is necessary for sorting them.

Specifically,

comp(x,x) is not false for all values of x; so, in a sense, a value can "come before itself" in correct order of array elements.
comp(x,y) and comp(y,x) are sometimes both true - so we can have pairs of elements each of which need to come before the other in the sort order.

therefore it makes no sense to sort using your comp().

Looking at the std::sort() page on cppreference, we read:

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than (i.e. is ordered before) the second.

and as expected std::sort() is not guaranteed to do anything meaningful given your comp(). In fact, your program has undefined behavior, and the compiler is allowed to make the program do anything it likes. The program may crash, may be stuck in an infinite loop, or may do nothing.

Consider using `std::partition()`

You said you wanted to:

Separate an array into 2 part: the odds and the evens.
Sort the even numbers in ascending order.
Sort he odds in descending order.

Well, why not do just that?

The standard library provides two algorithms you can use: std::sort and std::partition. Here's what the code would look like:

auto is_even = [](int x) { return x % 2 == 0; };
auto evens_end_and_odds_begin = 
    std::partition(std::begin(my_array), std::end(my_array), is_even);
std::sort(std::begin(my_array), evens_end_and_odds_begin, std::greater<int>{});
std::sort(evens_end_and_odds_begin, std::end(my_array), std::less<int>{});

score 3 · Answer 2 · answered Jan 10 '21 at 16:50

You can achieve your objective with a single sort call, using a clever comparison function. Something like this:

bool fancy_comparison(int a, int b) {
  bool a_is_even = (a % 2 == 0);
  bool b_is_even = (b % 2 == 0);
  if (a_is_even != b_is_even) {
    // Sort even numbers before odd ones
    return a_is_even;
  }
  if (a_is_even) {
    // Sort two even numbers ascending
    return a < b;
  }
  // Sort two odd numbers descending
  return a > b;
}

And then

sort(arr, arr+n, fancy_comparison);

cmdLP · Answer 3 · 2021-01-10T17:02:46.100

The issue is that you probably assume that the range sorted by sort includes the element that the second parameter points to, called last in most documentations. But ranges in c++ always excludes the element that end points to. C++ always uses half open ranges [begin, end). In your case the element at un_sorted.begin()+pos-1 is excluded, because the first sort call sorts all elements excluding that element. The second starts with the next. You should remove the -1 from the sort call.

When thinking about iterators, indices into arrays can help understanding them. end() is always begin() + size(). When removing the begin from the equation you get a range of indices: [begin, end) is [0, size), note: a half open range you sort the ranges [0, pos-1) and [pos, size), pos-1 is missing. [0, pos) are your even elements. [pos, size) the odd elements.

Why does std::sort not working with my comp function?

3 Answers3

Problems with your comp() function

Consider using std::partition()

Problems with your `comp()` function

Consider using `std::partition()`