Red de ordenamiento

En ciencias de la computación, una red de ordenamiento (en inglés: sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones. Esta puede ser imaginada como una red de hilos y módulos comparadores. Los valores (de cualquier tipo ordenable) fluyen a través de los hilos (no se debe confundir con hilo de ejecución). Cada comparador conecta dos hilos, compara los valores introducidos por los hilos, y los ordena obteniendo el menor como salida a un hilo, y el mayor a otro.

Las redes de ordenamiento se diferencian del más general ordenamiento por comparación en el hecho de que no son capaces de manejar cantidades arbitrariamente grandes de entrada, y que su secuencia de comparaciones se conoce de antemano, independientemente del resultado de las comparaciones previas. Esta independencia de la secuencia de comparaciones es útil para la ejecución paralela y para su implementación en hardware. A pesar de la simplicidad de las redes de ordenamiento, su teoría es sorprendentemente profunda y compleja. Las redes de ordenamiento fueron primero estudiadas circa 1954 por Armstrong, Nelson y O'Connor,^[1] quienes subsecuentemente patentaron la idea.^[2]

Las redes de ordenamiento pueden ser implementadas tanto en hardware como en software. Donald Knuth describe como los comparadores para los enteros binarios pueden ser implementados como sencillos dispositivos electrónicos de tres estados.^[1] Batcher, en 1968, sugirió usarlos para construir redes de interruptores para hardware de computadora, reemplazando a ambos: los buses de computadora y el más rápido pero más caro conmutador de barras cruzadas.^[3] Desde la década del 2000, las redes de ordenamiento (especialmente del ordenamiento bitónico) son usadas por la comunidad GPGPU para construir algoritmos de ordenamiento para correr en unidades de procesamiento gráfico.^[4]

Introducción

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

Una red de ordenamiento consiste en dos tipos de elementos: comparadores e hilos. Se supone que los hilos operan de izquierda a derecha, transportando valores (uno por hilo) que atraviesan la red al unísono. Cada comparador conecta dos hilos. Cuando un par de valores, que viaja a través de un par de hilos, encuentra un comparador, el comparador intercambia los valores si y sólo si el valor del hilo superior (i.e. el valor que viaja por el hilo superior) es mayor que el valor del hilo inferior.

Visto en fórmula, si el hilo superior trasporta $x$ y el hilo inferior transporta $y$ , entonces tras pasar por un comparador los hilos portan $x'=\min(x,y)$ y $y'=\max(x,y)$ , de forma que el par de valores está ordenado.^[5]^: 635 Una red de hilos y comparadores que es capaz de ordenar correctamente todas las posibles entradas en orden ascendente es llamada una red de ordenamiento.

La operación completa de una red de ordenamiento sencilla puede ser vista más abajo. Es fácil comprobar por qué esta red de ordenamiento puede correctamente ordenar las entradas; note que los primeros cuatro comparadores "hundirán" los valores mayores al fondo y "harán flotar" los valores menores hacia la parte superior. El comparador final sencillamente ordena los dos hilos intermedios.

Profundidad y eficiencia

La eficiencia de una red de ordenamiento puede ser medida por su tamaño total, el número de comparadores usados, o por su profundidad, definida (informalmente) como el mayor número de comparadores que cualquier valor de entrada puede encontrar en su paso a través de la red. Notando que las redes de ordenamiento pueden realizar ciertas comparaciones en paralelo (representado en la notación gráfica como comparadores que yacen en la misma línea vertical), y asumiendo que todas las comparaciones toman una unidad de tiempo, la profundidad de la red puede ser vista igual al número de unidades de tiempo requeridas para ejecutarla.^[5]^{: 636–637}

Redes de inserción y selección

Podemos fácilmente construir una red de cualquier tamaño recursivamente usando el principio de inserción y selección. Asumiendo que tenemos una red de ordenamiento de tamaño $n$ , podemos construir una red de tamaño $n+1$ insertando un número adicional en la subred ya ordenada (usando el principio detrás de insertion sort). Podemos también conseguir el mismo resultado primeramente "seleccionando" el menor valor de las entradas y posteriormente ordenando los valores restantes recursivamente (mediante el uso del principio detrás del ordenamiento de burbuja).

Una red de ordenamiento construida recursivamente que primeramente "hunde" el mayor valor hacia el fondo y posteriormente ordena los hilos restantes. Basado en el ordenamiento de burbuja.

Una red de ordenamiento construida recursivamente que primeramente ordena los primeros n hilos, y posteriormente inserta el valor restante. Basado en ordenamiento por inserción.

Las estructuras de estas dos redes de ordenamiento son muy similares. Una construcción de las dos variantes diferentes, que comprime conjuntamente comparadores que pueden correr simultáneamente indica que, de hecho, son idénticas.^[1]

Cuando se permiten comparadores en paralelo, las redes de ordenación de burbuja y por inserción son idénticas

La red de inserción tiene una profundidad de $2n-3$ ,^[1] haciéndola poco práctica. Mejores construcciones son discutidas más abajo.

Principio cero-uno

Aunque es fácil demostrar la corrección de algunas redes de ordenamiento (como las correspondientes a los ordenamientos insertion y bubble sort), no siempre es tan fácil. Existen $n!$ permutaciones de números en una red de $n$ hilos, y probarlos todos tomaría una cantidad significativa de tiempo, especialmente cuando el valor de $n$ es grande. El número de casos de prueba puede ser reducido significativamente, hasta $2^{n}$ , usando el llamado principio cero-uno. Incluso manteniéndose exponencial, esto es menor que $n!$ para todo $n\geq 4$ , y la diferencia crece rápidamente cuando $n$ se incrementa.

El principio cero-uno afirma que, si una red de ordenamiento puede correctamente ordenar todos las $2^{n}$ secuencias de ceros y unos, entonces es también válida para entradas arbitrariamente ordenadas. Esto no sólo drásticamente reduce el número de casos de pruebas necesarios para acertar la corrección de una red, sino que también es de gran utilidad al crear muchas construcciones de redes de ordenamiento.

El principio puede ser demostrado primeramente observando los siguientes hechos acerca de los comparadores: cuando una función monótona $f$ es aplicada a las entradas, i.e., $x$ y $y$ son reemplazados 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 en la profundidad de la red, este resultado puede extenderse a un lema enunciando que si la red transforma la secuencia $a_{1},\ldots ,a_{n}$ en $b_{1},\ldots ,b_{n}$ , entonces va a transformar $f(a_{1}),\ldots ,f(a_{n})$ en $f(b_{1}),\ldots ,f(b_{n})$ . La demostración ahora procede por contradicción: suponga que cierta entrada $a_{1},\ldots ,a_{n}$ contiene dos elementos $a_{i}<a_{j}$ , y la red incorrectamente intercambia estos valores a la salida. Entonces también incorrectamente ordenará $f(a_{1}),\ldots ,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, así que tenemos el principio cero-uno como la contraposición.^[5]^{: 640–641}

Construcción de las redes de ordenamiento

Varios algoritmos existen para construir sencillas pero eficientes redes de ordenamiento de profundidad $O(\log ^{2}n)$ (de ello el tamaño $O(n\log ^{2}n)$ ) tal como Batcher odd–even mergesort, ordenamiento bitónico, Shell sort, y la Pairwise sorting network. Estas redes son a menudo usadas en la práctica. También es posible, en teoría, construir redes de tamaño logarítmico para tamaños arbitrarios, usando una construcción llamada red AKS (o AKS network), nombrado tras las iniciales de sus descubridores Ajtai, Komlós, y Szemerédi.^[6] Aunque un descubrimiento teórico importante, la red AKS tiene poca o ninguna aplicación práctica dada la constante lineal escondida por la notación notación O grande, que está por los "muchos, muchos millares".^[5]^: 653 Esto se debe en parte a la construcción de grafo expansor. Una versión simplificada de la red AKS fue descrita por Paterson, quien nota que "las constantes obtenidas para la cota de profundidad todavía previene que la construcción sea de valor práctico".^[7] Otra construcción de redes de ordenamiento de tamaño $O(n\log n)$ fue descubierta por Goodrich.^[8] Aunque su tamaño tiene un valor constante mucho menor que aquel en la red AKS, su profundidad es $O(n\log n)$ , lo cual las hace ineficientes para implementaciones paralelas.

Redes de ordenamiento óptimas

Para un tamaño pequeño, fijo de entradas $n$ , una red de ordenamiento óptima puede ser construida, ya sea con profundidad minimal (para ejecución paralela maximal) o longitud minimal (número de comparadores). Estas redes pueden ser usadas para incrementar la eficienciaa de redes de ordenamiento mayores resultantes de construcciones recursivas de, e.g., Batcher, por medio de la parada de la ejecución tempranamente y la inserción de casos bases óptimos.^[9] La siguiente tabla sumariza los valores de optimalidad conocidos:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Profundidad^[10]	0	1	3	3	5	5	6	6	7	7	8	8	9	9	9	9
Longitud, cota superior ^[11]	0	1	3	5	9	12	16	19	25	29	35	39	45	51	56	60
Longitud, cota inferior (en caso de diferencia)^[11]											33	37	41	45	49	53

Las primeras dieciséis redes de profundidad óptima son listadas en The Art of Computer Programming de Knuth,^[1] y han estado desde la edición de 1973; no obstante, aunque la optimalidad de las primeras ocho fue establecida por Floyd y Knuth en los sesenta del siglo pasado, esta propiedad no fue demostrada para los seis últimos hasta el 2014 ^[10] (los casos nueve y diez habiendo estado decididos en 1991 ^[9]).

Desde uno hasta diez entradas, redes de longitud óptima son conocidas, y para valores más altos, cotas inferiores para sus longitudes $S(n)$ se pueden deducir inductivamente usando un lema gracias a Van Voorhis: $S(n+1)\geq S(n)+\lceil \log _{2}(n)\rceil$ . Todas, las diez redes óptimas, son conocidas desde 1969, con las primeras ocho nuevamente siendo conocidas como óptimas desde el trabajo de Floyd y Knuth, pero la optimalidad de los casos $n=9$ y $n=10$ tomó hasta 2014 para ser resuelta.^[11]

Algunos trabajos acerca del diseño de redes de ordenación óptimas han sido hechos usando algoritmos genéticos.^[12]

Complejidad de la comprobación de las redes de ordenamiento

Es poco probable que mejoras significativas subsecuentes para la comprobación de redes de ordenamiento puedan ser realizadas, a menos que P=NP, dado que el problema de comprobar cuando una red candidata es una red de ordenamiento es conocido que es NP-completo.^[13]

Referencias

↑ ^a ^b ^c ^d ^e Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Third Edition edición). Addison–Wesley. pp. 219-247. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting.
↑ O'Connor, Daniel G. & Nelson, "Sorting system with $n$ -line sorting switch", {{{country-code}}} {{{patent-number}}}.
↑ Batcher,, K. E. (1968). Sorting networks and their applications. Proc. AFIPS Spring Joint Computer Conference. pp. 307-314.
↑ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). «GPU Computing». Proceedings of the IEEE 96 (5): 879. doi:10.1109/JPROC.2008.917757.
↑ ^a ^b ^c ^d Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). Introduction to Algorithms (primera edición). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
↑ Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). «An $O (n log n)$ sorting network». Proc. 15th Annual ACM Symp. on the Theory of Computing (STOC). pp. 1-9. ISBN 0897910990. doi:10.1145/800061.808726.
↑ Paterson, M. S. (1990). «Improved sorting networks with $O (log N)$ depth». Algorithmica 5: 75-92. doi:10.1007/BF01840378.
↑ Goodrich, Michael (March 2014). «Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time». arXiv:1403.2777 [cs.DS].
↑ ^a ^b Parberry, Ian (1991). «A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks». Mathematical Systems Theory 24: 101-116. Archivado desde el original el 3 de marzo de 2016. Consultado el 28 de diciembre de 2014.
↑ ^a ^b Bundala, D.; Závodný, J. (2014). «Optimal Sorting Networks». Language and Automata Theory and Applications. Lecture Notes in Computer cience 8370: 236. ISBN 978-3-319-04920-5. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19.
↑ ^a ^b ^c 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)». arXiv:1405.5754 [cs.DM].
↑ Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press. pp. 21-27. ISBN 0-262-63185-7.
↑ Parberry, Ian (1991). «On the Computational Complexity of Optimal Sorting Network Verification». Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, The Netherlands: 252-269.

O. Angel, A.E. Holroyd, D. Romik, B. Virag, Random Sorting Networks, Adv. in Math., 215(2):839–868, 2007.

Enlaces externos

Sorting Networks
Sorting Networks
List of Sorting Networks
Sorting networks and the END algorithm
Lipton, Richard J.; Regan, Ken (24 de abril de 2014). «Galactic Sorting Networks». Gödel’s Lost Letter and P=NP.

http://optimizacion.cic.ipn.mx/sortingnetworks/

Datos: Q646477

[knuth-1] Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Third Edition edición). Addison–Wesley. pp. 219-247. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting.

[2] O'Connor, Daniel G. & Nelson, "Sorting system with $n$ -line sorting switch", {{{country-code}}} {{{patent-number}}}.

[3] Batcher,, K. E. (1968). Sorting networks and their applications. Proc. AFIPS Spring Joint Computer Conference. pp. 307-314.

[4] Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). «GPU Computing». Proceedings of the IEEE 96 (5): 879. doi:10.1109/JPROC.2008.917757.

[clrs-5] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). Introduction to Algorithms (primera edición). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[6] Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). «An $O (n log n)$ sorting network». Proc. 15th Annual ACM Symp. on the Theory of Computing (STOC). pp. 1-9. ISBN 0897910990. doi:10.1145/800061.808726.

[7] Paterson, M. S. (1990). «Improved sorting networks with $O (log N)$ depth». Algorithmica 5: 75-92. doi:10.1007/BF01840378.

[8] Goodrich, Michael (March 2014). «Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time». arXiv:1403.2777 [cs.DS].

[parberry91-9] Parberry, Ian (1991). «A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks». Mathematical Systems Theory 24: 101-116. Archivado desde el original el 3 de marzo de 2016. Consultado el 28 de diciembre de 2014.

[bundala_zavodny-10] Bundala, D.; Závodný, J. (2014). «Optimal Sorting Networks». Language and Automata Theory and Applications. Lecture Notes in Computer cience 8370: 236. ISBN 978-3-319-04920-5. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19.

[codish-11] 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)». arXiv:1405.5754 [cs.DM].

[12] Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press. pp. 21-27. ISBN 0-262-63185-7.

[parberry-13] Parberry, Ian (1991). «On the Computational Complexity of Optimal Sorting Network Verification». Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, The Netherlands: 252-269.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]