Ver el código de «Red de ordenamiento»

[[Archivo:SimpleSortingNetwork2.svg|miniaturadeimagen|250px|Una red de ordenamiento simple consistente en cuatro hilos y cinco conectores]]

En [[ciencias de la computación]], una '''red de ordenamiento''' ({{lang-en|sorting network}}) es un [[algoritmo de ordenamiento|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 (informática)|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,<ref name="knuth"/> quienes subsecuentemente patentaron la idea.<ref>{{citar patente |country=US |number=3029413 |title=Sorting system with {{mvar|n}}-line sorting switch |pubdate=10 April 1962 |fdate= 21 February 1957 |inventor1-first=Daniel G. |inventor1-last=O'Connor |inventor2-last=Raymond J. |inventor2-last=Nelson}}</ref>

Las redes de ordenamiento pueden ser implementadas tanto en [[hardware]] como en [[software]]. [[Knuth|Donald Knuth]] describe como los comparadores para los enteros binarios pueden ser implementados como sencillos dispositivos electrónicos de tres estados.<ref name="knuth"/> [[Ken Batcher|Batcher]], en 1968, sugirió usarlos para construir redes de [[interruptor]]es para hardware de computadora, reemplazando a ambos: los [[Bus (informática)|buses de computadora]] y el más rápido pero más caro [[conmutador de barras cruzadas]].<ref>{{cite conference |first=K. E. |last=Batcher, |url=http://www.cs.kent.edu/~batcher/sort.ps |title=Sorting networks and their applications |conference=Proc. AFIPS Spring Joint Computer Conference |pages=307–314 |year=1968}}</ref> 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 [[GPU|unidades de procesamiento gráfico]].<ref>{{cita publicación | doi = 10.1109/JPROC.2008.917757 | título = GPU Computing | publicación = Proceedings of the IEEE | volumen = 96 | número = 5 | páginas = 879 | año = 2008 | last1 = Owens | first1 = J. D. | last2 = Houston | first2 = M. | last3 = Luebke | first3 = D. | last4 = Green | first4 = S. | last5 = Stone | first5 = J. E. | last6 = Phillips | first6 = J. C. }}</ref>

==Introducción==
[[Archivo:Sorting-network-comparator-demonstration.svg|miniaturadeimagen|150px|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 ([[Id est|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 <math>x</math> y el hilo inferior transporta <math>y</math>, entonces tras pasar por un comparador los hilos portan <math>x' = \min(x, y)</math> y <math>y' = \max(x, y)</math>, de forma que el par de valores está ordenado.<ref name="clrs">{{cita libro 
| apellido = Cormen 
| nombre = Thomas H. 
| enlaceautor=Thomas H. Cormen 
| autor2 = [[Charles E. Leiserson|Leiserson, Charles E.]], [[Ron Rivest|Rivest, Ronald L.]]
| título = Introduction to Algorithms
| año = 1990
| edición = primera
| editorial = [[MIT Press]] and McGraw-Hill 
| isbn = 0-262-03141-8
}}</ref>{{rp|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.

[[Archivo:SimpleSortingNetworkFullOperation.svg|650px]]

==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 [[Computación paralela|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.<ref name="clrs"/>{{rp|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 <math>n</math>, podemos construir una red de tamaño <math>n + 1</math> '''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 [[recursividad|recursivamente]] (mediante el uso del principio detrás del [[ordenamiento de burbuja]]).

{|
|style="vertical-align: top;"| [[Archivo:Recursive-bubble-sorting-network.svg|200px|miniaturadeimagen|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]].]]
|style="vertical-align: top;"| [[Archivo:Recursive-insertion-sorting-network.svg|200px|miniaturadeimagen|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.<ref name="knuth"/>
{|
|style="vertical-align: top;"| [[Archivo:Six-wire-bubble-sorting-network.svg|200px|miniaturadeimagen|Red para el ordenamiento de burbuja.]]
|style="vertical-align: top;"| [[Archivo:Six-wire-insertion-sorting-network.svg|200px|miniaturadeimagen|Red para el ordenamiento por inserción.]]
|style="vertical-align: top;"| [[Archivo:Six-wire-pyramid-sorting-network.svg|200px|miniaturadeimagen|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 <math>2n - 3</math>,<ref name="knuth"/> haciéndola poco práctica. Mejores construcciones son discutidas [[#Construyendo redes de ordenamiento|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 <math>n!</math> permutaciones de números en una red de <math>n</math> hilos, y probarlos todos tomaría una cantidad significativa de tiempo, especialmente cuando el valor de <math>n</math> es grande. El número de casos de prueba puede ser reducido significativamente, hasta <math>2^n</math>, usando el llamado principio cero-uno. Incluso manteniéndose exponencial, esto es menor que <math>n!</math> para todo <math>n \geq 4</math>, y la diferencia crece rápidamente cuando <math>n</math> se incrementa.

El principio cero-uno afirma que, si una red de ordenamiento puede correctamente ordenar todos las <math>2^n</math> 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]] <math>f</math> es aplicada a las entradas, [[Id est|i.e.]], <math>x</math> y <math>y</math> son reemplazados por <math>f(x)</math> y <math>f(y)</math>, entonces el comparador produce 
:<math>\min(f(x), f(y)) = f(\min(x, y))</math>
y
:<math>\max(f(x), f(y)) = f(\max(x, y))</math>.
Por [[inducción matemática|inducción]] en la profundidad de la red, este resultado puede extenderse a un [[Lema (matemáticas)|lema]] enunciando que si la red transforma la secuencia <math>a_1, \ldots, a_n</math> en <math>b_1, \ldots, b_n</math>, entonces va a transformar <math>f(a_1), \ldots, f(a_n)</math> en <math>f(b_1), \ldots, f(b_n)</math>. La demostración ahora procede [[demostración por contradicción|por contradicción]]: suponga que cierta entrada <math>a_1, \ldots, a_n</math> contiene dos elementos <math>a_i < a_j</math>, y la red incorrectamente intercambia estos valores a la salida. Entonces también incorrectamente ordenará <math>f(a_1), \ldots, f(a_n)</math> para la función

:<math>
f(x) = \begin{cases}
        1\ &\mbox{si } x > a_i \\
        0\ &\mbox{en otro caso.}
       \end{cases}
</math>

Esta función es monótona, así que tenemos el principio cero-uno como la [[contraposición]].<ref name="clrs"/>{{rp|640–641}}

==Construcción de las redes de ordenamiento==
Varios algoritmos existen para construir sencillas pero eficientes redes de ordenamiento de profundidad <math>O(\log^2n)</math> (de ello el tamaño <math>O(n\log^2n)</math>) 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 [[Miklós Ajtai|Ajtai]], [[János Komlós|Komlós]], y [[Endre Szemerédi|Szemerédi]].<ref>{{Cite conference
 | doi = 10.1145/800061.808726 | chapter = An {{math|''O''(''n'' log ''n'')}} sorting network | title = Proc. 15th Annual ACM Symp. on the Theory of Computing (STOC) | pages = 1–9 | year = 1983 | last1 = Ajtai | first1 = M.| author1-link=Miklós Ajtai | last2 = Komlós | first2 = J. |author2-link=János Komlós (mathematician) | last3 = Szemerédi | first3 = E. |author3-link=Endre Szemerédi| isbn = 0897910990}}</ref> 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".<ref name="clrs"/>{{rp|653}} Esto se debe en parte a la construcción de [[grafo expansor]]. Una versión simplificada de la red AKS fue descrita por [[Michael S. Paterson|Paterson]], quien nota que "las constantes obtenidas para la cota de profundidad todavía previene que la construcción sea de valor práctico".<ref>{{cita publicación | doi = 10.1007/BF01840378 | título = Improved sorting networks with {{math|''O''(log ''N'')}} depth | journal = Algorithmica | volume = 5 | pages = 75–92 | year = 1990 | last1 = Paterson | first1 = M. S. }}</ref> Otra construcción de redes de ordenamiento de tamaño <math>O(n\log n)</math> fue descubierta por [[Michael T. Goodrich|Goodrich]].<ref>{{cite arXiv|last1=Goodrich|first1=Michael|authorlink1=Michael T. Goodrich|arxiv=1403.2777|class=cs.DS|title=Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time|date=March 2014}}</ref> Aunque su tamaño tiene un valor constante mucho menor que aquel en la red AKS, su profundidad es <math>O(n\log n)</math>, lo cual las hace ineficientes para implementaciones paralelas.

===Redes de ordenamiento óptimas===
Para un tamaño pequeño, fijo de entradas <math>n</math>, 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 [[Divide y vencerás|recursivas]] de, e.g., Batcher, por medio de la parada de la ejecución tempranamente y la inserción de casos bases óptimos.<ref name="parberry91">{{cita publicación |nombre=Ian |apellido=Parberry |título=A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks |publicación=Mathematical Systems Theory |volumen=24 |páginas=101–116 |año=1991 |url=http://larc.unt.edu/ian/pubs/9-input.pdf |fechaacceso=28 de diciembre de 2014 |urlarchivo=https://web.archive.org/web/20160303172143/http://larc.unt.edu/ian/pubs/9-input.pdf |fechaarchivo=3 de marzo de 2016 }}</ref> La siguiente tabla sumariza los valores de optimalidad conocidos:

{| class="wikitable" style="text-align: center;"
|-
! style="text-align: left;" | <math>n</math>
| style="width: 20px;" | 1 || style="width: 20px;" | 2 || style="width: 20px;" | 3 || style="width: 20px;" | 4 || style="width: 20px;" | 5 || style="width: 20px;" | 6 || style="width: 20px;" | 7 || style="width: 20px;" | 8 || style="width: 20px;" | 9 || style="width: 20px;" | 10 || style="width: 20px;" | 11 || style="width: 20px;" | 12 || style="width: 20px;" | 13 || style="width: 20px;" | 14 || style="width: 20px;" | 15 || style="width: 20px;" | 16
|- 
! style="text-align: left;" | Profundidad<ref name="bundala_zavodny"/>
| 0 || 1 || 3 || 3 || 5 || 5 || 6 || 6 || 7 || 7 || 8 || 8 || 9 || 9 || 9 || 9
|- 
! style="text-align: left;" | Longitud, [[cota superior asintótica|cota superior]]<ref name="codish"/>
| 0 || 1 || 3 || 5 || 9 || 12 || 16 || 19 || 25 || 29 || 35 || 39 || 45 || 51 || 56 || 60
|- 
! style="text-align: left;" | Longitud, [[cota inferior asintótica|cota inferior]] (en caso de diferencia)<ref name="codish"/>
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 33 || 37 || 41 || 45 || 49 || 53
|}

Las primeras dieciséis redes de profundidad óptima son listadas en ''[[The Art of Computer Programming]]'' de Knuth,<ref name="knuth">{{cite book |first=D. E. |last=Knuth |authorlink=Donald Knuth |title=[[The Art of Computer Programming]], Volume 3: Sorting and Searching |edition=Third Edition |publisher=Addison–Wesley |year=1997 |isbn=0-201-89685-0 |pages=219–247}} Section 5.3.4: Networks for Sorting.</ref> y han estado desde la edición de 1973; no obstante, aunque la optimalidad de las primeras ocho fue establecida por [[Robert Floyd|Floyd]] y Knuth en los sesenta del siglo pasado, esta propiedad no fue demostrada para los seis últimos hasta el 2014<ref name="bundala_zavodny">{{Cite journal| doi = 10.1007/978-3-319-04921-2_19| title = Optimal Sorting Networks| journal = Language and Automata Theory and Applications| volume = 8370| pages = 236| series = Lecture Notes in Computer cience| year = 2014| last1 = Bundala | first1 = D. | last2 = Závodný | first2 = J. | isbn = 978-3-319-04920-5| arxiv = 1310.6271}}</ref> (los casos nueve y diez habiendo estado decididos en 1991<ref name="parberry91"/>).

Desde uno hasta diez entradas, redes de longitud óptima son conocidas, y para valores más altos, cotas inferiores para sus longitudes <math>S(n)</math> se pueden deducir inductivamente usando un lema gracias a Van Voorhis: <math>S(n + 1) \geq S(n) + \lceil \log_2(n) \rceil</math>. 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 <math>n = 9</math> y <math>n = 10</math> tomó hasta 2014 para ser resuelta.<ref name="codish">{{cite arXiv |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Frank |first3=Michael |last4= Schneider-Kamp |first4=Peter |eprint=1405.5754 |title=Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten) |class=cs.DM |year=2014 }}</ref>

Algunos trabajos acerca del diseño de redes de ordenación óptimas han sido hechos usando [[algoritmo genético|algoritmos genéticos]].<ref>{{cite book |first=M. |last=Mitchell |title=An Introduction to Genetic Algorithms |url=https://archive.org/details/introductiontoge00mitc_876 |publisher=MIT Press |year=1998 |isbn=0-262-63185-7 |pages=[https://archive.org/details/introductiontoge00mitc_876/page/n24 21]–27}}</ref>

===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 [[Clases de complejidad P y NP|P=NP]], dado que el problema de comprobar cuando una red candidata es una red de ordenamiento es conocido que es [[NP-completo]].<ref name=parberry>{{cite conference |last=Parberry|first=Ian|title=On the Computational Complexity of Optimal Sorting Network Verification|journal=Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, The Netherlands |year=1991|pages=252–269}}</ref>

==Referencias==
{{Listaref|30em}}
* O. Angel, A.E. Holroyd, D. Romik, B. Virag, ''[http://arxiv.org/abs/math/0609538 Random Sorting Networks]'', Adv. in Math., 215(2):839–868, 2007.

==Enlaces externos==
*[http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm Sorting Networks] {{Wayback|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm |date=20110927024354 }}
*[https://web.archive.org/web/20080116050552/http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html Sorting Networks]
*[http://pages.ripco.net/~jgamble/nw.html List of Sorting Networks]
*[http://www.cs.brandeis.edu/~hugues/sorting_networks.html Sorting networks and the END algorithm]
* {{cite web |url=http://rjlipton.wordpress.com/2014/04/24/galactic-sortning-networks/ |first1=Richard J. |last1=Lipton |authorlink1=Richard J. Lipton |first2=Ken |last2=Regan |date=24 de abril de 2014 |title=Galactic Sorting Networks |website=Gödel’s Lost Letter and P=NP}}
http://optimizacion.cic.ipn.mx/sortingnetworks/ {{Wayback|url=http://optimizacion.cic.ipn.mx/sortingnetworks/ |date=20170323053918 }}
{{Control de autoridades}}
[[Categoría:Algoritmos de ordenamiento]]
[[Categoría:Ingeniería de la computación]]