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:
PHP
<?php
// PHP program to sort an array
// with 0, 1 and 2 in a single pass
// Sort the input array, the array is
// assumed to have values in {0, 1, 2}
function
sort012(&
$a
,
$arr_size
)
{
$lo
= 0;
$hi
=
$arr_size
- 1;
$mid
= 0;
while
(
$mid
<=
$hi
)
{
switch
(
$a
[
$mid
])
{
case
0:
swap(
$a
[
$lo
++],
$a
[
$mid
++]);
break
;
case
1:
$mid
++;
break
;
case
2:
swap(
$a
[
$mid
],
$a
[
$hi
--]);
break
;
}
}
}
// Utility functions
function
swap(&
$a
, &
$b
)
{
$temp
=
$a
;
$a
=
$b
;
$b
=
$temp
;
}
/* Utility function to print
array arr[] */
function
printArray(&
$arr
,
$arr_size
)
{
for
(
$i
= 0;
$i
<
$arr_size
;
$i
++)
echo
$arr
[
$i
].
" "
;
echo
""
;
}
// Driver Code
$arr
=
array
(0, 1, 1, 0, 1, 2,
1, 2, 0, 0, 0, 1);
$arr_size
= sizeof(
$arr
);
sort012(
$arr
,
$arr_size
);
echo
"array after segregation "
;
printArray(
$arr
,
$arr_size
);
// This code is contributed by ChitraNayal
?>
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