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} Output: {0, 0, 1, 1, 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}
En esta publicación ( Ordenar una array de 0, 1 y 2 (Conteo simple) ) se analiza una solución simple .
Método 1:
Enfoque: el problema es similar a nuestra publicación anterior Segregar 0 y 1 en una array , y ambos problemas son una variación del famoso problema de la bandera nacional holandesa .
El problema se planteó con tres colores, aquí ‘0’, ‘1’ y ‘2’. La array se divide en cuatro secciones:
- a[1..Lo-1] ceros (rojo)
- a[Lo..Mid-1] unos (blanco)
- a[Medio..Hola] desconocido
- a[Hola+1..N] dos (azul)
- Si el i-ésimo elemento es 0, cambie el elemento al rango bajo, reduciendo así el rango desconocido.
- De manera similar, si el elemento es 1, manténgalo como está pero reduzca el rango desconocido.
- Si el elemento es 2, cámbielo por un elemento de rango alto.
Algoritmo:
- Mantenga tres índices bajo = 1, medio = 1 y alto = N y hay cuatro rangos, 1 a bajo (el rango que contiene 0), bajo a medio (el rango que contiene 1), medio a alto (el rango que contiene elementos desconocidos) y alto a N (el rango que contiene 2).
- Atraviese la array de principio a fin y la mitad es menos que alta. (El contador de bucle es i)
- Si el elemento es 0, intercambie el elemento con el elemento en el índice bajo y actualice bajo = bajo + 1 y medio = medio + 1
- Si el elemento es 1, actualice mid = mid + 1
- Si el elemento es 2, intercambie el elemento con el elemento en el índice alto y actualice alto = alto – 1 y actualice i = i – 1. Como el elemento intercambiado no se procesa
- Imprima la array de salida.
Dry Run:
en la mitad del proceso, se conocen algunos elementos rojos, blancos y azules y están en el lugar «correcto». La sección de elementos desconocidos, a[Mid..Hi], se reduce al examinar a[Mid]:Examinar un [Mid]. Hay tres posibilidades:
a[Mid] es (0) rojo, (1) blanco o (2) azul.
Caso (0) a[Mid] es rojo, intercambie a[Lo] y a[Mid]; Lo++; Medio++
Caso (1) a[Mid] es blanco, Mid++
Caso (2) a[Mid] es azul, intercambie a[Mid] y a[Hi]; Hola-
Continúe hasta Mid>Hola.
Implementación:
Python
# Python program to sort an array with
# 0, 1 and 2 in a single pass
# Function to sort array
def
sort012( a, arr_size):
lo
=
0
hi
=
arr_size
-
1
mid
=
0
while
mid <
=
hi:
if
a[mid]
=
=
0
:
a[lo], a[mid]
=
a[mid], a[lo]
lo
=
lo
+
1
mid
=
mid
+
1
elif
a[mid]
=
=
1
:
mid
=
mid
+
1
else
:
a[mid], a[hi]
=
a[hi], a[mid]
hi
=
hi
-
1
return
a
# Function to print array
def
printArray( a):
for
k
in
a:
print
k,
# Driver Program
arr
=
[
0
,
1
,
1
,
0
,
1
,
2
,
1
,
2
,
0
,
0
,
0
,
1
]
arr_size
=
len
(arr)
arr
=
sort012( arr, arr_size)
print
"Array after segregation :"
,
printArray(arr)
# This code is contributed by Harshit Agrawal
Producción:
array after segregation 0 0 0 0 0 1 1 1 1 1 2 2
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido de la array. - Complejidad espacial: O(1).
No se requiere espacio adicional.
Método 2:
Enfoque: cuente el número de 0, 1 y 2 en la array dada. Luego almacene todos los 0 al principio seguidos de todos los 1 y luego todos los 2.
Algoritmo:
- Mantenga tres contadores c0 para contar 0s, c1 para contar 1s y c2 para contar 2s
- Recorra la array y aumente el recuento de c0 si el elemento es 0, aumente el recuento de c1 si el elemento es 1 y aumente el recuento de c2 si el elemento es 2
- Ahora recorra nuevamente la array y reemplace los primeros elementos c0 con 0, los siguientes elementos c1 con 1 y los siguientes elementos c2 con 2.
Implementación:
Python
# Python implementation of the approach
# Utility function to print contents
# of an array
def
printArr(arr, n):
for
i
in
range
(n):
print
(arr[i],end
=
" "
)
# Function to sort the array of 0s,
# 1s and 2s
def
sortArr(arr, n):
cnt0
=
0
cnt1
=
0
cnt2
=
0
# Count the number of 0s, 1s and
# 2s in the array
for
i
in
range
(n):
if
arr[i]
=
=
0
:
cnt0
+
=
1
elif
arr[i]
=
=
1
:
cnt1
+
=
1
elif
arr[i]
=
=
2
:
cnt2
+
=
1
# Update the array
i
=
0
# Store all the 0s in the
# beginning
while
(cnt0 >
0
):
arr[i]
=
0
i
+
=
1
cnt0
-
=
1
# Then all the 1s
while
(cnt1 >
0
):
arr[i]
=
1
i
+
=
1
cnt1
-
=
1
# Finally all the 2s
while
(cnt2 >
0
):
arr[i]
=
2
i
+
=
1
cnt2
-
=
1
# Prthe sorted array
printArr(arr, n)
# Driver code
arr
=
[
0
,
1
,
1
,
0
,
1
,
2
,
1
,
2
,
0
,
0
,
0
,
1
]
n
=
len
(arr)
sortArr(arr, n)
# This code is contributed by shubhamsingh10
Producción:
0 0 0 0 0 1 1 1 1 1 2 2
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesitan dos recorridos de la array. - Complejidad espacial: O(1).
Como no se requiere espacio adicional.
Consulte el artículo completo sobre Ordenar una array de 0, 1 y 2 para obtener más detalles.
- Complejidad temporal: O(n).
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA