Partition an array into positive and negative values

 

Question

You are given the below array

{-3,4,3,-2,-8,6,13,-15}

Now find the point where the negative numbers shifts into positive space. The performance should be at most O(n) and there should be no extra space usage.

Example Output: –3, –2, –8, –15, 4,3,6,13

The index returned should be 4 in this case.. (array index starts from 0)

Concept

    Just think a small concept about how to solve this. If you can get this worked out in mind, you have not forgotten the Partition algorithm we studied for quick sort. (http://analgorithmaday.blogspot.com/2011/02/partitioning-algorithmin-place.html)

In partition algorithm for quick sort, we just move shorter elements to the initial index and larger elements into the end indices. We have to follow the similar fashion here to partition this array. But out pivot is already known and obvious..

Our pivot for this array is always 0.. :) and we have to traverse the whole array once to check for negative numbers (<0). If you find a number less than zero, just put that into our i list. There will be no swapping if the negative numbers are found in-order.

The performance of this code will be O(n) worst case and there is no extra space.

Code

int partition_sign(int* arr, int start, int end)

{

    int i,j, pivot;

    pivot = 0;

    i=start-1;

    for(j=start; j<=end; j++)

    {

        if(arr[j] <= pivot) {

            i=i+1;

            if(i!=j)

                swap(arr[i], arr[j]);

        }

    }

    return i+1;

}

void main()

{

    int A[] = {-3,4,3,-2,-8,6,13,-15};

    int pos = partition_sign(A, 0, 7);

}

• The above partition logic is same as Quick sort partition.. It has many practical use like this. :)
• Instead of >=, we use <= so that all negative numbers come in left side (in-order of occurrence) and positive numbers to the right side (in wrong order of occurrence)
• If you use >=, you will get negative numbers in right side (in wrong order).
• The main use of such logic is to eliminate negative numbers from the array!!