C++ optimal way of bring the ones to the front of an array of zeros and ones

Question

I'm trying to write the fast and coolest solution to the problem of bringing all the ones to the front of an array of zeros and ones.

I wrote this:

void zeros_to_front(char * c, int n)
{
   char * lastPtr(c);
   for (char * thisCharPtr(c), * endCharPtr(c+n+1); thisCharPtr != endCharPtr; ++thisCharPtr)
   {
      if (*thisCharPtr == '1')
      {
         *lastPtr = '1';
         *thisCharPtr = '0';
          ++lastPtr;
      }
   }
}

int main()
{

   char thisArray[] = {'0', '0', '1', '0', '1', '1', '1'};
   int len = sizeof(thisArray)/sizeof(char);
   zeros_to_front(thisArray, len);
   for (int i = 0; i < len; ++i)
      std::cout << thisArray[i] << " ";

    return 0;
}

A few questions:

• is there a way to simplify

  *lastIdxPtr = '1';
   ++lastIdxPtr;
  

  into 1 line?

• Is there an algorithm that works faster on average?

Answer 1

The fastest way to do this is the two pass counting approach. Why? Because it eliminates the need for a condition in the inner loop, which is expensive. Here is the code:

void zerosToFront(char* c, size_t n) {
    size_t oneCount = 0, i;
    for(i = 0; i < n; i++) oneCount += c[i];
    for(i = 0; i < n - oneCount; i++) c[i] = 0;
    for(     ; i < n; i++) c[i] = 1;
}