⚖️ Segregate negatives and positives ⚖️

Question:

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

Note: Order of elements is not important here.

Logic:

1. Sorting :

   • Take the input as the array
   • sort the array. ( Either inbuilt or self implemented )
   • all the negatives will be seperated from the positives

2. 0 Reference :

   • Take the input as array
   • Declare two pointers i and j
   • i will move from arr [ 0 ]th location to arr [ arr.length - 1 ]th location. in this it will check if arr [ i ] < 0 and i is not equal to j . if yes, then it will swap arr [ i ] and arr [ j ]
   • if no, then it will simply increment j
   • when both i and j will reach the last position, the loop will stop
   • print the array

import java.util.*;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sortArr[] = new int[n];
        int zeroRef[] = new int[n];
        for(int i = 0; i < sortArr.length; i++){
            sortArr[i] = sc.nextInt();
            zeroRef[i] = sortArr[i];
        }

        //This is sorting solution
        Arrays.sort(sortArr);
        System.out.println("Segregation through sorting is: ");
        for(int i = 0; i < sortArr.length; i++){
            System.out.print(sortArr[i]+" ");
        }
        System.out.println();

        //This is 0 reference solution
        int j = 0;
        for(int i = 0; i < zeroRef.length; i++){
            if(zeroRef[i] < 0){
                if(i != j){
                    int temp = zeroRef[i];
                    zeroRef[i] = zeroRef[j];
                    zeroRef[j] = temp;
                }
                j++;
            }
        }

        System.out.println("Segregation through 0 reference method is: ");
        for(int i = 0; i < zeroRef.length; i++){
            System.out.print(zeroRef[i]+" ");
        }
        System.out.println();
    }
}

Comments

[Aaron Reese]

Use array filter to compare i to abs(i) and separate into two arrays then spread the two new arrays into a single array. Original order is preserved and cost is 2N +1

[Kaiwalya Koparkar]

Thanks for that solution. I'll definetly try that out!