Arrange 0's & 1's

Problem Statement:
-------------------

An array of size n among which there are n/2 0s and n/2 1s arranged in random order.
Arrange all the 1s to left and all 0s to right but it needs to be
stable i.e., the order of 1s and 0s in the i/p array should be maintained.

Expected Complexity:
--------------------------------
O(N) with constant space.


Pseudocode:
--------------------

1. Have two counters, count1 = 0 and count2 = (n/2)+1
2. Traverse thru the array, if(arr[ i ] == 1) { arr[ i ] = count1++;} else { arr[ i ] = count2++ };
3. At the end of the traversal, you have array filled with numbers 0 to n-1


Now the problem reduces to sorting and array of n numbers which has elements from 0 to
n-1 occuring only once which can be done in O(n).

for(j = 0; j <= 1; j++)
{
        for(i = 0; i<n; i++)
        {
                if(arr[ i ] != i)
                {
                        swap(arr[ i ], arr[ arr[ i ] ]);
                }
        }
}
</pre>


Note: j loop runs only twice irrespective on 'n' and has constant complexity. The order of this whole loop is 2*n = O(n).


4. After the array is sorted, Again traverse thru the array and make elements arr[0] to
arr[n/2] to '1' and arr[(n/2)+1] to arr[n] as '0'.


Space complexity is constant and time complexity is O(step2) + O(step3) + O(step4) = n + 2n +n = 4*n = O(n).


Solution #1 (Stable):
------------------------

<pre name='code' class='cpp'>
#include<iostream.h>

int a[] = { 1,0,0,0,1,1,1,0,0,1};
#define _SIZE sizeof(a)/sizeof(a[0])


/* Helper Function */
void printArray()
{
    for(int i=0;i<_SIZE; ++i)
        cout<<a[i]<<" ";

    cout<<endl;
}

int main()
{

    int countOne = 0;
    int countZero = (_SIZE)/2;
    int i = 0;

    /* Fill the array with numbers from 1 to N */
    for(i=0; i < _SIZE; ++i)
    {

        if(a[i] == 1)
        {
            a[i] = countOne;
            countOne++;
        }
        else
        {
            a[i] = countZero;
            countZero++;
        }
    }
    printArray();

    /* Swap the number and make it a sorted one */
    for(int j = 0; j< 2; ++j)
    {
        for(i=0; i < _SIZE; ++i)
        {
                if(a[i] != i)
                {
                        int temp = a[i];
                        a[i] = a[a[i]];
                        a[temp] = temp;
                }
        }


     }


    printArray();

    /* Fill the 1st N/2 elements with 1 */
    for(i=0; i<_SIZE/2; ++i)
        a[i] = 1;


    /* Fill the last N/2 elements with 1 */
    for(i=_SIZE/2; i<_SIZE; i++)
        a[i] = 0;

    printArray();

    return 0;
}

</pre>


Solution #2 (UnStable):
-----------------------------------


Here is a small variation of the quick sort to solve the same problem but this solution is not stable. So I prefer #1.


<pre name='code' class='cpp'>
#include<iostream.h>
using namespace std;
#define _SIZE sizeof(a)/sizeof(a[0])

void swap(int *a, int l, int r)
{
    cout<<"Swaping "<<l<<" "<<r<<endl;

    if(a[l] != a[r])
        a[l] ^= a[r] ^= a[l] ^= a[r];

    return;
}


bool compare_1_upper(int *a, int u, int p)
{

    return (a[u] == p);
}

bool compare_1_lower(int *a, int l, int p)
{
    return (a[l] < p);
}


bool compare_0_upper(int *a, int u, int p)
{
    return (a[u] > p);
}

bool compare_0_lower(int *a, int u, int p)
{
    return (a[u] == p);
}

bool (*funcPtr_upper)(int *, int, int) = 0;
bool (*funcPtr_lower)(int *, int, int) = 0;

void qPartition(int *a, int low, int upper)
{
    int pivot = a[low];
    int l = low - 1;
    int u = upper + 1;
    if(a[low])
    {
        funcPtr_upper = compare_1_upper;
        funcPtr_lower = compare_1_lower;
    }
    else
    {
        funcPtr_upper = compare_0_upper;
        funcPtr_lower = compare_0_lower;
    }
    while(1)
    {
        while(funcPtr_upper(a, --u, pivot));
        while(funcPtr_lower(a, ++l, pivot));
        if(l<u)
            swap(a, l, u);
        else
            return;
    }
    return;
}
int a[] = { 1,1,1,1,1,0,0,1};
void print()
{
    for(int i=0; i< _SIZE; ++i)
        cout<<a[i]<<" ";
    cout<<"\n";
}
int main()
{
    print();
    qPartition(a, 0, _SIZE - 1);
    print();
    return 0;
}