CODEWITHSUNDEEP
c++sortingcomparison
Tomme Nguyen
Tomme Nguyen

Reputation: 13

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

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

Upvotes: 0

Views: 1375

Answers (3)

einpoklum
einpoklum

Reputation: 132340

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:

  1. Separate an array into 2 part: the odds and the evens.
  2. Sort the even numbers in ascending order.
  3. 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>{});

Upvotes: 7

cmdLP
cmdLP

Reputation: 1856

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.

Upvotes: 0

Igor Tandetnik
Igor Tandetnik

Reputation: 52621

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);

Upvotes: 3

Related Questions