Написание функции для размещения элементов в массиве

Question

Цель состоит в том, чтобы расположить элементы массива из положительного с левой стороны и отрицательного с правой стороны. Ограничение состоит в том, что должен использоваться только один массив. Также порядок появления элементов должен оставаться неизменным в упорядоченном выходном массиве. Пример ввода

10 (количество элементов в массиве) -6 7 13 10 -8 15 5 -9 2 -1 (элементы массива) Пример вывода

7 13 10 15 5 2 -6 -8 -9 -1

Answer 1

Вам необходимо разбить элементы массива в stable . Как уже предлагалось в комментарии, вы можете использовать шаблон функции std::stable_partition:

template<class BidirIt, class UnaryPredicate>
BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);

Изменение порядка элементов в диапазоне [first, last) таким образом, чтобы всеэлементы, для которых предикат p возвращает true, предшествуют элементам, для которых предикат p возвращает false. Относительный порядок элементов сохраняется.

Например:

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

auto main() -> int {
   std::vector<int> v{0, -1, -7, 3, 5, -9, 2};

   // predicate for partitioning
   auto pred = [](int x) {
      return x >= 0;
   };

   std::stable_partition(v.begin(), v.end(), pred);

   for (auto i: v)
      std::cout << i << ' ';
   std::cout << '\n';
}

Вывод:

0 3 5 2 -1 -7 -9 

Предикат pred возвращает true для элементов, принадлежащих к первой группе (т. Е. Неотрицательных элементов) и false для элементов, принадлежащих ко второй (т. Е. Отрицательных элементов).

Обратите внимание, что оба std::stable_partition и std::partition возвращают итератор к первому элементу второй группы, если вы хотите знать границы группы.