Stable separation for two classes of elements in an array
- by AndreyT
Consider the following problem.
We are given an array of elements belonging to one two classes: either red or blue. We have to rearrange the elements of the array so that all blue elements come first (and all red elements follow). The rearrangement must be done is stable fashion, meaning that the relative order of blue elements must be preserved (same for red ones).
Is there a clever algorithm that would perform the above rearrangement in-place?
A non-in place solution is, of course, straightforward.
An obvious in-place solution would be to apply any stable sorting algorithm to the array. However, using a full-fledged sorting algorithm on an array intuitively feels like an overkill, especially taking into account the fact that we are only dealing with two classes of elements.
Any ideas greatly appreciated.
