How to sort an integer array into negative, zero, positive part without changing relative position?

Question

Give an O(n) algorithm which takes as input an array S, then divides S into three sets: negatives, zeros, and positives. Show how to implement this in place, that is, without allocating new memory. And you have to keep the number's relative sequence. for example: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

I am not sure whether or not such an solution exits. The best solutions I can think out are:

Solution 1: Using an extra integer array, then traverse the whole array to get negatives, then 0s, then positives.

Solution 2: Do not keep number's relative sequence. Then loop the array two times:

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
} 

Answer 1

This is an instance of the Dutch national flag problem studied by Edsger Dijkstra. It's interesting in that no stable solution to this problem is known that runs in O(n) time and O(1) space (or at least, the last time I checked the literature, no known solution to the problem exists).

Answer 2

I'm not sure if this helps, but the requirement to stably partition into three classes can be reduced to the problem of stably partitioning into two classes: separate the negative from non-negative, then the positive from non-positive. If the two-class problem can be solved in O(1) space and O(n) time, the solution can be applied twice to solve the original problem.

Answer 3

Zeros are indistinguishable so I presume you don't care whether they get swapped around or even simply overwritten at the end (i.e. we just zero out the middle part after we've finished getting the positive and negative numbers moved to opposite ends of the array).

If you're looking at a situation where the integers are just keys for something bigger, this may well not be the case- you may want zeros preserved and stably partitioned. But if not, here's two insights:

First, your problem is identical to the stable binary partition problem.

An algorithm for your problem of course does stable binary partitions (just an array with no zeros). Contrariwise, if the array has zeros you can still use a binary partition to do the dirty work: scan right through the array, swapping each zero you come across with the next negative value (keeping track of where that was so you don't do n^2 overall scanning), resulting in

[mixed -,+][possibly extra zeros][mixed 0,+].

Then you do two binary partitions to get

[-][+][0][+]

and shift the + values over to get the desired result.

AFAIK with binary partitions you can choose any two of stable, in-place, and O(n). So it looks like you're outta luck, but apparently an in-place O(n*log n) algorithm is known as is an O(n) algorithm using log(n) scratch space.

Second, if you can guarantee that the number of zeros will be at least f(n), the zeros can compensate for the lack of scratch space; it's simple to get a stable in-place partition in time O(n^2/f(n)). In particular, if the zeros will be at least some constant fraction of the array, you get O(n) runtime by just running these two steps till you're done:

1. Scan right through the array, swapping each zero you come across with the next negative value
2. Scan left through the array, swapping each zero you come across with the next positive value

If zeros are just as plentiful as either of the other types, this is done after doing 1 then 2 then 1 again.

Answer 4

Can't this be done simply using any "stable sort" performed with a custom comparitor which only checks the sign?

Edit:
No, that's O(n log n).

One thing you can do in linear time is reduce the problem. Since the zeros can't be ordered (how do you tell one from the other?), you can make a pass where you walk through the array, skipping the zeroes and filling in with the non-zero values. Then add the correct number of zeros at the end.

j=0;
for (i=0;i<N;i++) {
  if (A[i]) {
     A[j++]=A[i];
  }
}
while (j<N) {
   A[j++]=0;
}

Now you can ignore the last section and the problem becomes finding an O(n) algorithm for a stable partition around 0. Unfortunately, the stable_partition function from the c++ stl has only O(n) comparisons, but O(n log n) swaps if no additional space is available.

However, this article: "Stable minimum space partitioning in linear time" seems to indicate that it is possible in O(n). I don't think I understand it well enough to summarize it clearly here.

If that works, The final step is to insert the zeros back inbetween the partitions, which is also O(n), since the zeros have no order to maintain.

Answer 5

The C++ library has a stable_partition algorithm which requires n comparisons and O(n log n) swaps when it runs in-place.

As @Ted points out, the problem requires two applications of this algorithm.