Move all negative elements to one side of array

Move all negative elements to one side of array – Suppose you have an array of integers. It consists of both negative and positive numbers and the problem statement asks to shift/move all the negative and positive elements to the left of the array and to the right of the array respectively without using extra space. This will be a solution for move all negative numbers to beginning and positive to end with constant extra space.

Example

 Input:

arr[]={2,4,-10,13,-7,-60,52,8,-19 }

Output:

-10 -7 -60 -19 4 2 52 8 13

Explanation: Since all the numbers are shifted towards left and all the positive number is shifted towards right.

Algorithm

1. Set the j to 0.
2. Traversing the array from 0 to n(exclusively, where n is array’s length).
   1. Check if any element of an array is less than the 0,
      1. Check if i should not be equal to j,
         1. Swap the values of indexes arr[i] and arr[j], and increase the value of j.
3. Print the array.

Explanation for Move all Negative Numbers to Beginning and Positive to End

We are given an array of integer, and the array is containing the positive and negative elements. We have asked to shift all the negative elements to the left and the positive numbers to the right. For this, we are going to swap all the numbers, which are positive and negative elements. Traverse the array first and then check for the negative numbers, if the number is negative then only we will go for swapping the values.

Set the value of j to 0, it will be used for the alternative value to swap with. We will start traversing the array and check for each number as arr[i] is less than 0, if it is less than 0, means we found the negative number, and therefore we will check for if both of the indexes are not same, is all of the above conditions are true, then we will swap the numbers as arr[i] and arr[j] will be swapped, and increase the value of j. we will keep that traversal going on till all the possible values have been traversed and swapped and rearranged according to the given condition.

We have checked that condition that arr[i] is less than 0 because we are just arranging the negative numbers, all negative numbers after swapping will be arranged to the left of the array, and all other positive numbers will be arranged automatically to the right of the array. After all the swapping we have done, we just need to print the array in which the swapping operations performed.

Implementation

C++ program for Move all Negative Numbers to Beginning and Positive to End

#include<iostream>

using namespace std;

void shiftIntegers(int arr[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
        {
            if (i != j)
                swap(arr[i], arr[j]);
            j++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shiftIntegers(arr, n);

    return 0;
}

-10 -7 -60 -19 4 2 52 8 13

Java program to Move all negative elements to one side of array

class rearrangeNegativePositive
{
    public static void shiftIntegers(int arr[], int n)
    {
        int j = 0, temp;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] < 0)
            {
                if (i != j)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                j++;
            }
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
        int n = arr.length;

        shiftIntegers(arr, n);
        printArray(arr, n);
    }
}

-10 -7 -60 -19 4 2 52 8 13

Complexity Analysis for Move all negative elements to one side of array

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(1) as no extra space is required.

Conclusion

This is a program to move all negative numbers to beginning and positive to end with constant extra space in Java and C++.

Reference