Red de clasificación

En informática , las redes de comparación son dispositivos abstractos formados por un número fijo de "cables" que transportan valores y módulos comparadores que conectan pares de cables, intercambiando los valores si no están en el orden deseado. Estas redes suelen diseñarse para ordenar conjuntos fijos de valores, en cuyo caso se denominan redes de ordenación .

Las redes de ordenación se diferencian de las ordenaciones por comparación generales en que no pueden manejar entradas arbitrariamente grandes y en que su secuencia de comparaciones se establece de antemano, independientemente del resultado de las comparaciones anteriores. Para ordenar un mayor número de entradas, se deben construir nuevas redes de ordenación. Esta independencia de las secuencias de comparación es útil para la ejecución en paralelo y para la implementación en hardware . A pesar de la simplicidad de las redes de ordenación, su teoría es sorprendentemente profunda y compleja. Las redes de ordenación fueron estudiadas por primera vez alrededor de 1954 por Armstrong, Nelson y O'Connor, ^{[ 1 ]} quienes posteriormente patentaron la idea. ^{[ 2 ]}

Las redes de ordenación pueden implementarse tanto en hardware como en software . Donald Knuth describe cómo los comparadores para enteros binarios pueden implementarse como dispositivos electrónicos simples de tres estados. ^{[ 1 ]} Batcher , en 1968, sugirió utilizarlos para construir redes de conmutación para hardware de computadora, reemplazando tanto los buses como los conmutadores de barra cruzada , más rápidos pero más costosos . ^{[ 3 ]} Desde la década de 2000, las redes de ordenación (especialmente la ordenación por fusión bitónica ) son utilizadas por la comunidad GPGPU para construir algoritmos de ordenación que se ejecutan en unidades de procesamiento gráfico . ^{[ 4 ]}

Introducción

Demostración de un comparador en una red de clasificación.

Una red de clasificación consta de dos tipos de elementos: comparadores y cables. Los cables se extienden de izquierda a derecha, transportando valores (uno por cable) que recorren la red simultáneamente. Cada comparador conecta dos cables. Cuando un par de valores, al viajar a través de un par de cables, encuentra un comparador, este intercambia los valores si y solo si el valor del cable superior es mayor o igual que el valor del cable inferior.

En una fórmula, si el cable superior transporta $x$ y el cable inferior transporta $y$ , entonces después de pasar por un comparador los cables transportan $x'=\min(x,y)$ y $y'=\max(x,y)$ , respectivamente, por lo que el par de valores está ordenado. ^{[ 5 ]}^{: 635} Una red de cables y comparadores que ordenará correctamente todas las entradas posibles en orden ascendente se llama red de ordenación o centro de Kruskal. Al reflejar la red, también es posible ordenar todas las entradas en orden descendente.

A continuación se muestra el funcionamiento completo de una red de clasificación simple. Es evidente por qué esta red de clasificación ordena correctamente las entradas; observe que los primeros cuatro comparadores "envían" el valor más grande al fondo y "flotan" el valor más pequeño al principio. El último comparador ordena los dos cables centrales.

Profundidad y eficiencia

La eficiencia de una red de ordenación se puede medir por su tamaño total, es decir, el número de comparadores en la red, o por su profundidad , definida (informalmente) como el mayor número de comparadores que cualquier valor de entrada puede encontrar en su recorrido por la red. Teniendo en cuenta que las redes de ordenación pueden realizar ciertas comparaciones en paralelo (representadas en la notación gráfica por comparadores que se encuentran en la misma línea vertical), y suponiendo que todas las comparaciones toman un tiempo unitario, se puede observar que la profundidad de la red es igual al número de pasos de tiempo necesarios para ejecutarla. ^{[ 5 ]}^{: 636–637}

Redes de inserción y de burbujas

Podemos construir fácilmente una red de cualquier tamaño de forma recursiva utilizando los principios de inserción y selección. Suponiendo que tenemos una red de ordenación de tamaño n , podemos construir una red de tamaño n + 1 "insertando" un número adicional en la subred ya ordenada (utilizando el principio subyacente al ordenamiento por inserción ). También podemos lograr lo mismo "seleccionando" primero el valor más bajo de las entradas y luego ordenando los valores restantes de forma recursiva (utilizando el principio subyacente al ordenamiento de burbuja ).

Una red de clasificación construida recursivamente que primero coloca el valor más grande en la parte inferior y luego clasifica los cables restantes. Basada en el algoritmo de ordenación de burbuja.

La estructura de estas dos redes de clasificación es muy similar. Una construcción de las dos variantes diferentes, que agrupa comparadores que pueden realizarse simultáneamente, muestra que, de hecho, son idénticas. ^{[ 1 ]}

La red de inserción (o equivalentemente, red de burbujas) tiene una profundidad de $2 n - 3$ , ^{[ 1 ]} donde $n$ es el número de valores. Esto es mejor que el tiempo $O (n log n)$ necesario para las máquinas de acceso aleatorio , pero resulta que hay redes de ordenación mucho más eficientes con una profundidad de solo $O (log 2 n)$ , como se describe a continuación .

principio cero-uno

Si bien es fácil demostrar la validez de algunas redes de clasificación (como el clasificador de inserción/burbuja), no siempre es tan sencillo. Hay $n!$ permutaciones de números en una red $de$ $n$ cables, y probarlas todas llevaría mucho tiempo, especialmente cuando $n$ es grande. El número de casos de prueba se puede reducir significativamente a $2n$ , utilizando el llamado principio cero-uno. Aunque sigue siendo exponencial, este valor es menor que $n!$ para todo $n \geq 4$ , y la diferencia aumenta rápidamente a medida que $n$ se incrementa .

El principio de cero-uno establece que, si una red de ordenación puede ordenar correctamente todas $las$ $2ⁿ$ secuencias de ceros y unos, entonces también es válida para entradas ordenadas arbitrariamente. Esto no solo reduce drásticamente la cantidad de pruebas necesarias para verificar la validez de una red, sino que también resulta muy útil para crear diversas construcciones de redes de ordenación.

El principio se puede demostrar observando primero el siguiente hecho sobre los comparadores: cuando se aplica una función monótonamente creciente $f$ a las entradas, es decir, $x$ $e y$ se reemplazan por $f (x)$ y $f (y)$ , entonces el comparador produce $min(f (x), f (y)) = f (min(x, y))$ y $max(f (x), f (y)) = f (max(x, y))$ . Por inducción sobre la profundidad de la red, este resultado se puede extender a un lema que establece que si la red transforma la secuencia $a 1, ..., a n$ en $b 1, ..., b n$ , transformará $f (a 1), ..., f (a n)$ en $f (b 1), ..., f (b n)$ . Supongamos que alguna entrada $a 1, ..., a n$ contiene dos elementos $a i < a j$ , y la red intercambia incorrectamente estos en la salida. Entonces también ordenará incorrectamente $f (a 1), ..., f (a n)$ para la función

f(x)={\begin{cases}1\ &{\mbox{si }}x>a_{i}\\0\ &{\mbox{en otro caso.}}\end{cases}}

Esta función es monótona, por lo que tenemos el principio cero-uno como contrapositiva . ^{[ 5 ]}^{: 640–641}

Construcción de redes de clasificación

Existen diversos algoritmos para construir redes de ordenación de profundidad $O (log 2 n)$ (y por lo tanto de tamaño $O (n log 2 n)$ ), como el algoritmo de ordenación por fusión impar-par de Batcher , la ordenación bitónica , la ordenación Shell y la red de ordenación por pares . Estas redes se utilizan con frecuencia en la práctica.

También es posible construir redes de profundidad $O (log n)$ (y por lo tanto de tamaño $O (n log n)$ ) utilizando una construcción llamada red AKS , en honor a sus descubridores Ajtai , Komlós y Szemerédi . ^{[ 6 ]} Si bien es un descubrimiento teórico importante, la red AKS tiene una aplicación práctica muy limitada debido a la gran constante lineal oculta por la notación Big-O . ^{[ 5 ]}^{: 653} Esto se debe en parte a una construcción de un grafo expansor .

En 1990, Paterson describió una versión simplificada de la red AKS y señaló que "las constantes obtenidas para el límite de profundidad aún impiden que la construcción tenga un valor práctico". ^{[ 7 ]}

Una construcción más reciente llamada red de clasificación en zigzag de tamaño $O (n log n)$ fue descubierta por Goodrich en 2014. ^{[ 8 ]} Si bien su tamaño es mucho menor que el de las redes AKS, su profundidad $O (n log n)$ la hace inadecuada para una implementación paralela.

Redes de clasificación óptima

Para un número pequeño y fijo de entradas $n$ , se pueden construir redes de ordenación óptimas , ya sea con profundidad mínima (para una ejecución máximamente paralela) o con tamaño mínimo (número de comparadores). Estas redes se pueden usar para aumentar el rendimiento de redes de ordenación más grandes resultantes de las construcciones recursivas de, por ejemplo, Batcher, deteniendo la recursión prematuramente e insertando redes óptimas como casos base. ^{[ 9 ]} La siguiente tabla resume los resultados de optimalidad para redes pequeñas para las que se conoce la profundidad óptima:

Para redes de mayor tamaño, actualmente se desconocen tanto la profundidad óptima como el tamaño óptimo. Los límites conocidos hasta el momento se muestran en la tabla siguiente:

Las primeras dieciséis redes óptimas en profundidad se enumeran en El arte de la programación informática de Knuth , ^{[ 1 ]} y lo han estado desde la edición de 1973; sin embargo, mientras que la optimalidad de las primeras ocho fue establecida por Floyd y Knuth en la década de 1960, esta propiedad no se demostró para las últimas seis hasta 2014 ^{[ 16 ]} (los casos nueve y diez se decidieron en 1991 ^{[ 9 ]} ).

Para entre una y doce entradas, se conocen redes de ordenación mínimas (es decir, de tamaño óptimo), y para valores superiores, se pueden derivar inductivamente límites inferiores en sus tamaños $S (n) utilizando un lema debido a Van Voorhis$ ^{[ 1 ]} (p. 240): $S (n) \geq S (n - 1) + ⌈log 2 n ⌉$ . Las primeras diez redes óptimas se conocen desde 1969, y las primeras ocho se conocen nuevamente como óptimas desde el trabajo de Floyd y Knuth, pero la optimalidad de los casos $n = 9$ y $n = 10$ tardó hasta 2014 en resolverse. ^{[ 11 ]} La optimalidad de las redes de ordenación más pequeñas conocidas para $n = 11$ y $n = 12$ se resolvió en 2020. ^{[ 17 ]}^{[ 1 ]}

Se ha realizado algún trabajo en el diseño de redes de clasificación óptimas utilizando algoritmos genéticos : D. Knuth menciona que la red de clasificación más pequeña conocida para $n = 13$ fue encontrada por Hugues Juillé en 1995 "simulando un proceso evolutivo de reproducción genética" ^{[ 1 ]} (p. 226), y que las redes de clasificación de profundidad mínima para $n = 9$ y $n = 11$ fueron encontradas por Loren Schwiebert en 2001 "utilizando métodos genéticos" ^{[ 1 ]} (p. 229).

Complejidad de las pruebas de redes de clasificación

A menos que P=NP , es probable que el problema de probar si una red candidata es una red de clasificación siga siendo difícil para redes de gran tamaño, debido a que el problema es co-NP -completo. ^{[ 18 ]}

Referencias

1 2 3 4 5 6 7 8 9 Knuth, DE (1997). El arte de la programación informática, volumen 3: ordenación y búsqueda (segunda edición). Addison–Wesley. págs. 219–247 . ISBN 978-0-201-89685-5.Sección 5.3.4: Redes para la clasificación.
↑ US 3029413 , O'Connor, Daniel G. y Nelson, Raymond J., "Sistema de clasificación con interruptor de clasificación $de n$ líneas", publicado el 10 de abril de 1962
↑ Batcher, KE (1968). Redes de clasificación y sus aplicaciones . Actas de la Conferencia Conjunta de Computación de Primavera de AFIPS. págs. 307–314 .
↑ Owens, JD; Houston, M.; Luebke, D.; Green, S.; Stone, JE; Phillips, JC (2008). "Computación con GPU". Actas del IEEE . 96 (5): 879– 899. doi : 10.1109/JPROC.2008.917757 . S2CID 17091128 .
1 2 3 4 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
↑ Ajtai, M. ; Komlós, J. ; Szemerédi, E. (1983). Una red de clasificación $O(n log n)$ . STOC '83. Actas del decimoquinto simposio anual de la ACM sobre Teoría de la Computación . págs. 1–9 . doi : 10.1145/800061.808726 . ISBN 0-89791-099-0.
↑ Paterson, MS (1990). "Redes de clasificación mejoradas con profundidad $O$ $(log$ $N$ $) ".$ Algorithmica . 5 ( 1– 4): 75– 92. doi : 10.1007/BF01840378 . S2CID 2064561 .
↑ Goodrich, Michael (marzo de 2014). «Clasificación en zigzag». Actas del cuadragésimo sexto simposio anual de la ACM sobre teoría de la computación . págs. 684–693 . arXiv : 1403.2777 . doi : 10.1145/2591796.2591830 . ISBN 9781450327107. S2CID 947950 .
1 2 Parberry, Ian (1991). "Un límite inferior de profundidad óptimo asistido por computadora para redes de clasificación de nueve entradas" (PDF) . Teoría de sistemas matemáticos . 24 : 101–116 . CiteSeerX 10.1.1.712.219 . doi : 10.1007/bf02090393 . S2CID 7077160 .
1 2 3 Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Sorting Networks: to the End and Back Again . arXiv : 1507.01428 . Bibcode : 2015arXiv150701428C .
1 2 Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten) . Proc. Int'l Conf. Tools with AI (ICTAI). pp. 186– 193. arXiv : 1405.5754 . Bibcode : 2014arXiv1405.5754C .
1 2 Obtenido por el lema de Van Voorhis y el valor $S (11) = 35$
↑ Ehlers, Thorsten (febrero de 2017). "La fusión de secuencias casi ordenadas produce un clasificador de 24". Information Processing Letters . 118 : 17–20 . doi : 10.1016/j.ipl.2016.08.005 .
^ Dobbelaere , Bert. "ClasificadorHunter" . GitHub . Consultado el 2 de enero de 2022 .
↑ Wang, Chengu (2025). "Redes de clasificación de profundidad 13 para 28 canales". arXiv : 2511.04107 [ cs.DS ].
↑ Bundala, D.; Závodný, J. (2014). «Redes de ordenación óptimas». Teoría y aplicaciones del lenguaje y los autómatas . Notas de clase en informática. Vol. 8370. pp. 236–247 . arXiv : 1310.6271 . doi : 10.1007/978-3-319-04921-2_19 . ISBN 978-3-319-04920-5. S2CID 16860013 .
↑ Harder, Jannis (2020). "Una respuesta al problema de ordenación de Bose-Nelson para 11 y 12 canales". arXiv : 2012.04400 [ cs.DS ].
↑ Parberry, Ian (1991). Sobre la complejidad computacional de la verificación de redes de ordenación óptima . Actas de PARLE '91: Arquitecturas y lenguajes paralelos Europa, Volumen I: Arquitecturas y algoritmos paralelos, Eindhoven, Países Bajos . págs. 252–269 .

Angel, O.; Holroyd, AE; Romik, D.; Virág, B. (2007). "Redes de clasificación aleatoria" . Advances in Mathematics . 215 (2): 839– 868. arXiv : math/0609538 . doi : 10.1016/j.aim.2007.05.019 .

Enlaces externos

Lista de las redes de ordenación más pequeñas para un número dado de entradas.
Redes de clasificación
CAPÍTULO 28: CLASIFICACIÓN DE REDES
Redes de clasificación
Herramienta para generar y graficar redes de clasificación
Redes de clasificación y el algoritmo END
Lipton, Richard J. ; Regan, Ken (24 de abril de 2014). "Redes de clasificación galácticas" . La carta perdida de Gödel y P=NP .
Validez de las redes de clasificación

[knuth-1] 1 2 3 4 5 6 7 8 9 Knuth, DE (1997). El arte de la programación informática, volumen 3: ordenación y búsqueda (segunda edición). Addison–Wesley. págs. 219–247 . ISBN 978-0-201-89685-5.Sección 5.3.4: Redes para la clasificación.

[2] US 3029413 , O'Connor, Daniel G. y Nelson, Raymond J., "Sistema de clasificación con interruptor de clasificación $de n$ líneas", publicado el 10 de abril de 1962

[3] Batcher, KE (1968). Redes de clasificación y sus aplicaciones . Actas de la Conferencia Conjunta de Computación de Primavera de AFIPS. págs. 307–314 .

[4] Owens, JD; Houston, M.; Luebke, D.; Green, S.; Stone, JE; Phillips, JC (2008). "Computación con GPU". Actas del IEEE . 96 (5): 879– 899. doi : 10.1109/JPROC.2008.917757 . S2CID 17091128 .

[clrs-5] 1 2 3 4 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.

[6] Ajtai, M. ; Komlós, J. ; Szemerédi, E. (1983). Una red de clasificación $O(n log n)$ . STOC '83. Actas del decimoquinto simposio anual de la ACM sobre Teoría de la Computación . págs. 1–9 . doi : 10.1145/800061.808726 . ISBN 0-89791-099-0.

[7] Paterson, MS (1990). "Redes de clasificación mejoradas con profundidad $O$ $(log$ $N$ $) ".$ Algorithmica . 5 ( 1– 4): 75– 92. doi : 10.1007/BF01840378 . S2CID 2064561 .

[8] Goodrich, Michael (marzo de 2014). «Clasificación en zigzag». Actas del cuadragésimo sexto simposio anual de la ACM sobre teoría de la computación . págs. 684–693 . arXiv : 1403.2777 . doi : 10.1145/2591796.2591830 . ISBN 9781450327107. S2CID 947950 .

[parberry91-9] 1 2 Parberry, Ian (1991). "Un límite inferior de profundidad óptimo asistido por computadora para redes de clasificación de nueve entradas" (PDF) . Teoría de sistemas matemáticos . 24 : 101–116 . CiteSeerX 10.1.1.712.219 . doi : 10.1007/bf02090393 . S2CID 7077160 .

[codish_end_game-10] 1 2 3 Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Sorting Networks: to the End and Back Again . arXiv : 1507.01428 . Bibcode : 2015arXiv150701428C .

[codish-11] 1 2 Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten) . Proc. Int'l Conf. Tools with AI (ICTAI). pp. 186– 193. arXiv : 1405.5754 . Bibcode : 2014arXiv1405.5754C .

[vvoorhis-12] 1 2 Obtenido por el lema de Van Voorhis y el valor $S (11) = 35$

[13] Ehlers, Thorsten (febrero de 2017). "La fusión de secuencias casi ordenadas produce un clasificador de 24". Information Processing Letters . 118 : 17–20 . doi : 10.1016/j.ipl.2016.08.005 .

[sorterhunter-14] Dobbelaere , Bert. "ClasificadorHunter" . GitHub . Consultado el 2 de enero de 2022 .

[15] Wang, Chengu (2025). "Redes de clasificación de profundidad 13 para 28 canales". arXiv : 2511.04107 [ cs.DS ].

[bundala_zavodny-16] Bundala, D.; Závodný, J. (2014). «Redes de ordenación óptimas». Teoría y aplicaciones del lenguaje y los autómatas . Notas de clase en informática. Vol. 8370. pp. 236–247 . arXiv : 1310.6271 . doi : 10.1007/978-3-319-04921-2_19 . ISBN 978-3-319-04920-5. S2CID 16860013 .

[harder-17] Harder, Jannis (2020). "Una respuesta al problema de ordenación de Bose-Nelson para 11 y 12 canales". arXiv : 2012.04400 [ cs.DS ].

[parberry-18] Parberry, Ian (1991). Sobre la complejidad computacional de la verificación de redes de ordenación óptima . Actas de PARLE '91: Arquitecturas y lenguajes paralelos Europa, Volumen I: Arquitecturas y algoritmos paralelos, Eindhoven, Países Bajos . págs. 252–269 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 16 ]

[ 11 ]

[ 17 ]

[ 18 ]