views:

92

answers:

3

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.

+2  A: 

It is possible to do it in O(n) time and O(1) space apparently. The paper Stable minimum space partitioning in linear time by Jyrki Katajainen, and Tomi Pasanen claims to be able to do it.

Google for stable 0-1 sort.

Moron
Thanks. Unfortunately, the article is only avalable by subscription, but at least now I know that it is 1) possible, 2) non-trivial :)
AndreyT
It's available for free from CiteSeer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.5554
Ants Aasma
@Ants Aasma: Thank you for the link. I have updated the answer with that.
Moron
A: 

I don't know O(n) algorithm but here's a simple algorithm with O(n*log(n)) complexity in the worst case. Maybe it will be useful.

Cut off the zeroes from beginning and ones from the end, they are already on their places. Now the array looks like a sequence of ones followed by sequence of zeroes followed by sequence of ones and so on, like this: 1010101010

Exchange the first sequence of ones with the first sequence of zeroes, the third sequence of ones with the third sequence of zeroes and so on. It will become: 0110011001

The amount of sequences became about twice less. Repeat the above procedure until the array is sorted.

To exchange two neighbour sequences reverse the first one, then the second one, and then reverse them both.

rem
This is O(n^2) in the worst case: consider 0 1(n/2 times) 0 1 0 1... 0 1. A simple O(nlogn) solution is to have a lexicographic compare function on (color, index) and use any sort method using that compare function.
Moron
No, the amount of passes is O(log(n)) in the worst case. Here is an example: http://pastebin.com/NyekVWmv
rem
There's no simple in-place stable O(n*log(n)) sorting algorithm. Usually, stable sorting in different libraries is implemented using merge sort which requires O(n) additional memory, see for example GNU C++'s implementation of stable_sort and Sun Java's Arrays.sort.
rem
+1  A: 

This is called Stable Partitioning in C++ and there is a standard algorithm for this: std::stable_partition.

The SGI implementation has an adaptive behavior depending on the amount of memory available:

  • it runs in O(N) if it's possible to allocate O(N) space
  • it runs in O(N log N) swaps in place

I do wonder if the latter in place solution uses a stable sorting algorithm behind the scenes.

Matthieu M.