Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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++]);  
    }  
} 
like image 923
Gin Avatar asked Mar 18 '11 03:03

Gin


People also ask

How do you sort an array with negative and positive numbers in Javascript?

In order to sort numbers, you'll need to write a function that returns a negative number if a is less than b , returns a positive number if b is less than a , and returns 0 if the numbers are the same. This can easily be accomplished by subtracting the numbers.

How do you sort only positive numbers in an array?

Using brute force approach to sort only positive numbers in the array. We will first filter out the positive numbers from the given array and sort them in required order. After that we will use a temp array to store the sorted array and extra variable to track the elements of the filtered and sorted positive array.


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

like image 77
templatetypedef Avatar answered Sep 28 '22 04:09

templatetypedef


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.

like image 41
Ted Hopp Avatar answered Sep 28 '22 05:09

Ted Hopp