Interview question: C program to sort a binary array in O(n)
Posted
by Zacky112
on Stack Overflow
See other posts from Stack Overflow
or by Zacky112
Published on 2010-01-15T09:45:24Z
Indexed on
2010/04/09
6:33 UTC
Read the original article
Hit count: 170
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;
}
© Stack Overflow or respective owner