I hope the following approach will work.
Let 'a' be the input array with size n.
int i = 0, j = 1;
while( true)
{
while( i < n && a[i] == 0) i += 2;
while( j < n && a[j] == 1) j += 2;
if ( i < n && j < n ) swap(a[i], a[j]);
if ( i > n && j < n ) {
do single pass 2-color sort only on odd indices from j to n-1
putting 1's before 0's;
break;
}
if ( i < n && j > n ) {
do single pass 2-color sort only on even indices from i to n-1
putting 0's before 1's;
break;
}
}
Every element of the array is touched exactly once and it is in place.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
