Re-arrange a string into a { consonant, vowel, consonant, vowel ... } sequence
You have tagged this question with algorithm, and I like algorithm problems. In the spirit of the original question, the solution should not be using any additional space, which means your char vector suggestion at the end is not really relevant. I would agree with your analysis, that the problem is reduced to \$O(n)\$ by storing the vowels and consonants in different vectors, and then merging them again... but that relies on an \$O(n)\$ space complexity too.

I think the solution that the original problem (with no additional storage) is looking for, is a three-pointer option.... a 3-point turn, to make a bad pun.

Consider the following algorithm, which contains three pointers. Each pointer advances sequentially from the beginning to the end of the char array. There is a 'rotate' operation that makes a temp copy of the last char in an array slice, it then shifts all previous chars forward one, and then inserts what was the last char, at the front.

The three pointers consitute an \$O(n)\$ sequence through the data, and the rotate is another \$O(n)\$ operation, but worst-case is n/2, and the worst case will reduce significantly as the pointers advance, and the gap tightens up.... Technically, though, the time complexity combined worst case is \$O(n^2)\$ though.

So, in pseudocode:


set three pointers all to the first char

vowel pointer will, when set, point to the next available vowel - initialize to 0
consonant pointer will, when set, point to the next abailable consonant - initialize to 0
insert pointer - initialize to 0

loop while the insert pointer is valid

advance the vowel pointer to the next vowel (inclusive of the current char)
advance the consonant pointer to the next consonant (inclusive of the current char)
rotate the consonant to the insert pointer.
if the consonant was after the next vowel, indicate that the vowel has advanced 1 char
advance the insert pointer
rotate the vowel to the insert point.
if the vowel was after the consonant, indicate the consonant advanced 1 char
advance the insert pointer
advance the vowel pointer
advance the consonant pointer



So, working off this, and using beginner-level C++ (I am a Java person), I put together the following functions:

bool isVowel( const char ch )
{
  return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

void rotate(char *from, char *to)
{
    char c = *to;

    while (--to &gt;= from)
    {
        *(to + 1) = *to;
    }
    *from = c;
}

void rearange( char *str )
{

  char *vowel, *consonant;
  vowel = str;
  consonant = str;

  while ( *str )
  {
    while (*consonant &amp;&amp; isVowel(*consonant))
    {
        consonant++;
    }
    while (*vowel &amp;&amp; !isVowel(*vowel))
    {
        vowel++;
    }

    rotate (str, consonant);
    if (consonant &gt; vowel)
    {
        vowel++;
    }
    str++;

    rotate (str, vowel);
    if (vowel &gt; consonant)
    {
        consonant++;
    }
    str++;

    consonant++;
    vowel++;
  }

}


This is in an Ideone here;

The advantages here are that the logic for the boolean on_consonant is removed. Additionally, the pointers only ever advance, and never have to be re-located (if you ignore the rotate...)