{"post":"

Input: arr = {1,-3,9,-5,-2,6,4,-7}

Output: {-3,-5,-2,-7,9,6,4,1} when order is not maintained.

Output: {-3,-5,-2,-7,9,6,4,1} when order is maintained.

Explanation: The input contains an unsorted array with multiple elements both positive and negative. The output is the rearrangement of the positive and negative elements in the array.

There are two approaches to solve it:

Case 1: Rearrange the array without maintaining the order.
\nCase 2: Rearrange the array with the order maintained.

# Separate/Rearrange the array without maintaining the order

# Algorithm

Pass the given array to the function to rearrange the array elements.
Iterate through the array and find the negative element in the array and replace it with the first encountered positive element.
Then swap the elements and continue the process for all the negative elements.
The rearranged array is displayed on the console.

Code:

#include <iostream>\nusing namespace std;\n\nvoid rearrangePositiveNegativeElements(int arr[], int size){\n    int i, j = 0;\n    for(i = 0; i < size; i++){\n        if(arr[i] < 0){\n            if(i != j){\n                int temp = arr[i];\n                arr[i] = arr[j];\n                arr[j] = temp;\n            }\n            j++;\n        }\n    }\n}\n\nint main(){\n    int numElements, i;\n    cout << \"Enter the number of elements: \" << endl;\n    cin >> numElements;\n    int myArray[numElements];\n    cout << \"Enter the array elements: \" << endl;\n    for(i = 0; i < numElements; i++){\n        cin >> myArray[i];\n    }\n\n    cout << \"Original array is: \" << endl;\n    for(i = 0; i < numElements; i++){\n        cout << myArray[i] << \" \";\n    }\n    cout << endl;\n\n    rearrangePositiveNegativeElements(myArray, numElements);\n\n    cout << \"Rearranged array is: \" << endl;\n    for(i = 0; i < numElements; i++){\n        cout << myArray[i] << \" \";\n    }\n    cout << endl;\n    return 0;\n}\n\n

Output:

Enter the number of elements:\n8\n\nEnter the array elements:\n1\n-3\n9\n-5\n-2\n6\n4\n-7\n\nOriginal array is:\n\n1 -3 9 -5 -2 6 4 -7\n\nRearranged array is:\n\n-3 -5 -2 -7 9 6 4 1\n

Time Complexity: O(N)

# Rearrange the array with the order maintained

# Algorithm

Pass the given array to the function to rearrange the array elements.
Iterate through the array and find the negative element in the array and insert it within the array in the sequence of 0 to n-1 by shifting the positive element one position to the right.
If the encountered element is positive, then skip it and move on to the next element.
The rearranged array is displayed on the console.

Code:

#include <iostream>\nusing namespace std;\n\nvoid rearrangePositiveNegativeElements(int arr[], int size){\n    int i, temp, j;\n    for(i = 1; i < size; i++){\n        temp = arr[i];\n        if (temp > 0)\n            continue;\n\n        j = i - 1;\n\n        while(j >=0 && arr[j] > 0){\n            arr[j + 1] = arr[j];\n            j--;\n        }\n\n        arr[j + 1] = temp;\n    }\n}\n\nint main(){\n    int numElements, i;\n    cout << \"Enter the number of elements: \"<< endl;\n    cin >> numElements;\n    int myArray[numElements];\n    cout << \"Enter the array elements: \" << endl;\n    for(i = 0; i < numElements; i++){\n        cin >> myArray[i];\n    }\n\n    cout << \"Original array is: \" << endl;\n    for(i = 0; i < numElements; i++){\n        cout << myArray[i] << \" \";\n    }\n    cout << endl;\n\n    rearrangePositiveNegativeElements(myArray, numElements);\n\n    cout << \"Rearranged array is: \" << endl;\n    for(i = 0; i < numElements; i++){\n        cout << myArray[i] << \" \";\n    }\n    cout << endl;\n    return 0;\n}\n\n

Output:

Enter the number of elements:\n8\n\nEnter the array elements:\n1\n-3\n9\n-5\n-2\n6\n4\n-7\n\nOriginal array is:\n\n1 -3 9 -5 -2 6 4 -7\n\nRearranged array is:\n\n-3 -5 -2 -7 1 9 6 4\n

Time Complexity: O(N^2)

# Optimized Algorithm for Case 2

Pass the given array to the function to rearrange the array elements.
Iterate through the array and sort the elements using merge sort.
While positioning the elements in the subarray place first the negative elements of both the right and left subarrays and then the positive elements using additional condition in the algorithm.
The rearranged array is displayed on the console.

Code:

#include <iostream>\n\nusing namespace std;\n\nvoid modified_merge(int arr[], int left, int mid, int right)\n{\n    int i, j, k;\n    int left_size = mid - left + 1;\n    int right_size = right - mid;\n    int left_arr[left_size], right_arr[right_size];\n\n    for (i = 0; i < left_size; i++)\n    {\n        left_arr[i] = arr[left + i];\n    }\n\n    for (j = 0; j < right_size; j++)\n    {\n        right_arr[j] = arr[mid + 1 + j];\n    }\n\n    i = 0;\n    j = 0;\n    k = left;\n\n    while (i < left_size && left_arr[i] < 0)\n    {\n        arr[k++] = left_arr[i++];\n    }\n\n    while (j < right_size && right_arr[j] < 0)\n    {\n        arr[k++] = right_arr[j++];\n    }\n\n    while (i < left_size)\n    {\n        arr[k++] = left_arr[i++];\n    }\n\n    while (j < right_size)\n    {\n        arr[k++] = right_arr[j++];\n    }\n}\n\nvoid rearrange_array(int arr[], int left, int right)\n{\n    if (left < right)\n    {\n        int mid = left + (right - left) / 2;\n        rearrange_array(arr, left, mid);\n        rearrange_array(arr, mid + 1, right);\n        modified_merge(arr, left, mid, right);\n    }\n}\n\nint main()\n{\n    int arr[] = {1, -3, 9, -5, -2, 6, 4, -7};\n    int arr_size = sizeof(arr) / sizeof(arr[0]);\n\n    cout << \"Original array is: \" << endl;\n\n    for (int i = 0; i < arr_size; i++)\n    {\n        cout << arr[i] << \" \";\n    }\n\n    cout << endl;\n\n    rearrange_array(arr, 0, arr_size - 1);\n\n    cout << \"Rearranged array is: \" << endl;\n\n    for (int i = 0; i < arr_size; i++)\n    {\n        cout << arr[i] << \" \";\n    }\n\n    cout << endl;\n\n    return 0;\n}\n\n

Output:

Original array is:\n\n1 -3 9 -5 -2 6 4 -7\n\nRearranged array is:\n\n-3 -5 -2 -7 1 9 6 4\n

Time Complexity: O(NlogN)

This way with more practices of data structures and algorithms we can approach towards efficient source codes of any particular programs.

\n","title":"Separate positive and negative numbers in array","authorDetails":{"name":"Ankita Khan","slug":"ankita-khan"},"seo":{"title":"Separate positive and negative numbers in array"},"description":"Separate positive and negative numbers/values in an array in C++ in O(N) time complexity. We will cover two cases- Case 1: Rearrange the array without maintaining the order. Case 2: Rearrange the array with the order maintained.","slug":"rearrange-positive-and-negative-values-in-an-array-problem/","articleId":"636a83447bb1ce5072622b83","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}