13

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++]);  
    }  
}
Improve this question
13
  • what about three loops, one for each set, doing a bubble swap each time a member of the set is encountered? Commented Mar 18, 2011 at 3:06
  • 1
    Are you partitioning the array into three sets (negative, zero, positive) while keeping relative positions of numbers in each set intact? I'm asking because your example seems contradictory - {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 1, 2, 4}. If items are truly sorted, then -2 appears before -1, and if they are grouped as (-,0,+) while keeping the relative positions of numbers in each group intact, then the result should be {-1, -2, 0, 4, 1, 2} where 4 appears before 1 and 2. Commented Mar 18, 2011 at 3:12
  • @Anurag thank you for your notification. I fixed it. Commented Mar 18, 2011 at 3:16
  • @mmr, I think your algorithm is not O(n), since you have to move elements a lot times, and moving the element might be O(n) itself. Commented Mar 18, 2011 at 3:17
  • Even though your comparison criterion is looser than is typical, it seems to me that this is still a comparison-based sorting, so the O(N log N) lower limit probably still applies. Commented Mar 18, 2011 at 3:41

5 Answers 5

Reset to default
16

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

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

An O(n) time and O(n) space solution is straightforward.
@James McNellis- True, but the OP asked how to do this in-place (I assume that means O(1) memory)
Yep; that would be my assumption.
I don't think this is quite the Dutch national flag problem. In that problem, no element can be moved more than once and the elements of each class are indistinguishable (there is no stability requirement). The present problem allows elements to be moved up to O(1) times but the elements must be partitioned in a stable way.
This is a variant of the DNF problem for stable ternary partitioning. You're correct that it's not a perfect fit, but my claim that this hasn't yet been solved still holds. Thanks for pointing that out,
3

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.

Improve this answer

Comments

1

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.

Improve this answer

1 Comment

can you please extend this answer with references to back up your statements?
0

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.