Move all negative numbers to beginning and positive to end with constant extra space

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.

Examples :

Input: -12, 11, -13, -5, 6, -7, 5, -3, -6
Output: -12 -13 -5 -7 -3 -6 11 6 5

Naive approach: The idea is to sort the array of elements, this will make sure that all the negative elements will come before all the positive elements.
Below is the implementation of the above approach:

// Java program to move all negative numbers to the

// beginning and all positive numbers to the end with

// constant extra space

import java.util.*;

public class Gfg {

public static void move(int[] arr)

{

Arrays.sort(arr);

}

// Driver code

public static void main(String[] args)

{

int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };

move(arr);

for (int e : arr)

System.out.print(e + " ");

}

}

Output

Time Complexity: O(n*log(n)), Where n is the length of the given array.
Auxiliary Space: O(n)

--

--

Consulting Engineer @ MongoDB

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store