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:
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:
C
// C program to sort an array with
// 0, 1 and 2 in a single pass
#include <stdio.h>
// Function to swap *a and *b
void
swap(
int
* a,
int
* b);
// Sort the input array, the array is
// assumed to have values in {0, 1, 2}
void
sort012(
int
a[],
int
arr_size)
{
int
lo = 0;
int
hi = arr_size - 1;
int
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
void
swap(
int
* a,
int
* b)
{
int
temp = *a;
*a = *b;
*b = temp;
}
/* Utility function to print
array arr[] */
void
printArray(
int
arr[],
int
arr_size)
{
int
i;
for
(i = 0; i < arr_size; i++)
printf
(
"%d "
, arr[i]);
printf
(
"n"
);
}
// Driver code
int
main()
{
int
arr[] = {0, 1, 1, 0, 1, 2,
1, 2, 0, 0, 0, 1};
int
arr_size =
sizeof
(arr) /
sizeof
(arr[0]);
int
i;
sort012(arr, arr_size);
printf
(
"array after segregation "
);
printArray(arr, arr_size);
getchar
();
return
0;
}
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.
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