GitHub

Move Negative Elements in the Array to one side

Description

An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers.

Constraints

Code

Approach 1: Using built-in sort()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void move(vector<int> &arr)
{
    sort(arr.begin(), arr.end());
}
int main()
{
 
    vector<int> arr = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
    move(arr);
    for (int e : arr)
        cout << e << " ";
    return 0;
}

Explanation

Here we simply use the inbuilt sort function to re-arrange the array arr in an ascending order.

Analysis

Time Complexity: O(n log n)
Space Complexity: O(n)

Approach 2: Two Pointer Method

#include <iostream>
using namespace std;
 
void shiftall(int arr[], int left, int right)
{
    while (left <= right)
    {
 
        if (arr[left] < 0 && arr[right] < 0)
            left += 1;
        else if (arr[left] > 0 && arr[right] < 0)
        {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left += 1;
            right -= 1;
        }
        else if (arr[left] > 0 && arr[right] > 0)
            right -= 1;
        else
        {
            left += 1;
            right -= 1;
        }
    }
}
 
void display(int arr[], int right)
{
    for (int i = 0; i <= right; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main()
{
    int arr[] = {-12, 11, -13, -5,
                6, -7, 5, -3, 11};
    int arr_size = sizeof(arr) /
                sizeof(arr[0]);
 
    shiftall(arr, 0, arr_size - 1);
    display(arr, arr_size - 1);
    return 0;
}

Explanation

The shiftall function takes an array arr, a left index left, and a right index right as input.
The function uses a while loop to iterate while the left index is less than or equal to the right index.
Inside the loop, the function checks the values at the left and right indices of the array.
If both values are negative, the left index is incremented by 1.
If the value at the left index is positive and the value at the right index is negative, the function swaps the values and increments the left index by 1 and decrements the right index by 1.
If both values are positive, the right index is decremented by 1.
If none of the above conditions are met, it means that the value at the left index is negative and the value at the right index is positive. In this case, both indices are incremented and decremented by 1, respectively.
The function continues this shifting operation until the left index exceeds the right index.

Analysis

Time Complexity: O(n)
Space Complexity: O(1)

Sort an Array without using Sorting Algorithm Basics