Hello,
2010/12/4 siva viknesh <[email protected]>:
> Modified 2 color sort problem i.e. you are given an array of integers
> containing only 0s and 1s.You have to place all the 0s in even
> position and 1s in odd position. And if suppose, no. of 0s exceed no.
> of 1s or vice versa then keep them untouched. Do that in ONE PASS and
> without taking extra memory (modify the array in-place).
>
> For Example :
>
> Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
> Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1
> ,1,1}
the problem makes me to recall the quick-sort provided by Knuth in
Introduction to Algorithms, 2ed, here I use some skill like he shows.
eidx = 0 // even index
oidx = 1 // odd index
while (eidx < len && oidx < len):
while (eidx < len && array[eidx] == 1) eidx += 2;
while (oidx < len && array[oidx] == 0) oidx += 2;
if (eidx < len && oidx < len) swap(eidx, oidx);
}
if (eidx < len)
{
p = eidx;
q = (len >> 1) << 1;
while (p < q)
{
while (p < q && array[p] == 1) p += 2;
while (p < q && array[q] == 0) q -= 2;
if (p < q) swap(p, q);
}
}
else if (oidx < len)
// similar to above
--
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.
