Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn) | Algorithms

Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn) | Algorithms
Objec­tive: Rearrange Pos­i­tive and Neg­a­tive Num­bers of an Array so that one side you have pos­i­tive num­bers and other side with neg­a­tive Inte­gers with­out chang­ing their respec­tive order.
Exam­ple : Input :  1 –2 3 –4 5 –6 7 –8 9 –10
ReArranged Out­put :  –2 –4 –6 –8 –10 1 3 5 7 9

Method 1. One naive approach is to have another array of same size and nav­i­gate the input array and one scan place all the neg­a­tive num­bers to the new array and in sec­ond scan place all the pos­i­tive num­bers to new array. Here the Space com­plex­ity will be O(n). We have a bet­ter solu­tion which can solve this in O(1) space.

Method 2: Divide and Con­quer

• This approach is sim­i­lar to merge sort.
• Divide the array into two half, Solve them indi­vid­u­ally and merge them.
• Tricky part is in merging.

Merg­ing: (Neg­a­tive on left side and pos­i­tives on the right side)

• Nav­i­gate the left half of array till you won’t find a pos­i­tive inte­ger and reverse the array after that point.(Say that part is called ‘A’)
• Nav­i­gate the right half of array till you won’t find a pos­i­tive inte­ger and reverse the array before that point. (Say that part is called ‘B’)
• Now reverse the those parts from both the array (A and B)

public class RearrageArrayPositiveNegative {

    int[] arrA;

    public RearrageArrayPositiveNegative(int[] arrA) {

        this.arrA = arrA;

    }

    public void divideGroups(int low, int high) {

        if (low >= high)

            return;

        int mid = (low + high) / 2;

        divideGroups(low, mid);

        divideGroups(mid + 1 , high);

        merge(low, mid, high);

    }

    public void merge(int low, int mid, int high) {

        int l = low;

        int k = mid + 1;

        while (l <= mid && arrA[l] <= 0)

            l++;

        while (k <= high && arrA[k] <= 0)

            k++;

        reverse(l, mid);

        reverse(mid + 1, k - 1);

        reverse(l, k - 1);

    }

    public void reverse(int x, int y) {

        while (y > x) {

            int temp = arrA[x];

            arrA[x] = arrA[y];

            arrA[y] = temp;

            x++;

            y--;

        }

    }

Merge method of standard merge sort algorithm can be modified to solve this problem. While merging two sorted halves say left and right, we need to merge in such a way that negative part of left and right sub-array is copied first followed by positive part of left and right sub-array.

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 = r - m;

    /* create temp arrays */

    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1 + j];

    /* Merge the temp arrays back into arr[l..r]*/

    i = 0; // Initial index of first subarray

    j = 0; // Initial index of second subarray

    k = l; // Initial index of merged subarray

    // Note the order of appearance of elements should

    // be maintained - we copy elements of left subarray

    // first followed by that of right subarray

    // copy negative elements of left subarray

    while (i < n1 && L[i] < 0)

        arr[k++] = L[i++];

    // copy negative elements of right subarray

    while (j < n2 && R[j] < 0)

        arr[k++] = R[j++];

    // copy positive elements of left subarray

    while (i < n1)

        arr[k++] = L[i++];

    // copy positive elements of right subarray

    while (j < n2)

        arr[k++] = R[j++];

}

// Function to Rearrange positive and negative

// numbers in a array

void RearrangePosNeg(int arr[], int l, int r)

{

    if(l < r)

    {

        // Same as (l + r)/2, but avoids overflow for

        // large l and h

        int m = l + (r - l) / 2;

        // Sort first and second halves

        RearrangePosNeg(arr, l, m);

        RearrangePosNeg(arr, m + 1, r);

        merge(arr, l, m, r);

    }

}

Time complexity of above solution is O(n log n). The problem with this approach is we are using auxillary array for merging but we’re not allowed to use any data structure to solve this problem. We can do merging in-place without using any data-structure. The idea is taken from here.

Let Ln and Lp denotes the negative part and positive part of left sub-array respectively. Similarly, Rn and Rp denotes the negative and positive part of right sub-array respectively.
Below are the steps to convert [Ln Lp Rn Rp] to [Ln Rn Lp Rp] without using extra space.

1. Reverse Lp and Rn. We get [Lp] -> [Lp'] and [Rn] -> [Rn'] 
    [Ln Lp Rn Rp] -> [Ln Lp’ Rn’ Rp]

2. Reverse [Lp’ Rn’]. We get [Rn Lp].
 [Ln Lp’ Rn’ Rp] -> [Ln Rn Lp Rp]

http://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/

Approach 1: Modified Insertion Sort

We can modify insertion sort to solve this problem.

Loop from i = 1 to n - 1.
  a) If the current element is positive, do nothing.
  b) If the current element arr[i] is negative, we 
     insert it into sequence arr[0..i-1] such that 
     all positive elements in arr[0..i-1] are shifted 
     one position to their right and arr[i] is inserted
     at index of first positive element.

void RearrangePosNeg(int arr[], int n)

{

    int key, j;

    for(int i = 1; i < n; i++)

    {

        key = arr[i];

        // if current element is positive

        // do nothing

        if (key > 0)

            continue;

        /* if current element is negative,

        shift positive elements of arr[0..i-1],

        to one position to their right */

        j = i - 1;

        while (j >= 0 && arr[j] > 0)

        {

            arr[j + 1] = arr[j];

            j = j - 1;

        }

        // Put negative element at its right position

        arr[j + 1] = key;

    }

}

Read full article from Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn) | Algorithms