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:
JavaScript
<script>
// Javascript program to sort an
// array of 0, 1 and 2
// Sort the input array, the array is
// assumed to have values in {0, 1, 2}
function
sort012(a, arr_size)
{
let lo = 0;
let hi = arr_size - 1;
let mid = 0;
let temp = 0;
while
(mid <= hi)
{
if
(a[mid] == 0)
{
temp = a[lo];
a[lo] = a[mid];
a[mid] = temp;
lo++;
mid++;
}
else
if
(a[mid] == 1)
{
mid++;
}
else
{
temp = a[mid];
a[mid] = a[hi];
a[hi] = temp;
hi--;
}
}
}
/* Utility function to print
array arr[] */
function
printArray(arr, arr_size)
{
let i;
for
(i = 0; i < arr_size; i++)
{
document.write(arr[i] +
" "
);
}
document.write(
"<br>"
);
}
// Driver code
let arr= [0, 1, 1, 0, 1, 2,
1, 2, 0, 0, 0, 1 ];
let arr_size = arr.length;
sort012(arr, arr_size);
document.write(
"Array after seggregation <br>"
)
printArray(arr, arr_size);
// This code is contributed by rag2127
</script>
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:
JavaScript
<script>
// Javascript implementation of the
// approach
// Utility function to print the
// contents of an array
function
printArr( arr, n)
{
for
(let i = 0; i < n; i++)
document.write(arr[i] +
" "
);
}
// Function to sort the array of 0s,
// 1s and 2s
function
sortArr( arr, n)
{
let i, cnt0 = 0, cnt1 = 0,
cnt2 = 0;
// Count the number of 0s, 1s and
// 2s in the array
for
(i = 0; i < n; i++)
{
switch
(arr[i])
{
case
0:
cnt0++;
break
;
case
1:
cnt1++;
break
;
case
2:
cnt2++;
break
;
}
}
// Update the array
i = 0;
// Store all the 0s in the
// beginning
while
(cnt0 > 0)
{
arr[i++] = 0;
cnt0--;
}
// Then all the 1s
while
(cnt1 > 0)
{
arr[i++] = 1;
cnt1--;
}
// Finally all the 2s
while
(cnt2 > 0)
{
arr[i++] = 2;
cnt2--;
}
// Print the sorted array
printArr(arr, n);
}
// Driver code
let arr = [0, 1, 1, 0, 1, 2, 1,
2, 0, 0, 0, 1];
let n = arr.length;
// Function calling
sortArr(arr, n);
// This code is contributed by jana_sayantan.
</script>
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