Puzzle: Sort an array of 0's and 1's in one parse.

c, optimization, sorting

Solution

Let me try this:

void arrange(int a[],int n)
{
    int* p = a;
    int* q = &a[n-1];

    while (p <= q) 
    {
        while (*p == 1 && p <= q) /* Find a Zero, starting from the front */
        {
            ++p;
        }
        while (*q == 0 && p <= q) /* Find a One, starting from the back */
        {
            --q;
        }

        if (p < q) /* *p == Zero, and *q == One, and p is to the left of q. */
        {
            *p = 1; 
            *q = 0;
        }
    }
}

This works with two pointers, one starting at the front, the other starting at the back, and they both move towards the middle until they meet.

Along the way, if the two pointers find a 0 on the left and a 1 on the right, swap the values, then continue.

(code is untested, but the outline seems solid)

Problem

Is it possible to arrange the array made up of only 1's and 0's in descending order within one parse without using auxiliary array? For example: Suppose you have an array `a[]={1,0,0,0,1,0,1}`, for this the expected output will be `a[]={1,1,1,0,0,0,0}`. I have written the below C code but it finds the solution in 2 parses. Could it be optimized? ``` void arrange(int a[],int n) { int i,count=0; for(i=0;i<n;i++) { if(a[i]==1) count++; a[i]=0; } for(i=0;i<count;i++) { a[i]=1; } } ```

Original source