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

There are many solutions to this problem. I shall start with very simple one.

Solution1: count the number of ones in array and fill the front elements of array with those many ones and rest of the array with zeroes. Following code does that-

void zero_to_front(char* c, int n)
{ 
    int count = 0;
    for(int i=0; i<n; i++)
        if(c[i] == 1) count++;

    for(int i=0; i<n; i++)
        if(i<count) c[i]=1;
        else c[i] = 0

}

Time complexity is: O(n)

Solution2: Each time you find 0 in array look for 1 in following positions in array and swap it. Following code does that.

void zero_to_front(int*c, int n){
    int one_pos = -1;
    for (int i = 0; i < n; i++) {
        if (c[i] == 0) {

            if(one_pos == -1)
                one_pos = i+1;
            //Find the position of first one
            while (one_pos < n && c[one_pos] != 1 )
                one_pos++;
            //swap(c[i], c[one_pos]);
            int temp = c[i];
            c[i] = c[one_pos];
            c[one_pos] = temp;
        }

    }
}

Time complexity is: O(n)

Solution3: Sort the array in reverse order. Time complexity is: O(nlogn)

Answer 2

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;
}

Answer 3

This version takes the same form as cmasters' but might be faster depending on your standard library implementation. I know Visual C++ will turn each of these std::fill calls into a memset().

void zero_to_front(char* c, int n)
{
    size_t ones = std::count(c, c + n, '1');
    std::fill(c, c + ones, '1');
    std::fill(c + ones, c + n, '0');
}

Answer 4

This solution will require 1 pass in the array and space O(n). The final result is stored in array result

 void cal(int *data , int* result , int n) {
      int index = n - 1;
      for(int i = 0; i < n; i++){
         if(data[i] == 1){
             result[index--] = 1;
         } 
      } 
  }