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

Asked 2011-03-18T03:04:55.447

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++]);  
    }  
}

arrays algorithm data-partitioning

Edit Report

2 Answers

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).

answered 2011-03-18T05:17:54.757

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:

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

If zeros are just as plentiful as either

answered 2011-08-31T06:42:00.447

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

2 Answers

Your Answer