Programa Java para segregar 0 en el lado izquierdo y 1 en el lado derecho de la array

Se le da una array de 0 y 1 en orden aleatorio. Separe los 0 en el lado izquierdo y los 1 en el lado derecho de la array. El objetivo básico es atravesar los elementos de la array y clasificarlos segregando 0 y 1.
 

Ilustración:

Array de entrada = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 

Array de salida = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 

Enfoques:

1. Uso de la segregación por conteo 
2. Usando la clasificación de una array
3. Usando punteros

A continuación, los tres enfoques se discuten en detalle:

Enfoque 1: 

• Cuente el número de 0s.
• Recorriendo toda la array para buscar índices donde hay ceros presentes
• Manteniendo un conteo e incrementando como 0 aparece
• Imprimir todos los ceros al frente
• El número restante de 1s será 1- (número total de 0s)
• Imprimir los elementos restantes

A continuación se muestra la implementación para segregar 0 y 1 utilizando el algoritmo anterior:

// Java code to Segregate 0s and 1s in an array
 
// Importing generic libraries
import java.util.*;
// Importing Array libraries
import java.util.Arrays;
 
public class GFG {
 
    // Function to segregate 0s and 1s
    static void segregate0and1(int arr[], int n)
    {
        // Counts the no of zeros in array
        int count = 0;
 
        // Iteration over array
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0)
 
                // Incrementing the count
                count++;
        }
 
        // Loop fills the arr with 0 until count
        for (int i = 0; i < count; i++)
            arr[i] = 0;
 
        // Loop fills remaining arr space with 1
        for (int i = count; i < n; i++)
            arr[i] = 1;
    }
 
    // Function to print segregated array
    static void print(int arr[], int n)
    {
        System.out.print("Array after segregation is ");
 
        // Iteration over array
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Main driver function
    public static void main(String[] args)
    {
        // Array taken for consideration
        int arr[] = new int[] { 0, 1, 0, 1, 1, 1 };
 
        // Using inbuilt function to store array size
        int n = arr.length;
 
        // Calling function that segregates array
        segregate0and1(arr, n);
 
        // Printing the above segregated array
        print(arr, n);
    }
}

Producción:

Array after segregation is 0 0 1 1 1 1 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Enfoque 2: Uso de la función sort()

sort() Es java.util.Arrays

Sintaxis:

public static void sort(int[] arr, int from_Index, int to_Index)

Parámetros:

arr        - the array to be sorted
from_Index - the index of the first element, inclusive, to be sorted
to_Index   - the index of the last element, exclusive, to be sorted

Tipo de devolución:

This method doesn't return any value

// Java code to Segregate 0s and 1s in an array
 
// Importing generic libraries
import java.util.*;
 
public class GFG {
 
    // Function to print segregated array
    // Taking arguments- array and array size
    static void print(int arr[], int n)
    {
        System.out.print("Array after segregation is ");
 
        // Iteration over array
        for (int i = 0; i < n; ++i)
 
            // Printing array elements
            System.out.print(arr[i] + " ");
    }
 
    // Main driver function
    public static void main(String[] args)
    {
        // Array taken for consideration
        int arr[] = new int[] { 0, 1, 0, 1, 1, 1 };
 
        // Using length inbuilt function to
        int n = arr.length;
 
        // Using sort inbuilt function
        Arrays.sort(arr);
 
        // Printing elements after executing sorting
        print(arr, n);
    }
}

Producción:

Array after segregation is 0 0 1 1 1 1 

Complejidad de tiempo: O(n*logn)

Espacio Auxiliar: O(1)

Enfoque 3: mantenga el puntero izquierdo e intercambie con la posición de la izquierda cuando se encuentre cero en la array e incremente el puntero izquierdo.

// Java code to Segregate 0s and 1s in an array
 
// Importing generic libraries
import java.util.*;
import java.io.*;
 
class GFG {
 
    // Print function outside main to print elements
    static void print(int a[])
    {
 
        System.out.print("Array after segregation is: ");
 
        // Iteration over array using array
        // class inbuilt function .length()
        for (int i = 0; i < a.length; ++i) {
 
            // Printing elements in array
            System.out.print(a[i] + " ");
        }
    }
 
    // Main driver method
    public static void main(String[] args)
    {
        // Random array taken for consideration
        int a[] = { 1, 1, 0, 0, 0, 0, 1, 1 };
 
        // Maintaining left pointer
        int left = 0;
 
        // Iteration over array using length function
        for (int i = 0; i < a.length; ++i) {
 
            // If zeros are present
            if (a[i] == 0) {
 
                // Swap the elements using
                // temporary variable
                int temp = a[left];
                a[left] = a[i];
                a[i] = temp;
 
                // Pre incrementing left pointer
                ++left;
            }
        }
 
        // Calling above function to
        // print updated array
        print(a);
    }
}

Producción:

Array after segregation is: 0 0 0 0 1 1 1 1 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)