why is my comparator function not working?

Question

I have an array with elements as [0, 1, 0, 3, 12]. I want to shift all the zeros to the end of it while maintaining the relative order of the non-zero elements. After shifting the array should look like this [1, 3, 12, 0, 0]. So to do this I wrote the following code:

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b){
    if (a == 0) {
        return a > b;
    } else {
        return true;
    }
}

int main(){
    int arr[] = {0, 1, 0, 3, 12};
    sort(arr, arr + 5, cmp);
    for (int i: arr) {
        cout << i;
    }
}

I wrote this code thinking that by returning false whenever zero is placed before a non-zero element i can swap the elements but this code gives the output as [12, 3, 1, 0, 0] i.e it just sorted the elements in descending order. Can anyone explain me why my comparator function does not working? Can I use comparator function to do this?

Answer 1

The comparator you pass to std::sort needs to be a strict weak order. In particular, you need cmp(x, x) = false for the same value, and at most one of cmp(x, y) and cmp(y, x) to be true (which is not true for cmp(1, 2) == cmp(2, 1) == true)

What you want in your order is for all elements to be equivalent, except 0 which is greater than all other elements. This can be done with a function like this:

bool cmp(int a, int b) {
    if (a == 0) {
        if (b == 0) return false;  // equal
        return false;  // a is greater
    }
    if (b == 0) return true;  // `a < 0`? True, since 0 is the greatest element
    return false;  // All other elements are equivalent, not less than
}

// Simplified to
bool cmp(int a, int b) {
    return b == 0 && a != 0;
}

And then you want to use std::stable_sort to preserve the order of the equivalent elements.

---

However, sorting isn't the best approach here. You can simply move all the non-zero elements forward, then fill in the back space with 0s:

void move_zeroes_to_back(int* begin, int* end) {
    int* nonzero_begin = begin;
    for (; begin != end; ++begin) {
        if (*begin != 0) *nonzero_begin++ = *begin;
        // else Don't move zero values forward
    }
    // Fill in the rest
    for (; nonzero_begin != end; ++nonzero_begin) {
        *nonzero_begin = 0;
    }
}

Where the first part of this algorithm is what std::remove does:

void move_zeroes_to_back(int* begin, int* end) {
    int* nonzero_end = std::remove(begin, end, 0);  // Remove all zero values
    std::fill(nonzero_end, end, 0);  // Replace removed zero values at the end
}