Arranging odd and even numbers in a vector C++

This may not be a perfect solution and it just popped out right off my mind without being tested or verified, but it's just to give you an idea.

(Let A,B,C,D be odd numbers and 0,1,2 even numbers correspondingly)

Given:

A 0 B C D 1 2 (random ordered list of odd/even numbers)

Wanted:

A 0 B 1 C 2 D (input sequence altered to match the wanted odd/even criteria)

Next, we invent the steps required to get from given to wanted:

// look at 'A' -> match, next
// Result: A 0 B C D 1 2  

// look at '0' -> match, next
// Result: A 0 B C D 1 2

// look at 'B' -> match, next
// Result: A 0 B C D 1 2

// look at 'C' -> mismatch, remember index and find first match starting from index+1
// Result: A 0 B C D ->1<- 2 

// now swap the numbers found at the remembered index and the found one.
// Result: A 0 B 1 D C 2 

// continue until the whole list has been consumed.

As I said, this algorithm may not be perfect, but my intention is to give you an example on how to solve these kinds of problems. It's not good to always think in code first, especially not with a problem like this. So you should first think about where you start, what you want to achieve and then carefully think of how to get there step by step.

I feel I have to mention that I did not provide an example in real code, because once you got the idea, the execution should be pretty much straight forward.

Oh, and just a small remark: Almost nothing about your code is C++.

A simple solution, that is not very efficient would be to split the vector into 2 vectors, that contain even and uneven numbers and then always take one from the even, one from the uneven and then the remainder, from the one that is not completely entered.

some c++ (that actually uses vectors, but you can use an array the same way, but need to change the pointer arithmetic) I did not test it, but the principle should be clear; it is not very efficient though

EDIT: The answer below by @AAAAAAAAARGH outlines a better algorithmic idea, that is inplace and more efficient.

void change_vector_even_uneven(std::vector<unsigned>& in_vec){
      std::vector<unsigned> even;
      std::vector<unsigned> uneven;
  
      for (auto it = in_vec.begin(); it != in_vec.end(); it++){
          if ((*it) % 2 == 0)) even.push_back(*it);
          else uneven.push_back(*it);
      }
      
      auto even_it = even.begin();
      auto uneven_it = uneven.begin();
      for (auto it = in_vec.begin(); it != in_vec.end(); it++){
          if (even_it == even.end()){
              (*it) = (*uneven_it);
              uneven_it++;
              continue; 
          }   
          if (uneven_it == uneven.end()){
              (*it) = (*even_it);
              even_it++;
              continue;
          }   
          if ((it - in_vec.begin()) % 2 == 0){
              (*it) = (*even_it);
              even_it++;
          }
          else{
              (*it) = (*uneven_it);
              uneven_it++;
          }   
      }   
  }  

The solutions is simple. We sort the even and odd values into a data structure. In a loop, we iterate over all source values. If they are even (val & 2 == 0) we add them at the end of a std::deque for evens and if odd, we add them to a std::deque for odds.

Later, we we will extract the the values from the front of the std::deque.

So, we have a first in first out principle. The std::deque is optimized for such purposes.

Later, we make a loop with an alternating branch in it. We, alternatively extract data from the even queue and then from the odd queue. If a queue is empty, we do not extract data.

We do not need an additional std::vector and can reuse the old one.

With that, we do not need to take care for the same number of evens and odds. It will of course always work.

Please see below one of millions of possible solutions:

#include <iostream>
#include <vector>
#include <deque>

int main() {

    std::vector testData{ 2, 6, 7, 8, 9, 3, 5, 1 };

    // Show initial data
    std::cout << "\nInitial data: ";
    for (const int i : testData) std::cout << i << ' ';
    std::cout << '\n';

    // We will use a deques to store odd and even numbers
    // With that we can efficiently push back and pop front
    std::deque<int> evenNumbers{};
    std::deque<int> oddNumbers{};

    // Sort the original data into the specific container
    for (const int number : testData)
        if (number % 2 == 0) 
            evenNumbers.push_back(number);
        else 
            oddNumbers.push_back(number);

    // Take alternating the data from the even and the odd values
    bool takeEven{ true };
    for (size_t i{}; !evenNumbers.empty() && !oddNumbers.empty(); ) {

        if (takeEven) {  // Take even numbers
            if (not evenNumbers.empty()) {          // As long as there are even values
                testData[i] = evenNumbers.front();  // Get the value from the front
                evenNumbers.pop_front();            // Remove first value
                ++i;
            }
        } 
        else { // Now we take odd numbers
            if (not oddNumbers.empty()) {           // As long as there are odd values
                testData[i] = oddNumbers.front();   // Get the value from the front
                oddNumbers.pop_front();             // Remove first value
                ++i;
            }
        }
        // Next take the other container
        takeEven = not takeEven;
    }

    // Show result
    std::cout << "\nResult:       ";
    for (const int i : testData) std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

Here is yet another solution (using STL), in case you want a stable result (that is, the order of your values is preserved).

  #include <algorithm>
  #include <vector>

  auto ints = std::vector<int>{ 2, 6, 7, 8, 9, 3, 5, 1 };

  // split list to even/odd sections -> [2, 6, 8, 7, 9, 3, 5, 1]
  const auto it = std::stable_partition(
    ints.begin(), ints.end(), [](auto value) { return value % 2 == 0; });

  auto results = std::vector<int>{};
  results.reserve(ints.size());

  // merge both parts with equal size
  auto a = ints.begin(), b = it;
  while (a != it && b != ints.end()) {
    results.push_back(*a++);
    results.push_back(*b++);
  }

  // copy remaining values to end of list
  std::copy(a, it, std::back_inserter(results));
  std::copy(b, ints.end(), std::back_inserter(results));

The result ist [2, 7, 6, 9, 8, 3, 5, 1]. The complexity is O(n).

This answer, like some of the others, divides the data and then reassembles the result. The standard library std::partition_copy is used to separate the even and odd numbers into two containers. Then the interleave function assembles the result by alternately copying from two input ranges.

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

template <typename InIt1, typename InIt2, typename OutIt>
OutIt interleave(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest)
{
    for (;;) {
        if (first1 == last1) {
            return std::copy(first2, last2, dest);
        }
        *dest++ = *first1++;

        if (first2 == last2) {
            return std::copy(first1, last1, dest);
        }
        *dest++ = *first2++;
    }
}

void reorder_even_odd(std::vector<int> &data)
{
    auto is_even = [](int value) { return (value & 1) == 0; };

    // split
    std::vector<int> even, odd;
    std::partition_copy(begin(data), end(data), back_inserter(even), back_inserter(odd), is_even);

    // merge
    interleave(begin(even), end(even), begin(odd), end(odd), begin(data));
}

int main()
{
    std::vector<int> data{ 2, 6, 7, 8, 9, 3, 5, 1 };

    reorder_even_odd(data);

    for (int value : data) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

Demo on Compiler Explorer

As suggested, I am using vectors and STL. No need to be a great mathematician to understand v_pozitie will start with pairs of odd and even and terminate with the integers not in the initial pairs. I am then updating three iterators in v_positie (no need of temporary containers to calculate the result) : even, odd and end,(avoiding push_back) and would code this way :

#include <vector>
#include <algorithm>

void vector_pozitii_pare_impare(std::vector<int>& v_initial, std::vector<int>& v_pozitie) {

  int nodd (0), neven (0);
  std::for_each (v_initial.begin (), v_initial.end (), [&nodd] (const int& n) {
    nodd += n%2;
  });
  neven = v_initial.size () - nodd;

  int npair (neven < nodd ?neven:nodd); 
  npair *=2;
  std::vector<int>::iterator iend (&v_pozitie [npair]), ieven (v_pozitie.begin ()), iodd (&v_pozitie [1]);

  std::for_each (v_initial.begin (), v_initial.end (), [&iend, &ieven, &iodd, &npair] (const int& s) {
    if (npair) {
      switch (s%2) {
      case 0 :
        *ieven++ = s;
        ++ieven;
        break;
      case 1 :
        *iodd++ = s;
        ++iodd;
        break;
      }
      --npair;
    }
    else *iend++ = s;
  });
}

int main (int argc, char* argv []) {
  const int N = 8;
  int tab [N] = {2, 6, 7, 8, 9, 3, 5, 1};
  std::vector<int> v_initial (tab, (int*)&tab [N]);
  std::cout << "\tv_initial == ";
  std::for_each (v_initial.begin (), v_initial.end (), [] (const int& s) {std::cout << s << "  ";});
  std::cout << std::endl;

  std::vector<int> v_pozitie (v_initial.size (), -1);
  vector_pozitii_pare_impare (v_initial, v_pozitie);
  
  std::cout << "\tv_pozitie == ";
  std::for_each (v_pozitie.begin (), v_pozitie.end (), [] (const int& s) {std::cout << s << "  ";});
  std::cout << std::endl;  
}