Programa Python3 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) 

# Python 3 code to Segregate
# 0s and 1s in an array
  
# Function to segregate 0s and 1s
def segregate0and1(arr, n) :
      
    # Counts the no of zeros in arr
    count = 0 
  
    for i in range(0, n) :
        if (arr[i] == 0) :
            count = count + 1
  
    # Loop fills the arr with 0 until count
    for i in range(0, count) :
        arr[i] = 0
  
    # Loop fills remaining arr space with 1
    for i in range(count, n) :
        arr[i] = 1
          
  
# Function to print segregated array
def print_arr(arr , n) :
    print( "Array after segregation is ",end = "")
  
    for i in range(0, n) :
        print(arr[i] , end = " ")
          
  
# Driver function
arr = [ 0, 1, 0, 1, 1, 1 ]
n = len(arr)
      
segregate0and1(arr, n)
print_arr(arr, n)
  
  
          
# This code is contributed by Nikita Tiwari.

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: 

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.

# 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):
  
    type0 = 0
    type1 = size - 1
      
    while(type0 < type1):
        if(arr[type0] == 1):
            (arr[type0], 
             arr[type1]) = (arr[type1],
                            arr[type0])
            type1 -= 1
        else:
            type0 += 1
      
# Driver Code
arr = [0, 1, 0, 1, 1, 1]
arr_size = len(arr)
segregate0and1(arr, arr_size)
print("Array after segregation is", 
                         end = " ")
for i in range(0, arr_size):
        print(arr[i], end = " ")
  
# This code is contributed
# by Shivi_Aggarwal

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.