How to sort std::vector ignoring certain numbers?

Question

I am trying to sort a vector of numbers and ignore a certain number, i.e. leave it in place. This answer does not actually leave the element where it was found.

For example if I have the following

std::vector<int> test{5, 3, 8, 4, -1, 1, 11, 9, 6};
std::sort(test.begin(), 
         std::partition(test.begin(), test.end(), [](int n)
                                                  {return n != -1;}));

Sorts test into 1 3 4 5 6 8 9 11 -1. I searched for a couple hours, and tinkered with both custom comparators and using std::partition, but I cannot come up with a solution that sorts the test vector into 1 3 4 5 -1 6 8 9 11. Is this just practically very difficult?

Answer 1

As per @Bathsheba 's remedy mentioned in his answer, and fooling std::sort()'s predicate, one can achieve the solution something like follows:

DEMO

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

int main()
{
    std::vector<int> test{5, 3, 8, 4, -1, 1, 11, 9, 6};
    // get the position of -1
    auto itr = std::find(test.begin(), test.end(), -1);
    // sort all elements so that -1 will be moved to end of vector
    std::sort(test.begin(), test.end(), [](const int& lhs, const int& rhs )
        {
            if( lhs == -1 ) return false;
            if( rhs == -1 ) return true;
            return lhs < rhs;
        });

    test.erase(test.end()-1);   //  now erase it from end
    test.insert(itr, -1);       //  insert to the earlier position

    for(const auto& it: test)   std::cout << it << " ";

    return 0;
}

Answer 2

Yes, it's tricky to do this using std::sort: you'd somehow have to fool your comparator into inserting the invariant number into the correct place, and that's difficult without examining the other elements beforehand.

A simple remedy is to use an insertion sort; omitting the out-of-place number (but recording the position) when you get to it, and inserting it manually at the end at that recorded position.

Answer 3

Given a vector.

• Find the location of the element you want to leave.
• Swap it out to the end.
• Partial sort the vector (without the last element) - all elements before the selected location will be sorted, after that there will be a random order.
• Swap the element back into the found location
• sort the rest of the vector

The code:

std::vector< int > data{ 5, 3, 8, 4, -1, 1, 11, 9, 6 };

auto chosen_iter = std::find( data.begin(), data.end(), -1 );

std::swap( *chosen_iter, *( data.end() - 1 ) );

std::partial_sort( data.begin(), chosen_iter, data.end() - 1 );

std::swap( *chosen_iter, *( data.end() - 1 ) );

std::sort( chosen_iter + 1, data.end() );

Answer 4

Without swapping the element to the end :

• Find the location of the element.
• Partial sort the vector up to and excluding this location, using a comparator that makes this element greater than the other elements of the vector, so that the element does not appear in the partial sorted part.
• Sort the rest of the vector from this location to the end, using a comparator that makes this element lesser than the other elements of the rest of the vector, this reput this element at this location.

Code :

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

using namespace std;

constexpr int ignored_number = 100;

int main()
{
    vector<int> test{5, 3, 8, 4, ignored_number, 1, 11, 9, 6};

    auto it = find(test.begin(), test.end(), ignored_number);
    partial_sort(test.begin(), it, test.end(), [](int lhs, int rhs) {
        return lhs == ignored_number ? false :
            (rhs == ignored_number ? true : lhs < rhs);
    });
    sort(it, test.end(), [](int lhs, int rhs) {
        return rhs == ignored_number ? false :
            (lhs == ignored_number ? true : lhs < rhs);
    });

    for (const auto& x: test) {
      cout << x << ' ';
    }
    cout << endl;
}