Alternate positive and negative numbers in an array

Question

Given an array of positive and negative numbers(no zeroes), I have to arrange them in such a way that the positive and negative numbers should be arranged consecutively.

The number of positive and negative numbers may not be equal i.e. if there is no positive number(or negative) left, then all the remaining negative numbers(or positive) are appended to the end of the array.

The order is important i.e.if input array is {2,-1,-3,-7,-8, 9, 5,-5,-7},then the output array should be {2,-1, 9,-3, 5,-7,-8,-5,-7}. The code is done in O(n) without using another array.

Here is my solution in java, I test it again several case and it works. However, I'm not sure if this run in O(n) time. Basically, I count the number of positive and negative number first. then I have two index i = 0 and j =1. j is always 1 step ahead i. From there I keep checking if the number in i is positive and j is negative, if it isn't, i will iterate through the array until I find the next positive/negative for the correct position and move it to the correct position.

Any suggestion is much appreciated. Thanks!

//array of negative and positive, arrange them so that positive number follow by negative
// if no pos or neg left, the rest append to the array. 
//should be O(n) no additional array
public static void alter(int[] a) {
    int pos = 0;
    int neg = 0;
    int index = 0;
    while (c < a.length) {
        if (a[index] > 0) {
            pos++;
        } else neg++;
        index++;
    }

    int i = 0;
    int j = 1;
    int temp = 0;
    //run until no more positive number or negative number
    while (pos > 0 && neg > 0) {
        //
        if (a[i] > 0) {
            pos--;
            if (a[j] < 0) {
                i += 2;
                j += 2;
                neg--;
            } else // a[j] > 0
            {
                while (a[j] > 0) {
                    j++;
                }
                //a[j] < 0
                neg--;
                //move that number to the appropriate place 
                while (j > i) {
                    temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                    j--;
                } // end while
                i += 2;
                j += 2;
            }
        } else // a[i] < 0
        {
            while (a[i] < 0) {
                i++;
            }
            //a[i] > 0
            //move that number to the appropriate place 
            while (i > (j - 1)) {
                temp = a[i];
                a[i] = a[i - 1];
                a[i - 1] = temp;
                i--;
            }

        } //end else    
    }

}

Answer 1

However, I'm not sure if this run in O(n) time

I do not think it runs in O(n). The moment you have to "find the next correct element and move it to the correct location", you need to

1. Loop over the remainder of the array. Which means that for the worst case scenario (array with all positive elements at the start, and all negative elements at the end) you will loop for each of the positive elements one more time over half of the "unsorted" part of the array
2. When you move the element back to the correct location, you move it position by position. This means you loop once more over the "unsorted" part of the array

Not really sure yet how you would get it running in O(n) if you need to respect the requirement that the ordering must be respected without using a third array.

Answer 2

Yes, it can be done in O(n).

Lets assume that c is current position. And a[c] is positive number.

1) Increment i from c towards end of array until i points to first wrong number (number that have the same sign as previous, in this case positive).

2) Set j := i;

3) Increment j towards end of array until j points to number with wanted sign (in this case - negative).

4) Swap a[i] with a[j].

5) Set c := j;

6) Set j := c + 1;

In each step you always increment i or j or c. Never decrement. Variable i can be incremented no more than n times. Same to j and c.

So maximum number of increments is 3n ~ O(n).

Answer 3

PFB my code. If we will use Stack then it will make our problem more easier.

public class AlternatePosNeg {
public static void main(String[] args) {
    int arr[] = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };

    Stack<Integer> pos = new Stack<>();
    Stack<Integer> neg = new Stack<>();

    int i;

    for (i = 0; i < arr.length; i++) {
        if (arr[i] > 0) {
            pos.push(arr[i]);
        } else {
            neg.push(arr[i]);
        }
    }

    int tempArr[] = new int[arr.length];

    i = 0;

    int sizePos = pos.size();
    int sizeNeg = neg.size();

    while (i < tempArr.length) {
        if (sizePos > sizeNeg) {
            if (pos.size() > 0) {
                tempArr[i] = pos.pop();
            }
            if (neg.size() > 0) {
                tempArr[i + 1] = neg.pop();
                i++;
            }
        } else {
            if (neg.size() > 0) {
                tempArr[i] = neg.pop();
            }
            if (pos.size() > 0) {
                tempArr[i + 1] = pos.pop();
                i++;
            }
        }

        i++;
    }

    for (int no : tempArr) {
        System.out.print(no + " ");
    }
}

}