An Algorithm a Day: Partition an array into positive and negative values
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)
Read full article from An Algorithm a Day: Partition an array into positive and negative values
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)
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.
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;
}http://blueocean-penn.blogspot.com/2014/04/in-place-sort-of-array-of-numbers-by.html
Read full article from An Algorithm a Day: Partition an array into positive and negative values
