[09 Feb 2020] Rearrange positive and negative numbers with constant extra space

Rearrange positive and negative numbers with constant extra space

Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like hash table, arrays, etc. The order of appearance should be maintained.

Examples:

Input:  [12 11 -13 -5 6 -7 5 -3 -6] 

Output: [-13 -5 -7 -3 -6 12 11 6 5]

// C++ program to Rearrange positive and negative // numbers in a array #include <stdio.h>    // A utility function to print an array of size n void printArray(int arr[], int n) {     for (int i = 0; i < n; i++)         printf("%d ", arr[i]);     printf("\n"); }    // Function to Rearrange positive and negative // numbers in a array 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;     } }    /* Driver program to test above functions */ int main() {     int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };     int n = sizeof(arr) / sizeof(arr[0]);        RearrangePosNeg(arr, n);     printArray(arr, n);        return 0; }

Output:

-12 -13 -5 -7 -3 -6 11 6 5

Output:

-12 -13 -5 -7 -3 -6 11 6 5

// Java program to Rearrange positive // and negative numbers in a array import java.io.*;    class GFG {     // A utility function to print     // an array of size n     static void printArray(int arr[], int n)     {         for (int i = 0; i < n; i++)             System.out.print(arr[i] + " ");         System.out.println();     }        // Function to Rearrange positive and negative     // numbers in a array     static 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;         }     }        // Driver program     public static void main(String[] args)     {         int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };         int n = arr.length;         RearrangePosNeg(arr, n);         printArray(arr, n);     } }    // This code is contributed by vt_m.

Output:

-12 -13 -5 -7 -3 -6 11 6 5

Output:

-12 -13 -5 -7 -3 -6 11 6 5

Time complexity of above solution is O(n2) and auxiliary space is O(1). We have maintained the order of appearance and have not used any other data structure.

# Python 3 program to Rearrange positive  # and negative numbers in a array    # A utility function to print  # an array of size n def printArray(arr, n):     for i in range(n):         print(arr[i], end = " ")     print()    # Function to Rearrange positive  # and negative numbers in a array def RearrangePosNeg(arr, n):        for i in range(1, n):         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 and arr[j] > 0):             arr[j + 1] = arr[j]             j = j - 1            # Put negative element at its          # right position         arr[j + 1] = key    # Driver Code if __name__ == "__main__":     arr = [ -12, 11, -13, -5,              6, -7, 5, -3, -6 ]     n = len(arr)        RearrangePosNeg(arr, n)     printArray(arr, n)    # This code is contributed # by ChitraNayal

Output:

-12 -13 -5 -7 -3 -6 11 6 5

Output:

-12 -13 -5 -7 -3 -6 11 6 5