Programa de Python para separar 0 y 1 en una 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. Atraviesa la array solo una vez. 

Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 

Método 1 (Cuenta 0 o 1) 
Gracias a Naveen por sugerir este método. 
1) Cuente el número de 0s. Deje que el conteo sea C. 
2) Una vez que hayamos contado, podemos poner C 0 al principio y 1 en las n – C posiciones restantes en la array.
Complejidad de tiempo : O(n) 

Producción : 

Array after segregation is 0 0 1 1 1 1 

El método 1 atraviesa la array dos veces. El método 2 hace lo mismo en un solo paso.

Método 2 (Usar dos índices para atravesar) 
Mantener dos índices. Inicialice el primer índice a la izquierda como 0 y el segundo índice a la derecha como n-1.
Haz lo siguiente mientras izquierda < derecha 
a) Sigue incrementando el índice a la izquierda mientras haya 0 
b) Sigue disminuyendo el índice a la derecha mientras haya 1 
c) Si la izquierda <derecha entonces intercambia arr[left] y arr[right]

Implementación: 

# Python program to sort a binary array in one pass
  
# Function to put all 0s on left and all 1s on right
def segregate0and1(arr, size):
    # Initialize left and right indexes
    left, right = 0, size-1
      
    while left < right:
        # Increment left index while we see 0 at left
        while arr[left] == 0 and left < right:
            left += 1
  
        # Decrement right index while we see 1 at right
        while arr[right] == 1 and left < right:
            right -= 1
  
        # If left is smaller than right then there is a 1 at left
        # and a 0 at right. Exchange arr[left] and arr[right]
        if left < right:
            arr[left] = 0
            arr[right] = 1
            left += 1
            right -= 1
  
    return arr
  
# driver program to test
arr = [0, 1, 0, 1, 1, 1]
arr_size = len(arr)
print("Array after segregation")
print(segregate0and1(arr, arr_size))
  
# This code is contributed by Pratik Chhajer

Producción: 

Array after segregation is 0 0 1 1 1 1 

Complejidad de tiempo: O(n)

Otro enfoque: 
1. Tome dos punteros type0 (para el elemento 0) comenzando desde el principio (índice = 0) y type1 (para el elemento 1) comenzando desde el final (index = array.length-1). 
Inicialice type0 = 0 y type1 = array.length-1 
2. Está destinado a poner 1 en el lado derecho de la array. Una vez hecho esto, entonces 0 definitivamente estará hacia el lado izquierdo de la array.

Producción: 
 

Array after segregation is 0 0 1 1 1 1 

Complejidad de tiempo: O(n)
Consulte el artículo completo sobre Segregar 0 y 1 en una array para obtener más detalles.