Dada una array A[] que consta de 0, 1 y 2. La tarea es escribir una función que ordene la array dada. Las funciones deben poner todos los 0 primero, luego todos los 1 y todos los 2 al final.
Ejemplos:
Input : {0, 1, 2, 0, 1, 2, 2, 2, 2, 1} Output : {0, 0, 1, 1, 1, 2, 2, 2, 2, 2} Input : {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1} Output : {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Solución simple: creamos tres listas vacías. Agregamos todos los 0 a la primera lista, los 1 a la segunda lista y los 2 a la tercera lista. Finalmente agregamos todas las listas y regresamos
# Function for sort def SortWithoutSorting(arr): # 3 Empty list for initialize 0 1 and 2 l1 =[] l2 =[] l3 =[] for i in range(len(arr)): if arr[i] == 0: l1.append(arr[i]) elif arr[i] == 1: l2.append(arr[i]) else: l3.append(arr[i]) return (l1 + l2 + l3) # Driver Code arr = array.array('i', [0, 1, 0, 1, 2, 2, 0, 1]) print(SortWithoutSorting(arr))
Solución eficiente La solución anterior requiere espacio adicional. Cómo hacerlo sin espacio adicional (en el lugar) en la misma lista dada y usando solo un recorrido. Consulte Ordenar una array de 0, 1 y 2 para la implementación de la solución eficiente.