Как отсортировать элементы так, чтобы слева находились нечетные элементы, а справа — четные?

Question

[ReD]

Нашёл в сети такое решение:

struct Comparator : public std::binary_function<int, int, bool>
{
    bool operator()(int lhs, int rhs)const
    {
        if (lhs & 1  &&  rhs & 1)
            return lhs < rhs;
        return lhs & 1;
    }
};

std::sort(vec.begin(), vec.end(), Comparator());

Но не понял логику срабатывания условия:

if (lhs & 1 && rhs & 1)

Объясните пожалуйста как работает выражение:
(lhs & 1 && rhs & 1)

Answer 1

[Дмитрий]

Прочитайте про битовые операции. Если коротко, у нечетного числа в бинарном представлении последний бит всегда 1, например 3 это 11, 5 это 101 и тд.

Comments

[ReD]

Спасибо за направление! Теперь ясно!

Answer 2

[Mace_UA]

2017 год. Вам не нужны std::binary_function и прочая устаревшая фигня. Да и можно заюзать лямбду, если этот компаратор нужен только в одном месте кода.

Судя по описанию задачи, Вам нужно не отсортировать массив -- Вам нужно сделать partition.

Воспользуйтесь стандартными алгоритмами std::partition (если относительный порядок чётных и нечётных элементов между собой не важен) или std::stable_partition (если нужно сохранить оригинальный порядок).

Пример:

std::stable_partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 1; });