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

I've come up with the following program to开发者_JS百科 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;
}

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

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.

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.

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.

void my_sort(int* arr, int n){
  int zero = -1;

  for(int i = 0; i < n;i++){
    if(arr[i] == 0){
      zero++; 
      swap(arr[zero],arr[i]);
    }
  }
}

keep a pivot for the last zeroth index and keep swapping all numbers from left to right till you reach the end of the array

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

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

The general solution (if it is not only 0s and 1s) is called "Sorting by Counting". It can always be used if you know that the data is in a certain range. E.g. you want to sort a group of persons by their birthdate, excluding the year. You just make an array of 367 (leap year) days, and every slot in that array is a (linked)list able to hold your data. Now you sweep over your data, calculate the "day of year" from the birthday date of the peersons and append them to the approbriated list.

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

int left = 0;
int right = arr.Length-1;
int first = arr[left];
while (left < right)
{
    if (arr[left] == 0 && arr[right] ==1)
    {
        left++;
        right--;
    }
    else if (arr[left] == 1 && arr[right] == 1)
    {
        right--;
    }
    else if (arr[left] == 0 && arr[right] == 0)
    {
        left++;
    }
    else
    {
        arr[left] = 0;
        arr[right] = 1;
        left++;
        right--;
    }
}

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

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]

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

here's a simple answer:)

int main()
{
    int a[]={1,0,1,1,1,0,1,0,1},size=9,end_value,index1,index2=-1;
    end_value=a[size-1];
    for(index1=0;index1 < size-1;index1++)
    {
        if(a[index1]==end_value )
        {
            index2++;
            a[index2]=!a[index2];
            a[index1]=!a[index1];
        }
    }
    index2++;
    a[index2]=!a[index2];
    a[index1]=!a[index1];
}

This can be done with a simple binary counting sort:

#include <stdio.h>

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

    ptr = arr;
    last = arr + N - 1;
    while (ptr != last)
    {
        if (!*ptr) zeros++;
        ptr++;
    }

    for (i = 0; i < zeros; i++) arr[i] = 0;
    for (; i < N; i++) arr[i] = 1;

    for (i = 0; i < N; i++)
        printf("%d ", arr[i]);
    putchar('\n');

    return 0;
}

This should work fine. Only a single loop will do the job.

int arr[]={0,0,0,1,0,1,0,1,0};
int lastz=7,i=0,temp,n;
n=9;
while(i<n){
        if(arr[i]==0 && i<lastz){
            lastz=i;
        } else if(arr[i]==1 && lastz<i){
            temp=arr[lastz];
            arr[lastz]=arr[i];
            arr[i]=temp;
            lastz++;
        }
        i++;
 }

Here is the C Implementation which will give the solution in O(n) time.

/*
C program to sort a binary array in one pass
Input:  0 1 0 1 1 0
OutPut: 0 0 0 1 1 1
*/

#include<stdio.h>
void segregate0and1(int*, int);

int main()
{
    int a[] = {0, 1, 0, 1, 1, 0};
    int array_length = sizeof(a)/sizeof(a[0]);

    segregate0and1(a, array_length);

    printf("Array after segregation: ");
    for (int i = 0; i < array_length; i++)
        printf("%d ", a[i]);
    printf("\n");    

    return 0;
}

void segregate0and1(int a[], int array_length)
{
    int left = 0, right = array_length-1;

    while (left < right)
    {
        /* Increment left index while we see 0 at left */
        while (a[left] == 0 && left < right)
            left++;

        /* Decrement right index while we see 1 at right */
        while (a[right] == 1 && left < right)
            right--;

        /* If left is smaller than right then there is a 1 at left
          and a 0 at right.  Exchange a[left] and a[right]*/
        if (left < right)
        {
            a[left] = 0;
            a[right] = 1;
        }
    }
}