Interview question: C program to sort a binary array in O(n)

Question

I've comeup with the following program to do it, but it does not seem to work and goes into infinite loop. Its working is similar to quicksort.

int main()
{
 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int *front, *last;

 front = arr;
 last = arr + N;
 while(front <= last)
 {
  while( (front < last) && (*front == 0) )
   front++;

  while( (front < last) && (*last == 1) )
   last--;

  if( front < last)
  {
   int temp = *front;
   *front = *last;
   *last = temp;
   front ++;
   last--;
  }
 }
 for(int i=0;i<N;i++)
  printf("%d ",arr[i]);

 return 0;
}

Answer 1

You're making it too hard on yourself! You can do it in O(n) knowing only the size of the array n and the sum of the elements S. Since a binary array has only two possibilities for each element, knowing how many there are of one element and the total size is good enough.

Once you know that, just output an array containing S - n zeroes and n ones, in that order. Done!

An alternative approach that doesn't require summing it up first and works in-place is as follows: Place a "write" pointer w at index 0 and a "read" pointer r at index n-1. Iterate backwards with the read pointer, and each time you encounter a 0, write a "0" at w and increment it. When you reach the beginning with r, fill the rest of the array with "1" using w.

Answer 2

I see at least two problems in the program:

Problem 1:

last = arr + N;

is incorrect. It should be:

last = arr + N - 1;

because

(arr + 0) points to 0th ele
(arr + 1) points to 1st ele
...
(arr + N -1) points to (N-1)th ele..which is the last element.

Problem2:
Next your while loop:

while(front <= last)

is incorrect and should be:

while(front < last)

In your case when front and last become equal, your loop continues but neither front nor last get modified at this point, resulting in infinite loop.

When front and last become equal, it makes no point to continue, your array would have been sorted by then.

Answer 3

Do you mean the array only has 0s and 1s?

Sum all the N elements, then overwrite the array :)

int main() {
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
    int N = sizeof arr / sizeof *arr; /* 18 */
    int sum = 0;
    int ndx;
    for (ndx=0; ndx<N; ndx++) sum += arr[ndx];
    for (ndx=0; ndx<N-sum; ndx++) arr[ndx] = 0;
    for (ndx=N-sum; ndx<N; ndx++) arr[ndx] = 1;
}

Answer 4

Your code does not go into an endless loop on my system:

# gcc $CFLAGS -o test test.c
# ./test
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

However the result is wrong. I see 8 times 1, but it should be 9 times one.

As some people pointed out, summing up is a much simpler approach:

#include <stdio.h>

int main() 
{
    int i;
    int count;
    int N = 18;
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};

    /* Sum up all elements */
    i = 0;
    count = 0;
    while (i < N) count += arr[i++];

    /* Overwrite the array */
    i = 0;
    count = N - count;
    while (i < count) arr[i++] = 0;
    while (i < N) arr[i++] = 1;

    /* Print result */
    for (i = 0; i < N; i++) printf("%d ",arr[i]);
}

Answer 5

If you aim at O(n) forget all quicksorts (Θ(nlogn)), bubblesorts etc. No classic sort algorithm achieves O(n) for standard data sets, you must exploit the binary nature of the set.

 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int i,s=0;
 for(i=0;i<N;i++) s+=(arr[i]==0);
 for(i=0;i<N;i++) arr[i]=!(i<s);

Answer 6

The basic idea of your algorithm works well and the implementation can be simplified:

int a[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};

int *begin = a;
int *end = begin + 17;

while (begin < end) {
   if (*begin == 0)
      begin++;
   else if (*end == 1)
      end--;
   else {
      *begin = 0;
      *end = 1;
   }
}

Note that (begin < end) is a stronger condition for termination of the loop and in each iteration of the just one action (moving a pointer or swapping values) is taken, simplifying the code and making it easier to understand that the loop will really terminate.

Answer 7

apparently the other question was closed... your algorithm works perfectly. what i posted in response to maddy in an apparent dup of this redirected here by a person who closed it

int main()
{
  int v[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; int *a, *b, i, n;
  n = sizeof(v) / sizeof(int);
  for (a = v, b = v + n - 1; a < b; ++a) {
    if (*a) {
      for (; *b; --b) if (a == b) goto end;
      *a = 0; *b-- = 1;
    }
  }
  end: for (i = 0; i < n; ++i) printf("%d%s", v[i], (i==n-1?"\n":",")); return 0;
}

moved some lines together to make it fit on the page.... pretty much the same

Answer 8

Reposting here, as the question where I replied got closed (duplicate of this one).

I'm sorry about answering this using Python, but it is an exercise I wanted to do. The code is meant to be verbose, to output the steps of the algorithm. Of course, the translation to C is not difficult, as long as you are careful moving the pointer. Cheers!

# Put zeros on the left, ones on the right in one pass                                                
a = [1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1]
cl = 0
cr = len(a) - 1
print a

while(True):
    if cl + 1 == cr:
        print 'last pass; adjacent elements'
        if a[cl] == 0:
            print 'a[%d] = 0; leave and exit loop' % (cl)
            print 'final array:'
            print a
            break
        if a[cl] == 1:
            print 'a[%d] = 1; try to swap with a[%d]' % (cl, cr)
            if a[cr] == 1:
                print 'a[%d] = 1 as well; leave and exit loop' % (cr)
                print 'final array:'
                print a
                break
            else:
                print 'a[%d] and a[%d] swapped; leave and exit loop' % (cl, cr)
                a[cl] = 0
                a[cr] = 1
                print 'final array:'
                print a
                break
    if a[cl] == 0:
        print 'a[%d] = 0; leave and move on to a[%d]' % (cl,cl+1)
        cl += 1
        continue
    else:
        print 'a[%d] = 1 move to the right' % (cl)
        while(True):
            if a[cr] == 1:
                print 'a[%d] cannot be moved to a[%d], try a[%d]' % (cl, cr, cr-1)
                cr -= 1
                continue
            else:
                print 'a[%d] swapped with a[%d]' % (cl, cr)
                a[cr] = 1
                a[cl] = 0
                cr -= 1
                cl += 1
                print 'next up: a[%d]; right side blocked up to %d' % (cl,cr)
                break
    if (cl + 1) == cr:
        break

Sample output:

[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1]
a[0] = 1 move to the right
a[0] cannot be moved to a[26], try a[25]
a[0] swapped with a[25]
next up: a[1]; right side blocked up to 24
a[1] = 0; leave and move on to a[2]
a[2] = 1 move to the right
a[2] cannot be moved to a[24], try a[23]
a[2] swapped with a[23]
next up: a[3]; right side blocked up to 22
a[3] = 0; leave and move on to a[4]
a[4] = 0; leave and move on to a[5]
a[5] = 1 move to the right
a[5] swapped with a[22]
next up: a[6]; right side blocked up to 21
a[6] = 1 move to the right
a[6] cannot be moved to a[21], try a[20]
a[6] cannot be moved to a[20], try a[19]
a[6] swapped with a[19]
next up: a[7]; right side blocked up to 18
a[7] = 1 move to the right
a[7] swapped with a[18]
next up: a[8]; right side blocked up to 17
a[8] = 0; leave and move on to a[9]
a[9] = 0; leave and move on to a[10]
a[10] = 1 move to the right
a[10] cannot be moved to a[17], try a[16]
a[10] cannot be moved to a[16], try a[15]
a[10] swapped with a[15]
next up: a[11]; right side blocked up to 14
a[11] = 0; leave and move on to a[12]
a[12] = 0; leave and move on to a[13]
last pass; adjacent elements
a[13] = 1; try to swap with a[14]
a[13] and a[14] swapped; leave and exit loop
final array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Answer 9

http://www.allegro.cc/forums/thread/555037/555299#target

Answer 10

Overkill, but you could use Pang Ko's linear time Suffix Array construction algorithm:

http://sites.google.com/site/kopangcn2/software2

That would blow the interviewer's mind :P