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

Question

I've come up 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; } ```

Accepted Answer

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.

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

Solution

Problem