How to sort vector in c++

user_15569855 0
Viewed 311

I have some vectors like this:

vector<int> vec {3;0;1;0;5}; 
vector<int> vec1{3;2;1;7;5};

I want to sort them in ascending order but, if they contain any elements that are zero, the must be moved to the end of the vector.

My desired result is:

 vector<int> vec {1;3;5;0;0};
 vector<int> vec1 {1;2;3;5;7};

I used the following code; however, the order of elements is unchanged:

std::sort(vec.begin(), vec.end(), [](int a, int b)
            {
              return a < b && a>0;;  
            });

How can I fix this?

c++
3 Answers

Since you want the zeros to appear at the end of the sorted sequence, you could take in consideration this special value in any case.

I suggest the following closure

[](int a, int b)
{
  return a==0 ? false       // a after b in any case
              : b==0 ? true // b after a in any case
                     : a<b; // usual comparison
}
user_115270760

Your sort algorithm should take into account a zero in either position. So, if b is zero, then return true if a is not zero, or false if a is also zero†; otherwise, if a is zero, return false; otherwise (neither is zero), return the result of the normal comparison.

Here's a working example, using your data (note also the correction to the way the vectors are initialized – using a comma separator, rather than a semicolon):

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> vec1{ 3, 0, 1, 0, 5 };
    std::vector<int> vec2{ 3, 2, 1, 7, 5 };

    auto mySort = [](const int& a, const int& b)
    {
        // For "short-circuiting" to work, the ORDER of the comparisons is critical!
        return (b == 0 && a != 0) || (a != 0 && a < b);
    };

    std::sort(vec1.begin(), vec1.end(), mySort);
    for (auto i : vec1) std::cout << i << " "; // 1 3 5 0 0
    std::cout << std::endl;

    std::sort(vec2.begin(), vec2.end(), mySort);
    for (auto i : vec2) std::cout << i << " "; // 1 2 3 5 7
    std::cout << std::endl;

    return 0;
}

† As pointed out in the comment by Nathan Pierson, the comparator function should return false for two equal values, even if those are both zero.

user_108710730

There are answers showing how to write the comparator for std::sort correctly, but another option is to first partition the vector into non-zero and zero elements, and then sort the non-zero elements. This way is less error prone (since you can use the default comparator, instead of writing one), and is more efficient, since you have to sort fewer elements.

auto p = std::partition(std::begin(vec), std::end(vec), 
                        [](int n) { return n; });  

std::sort(std::begin(vec), p);
user_83728530
Related