Red de ordenamiento

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 ${\displaystyle n}$, podemos construir una red de tamaño ${\displaystyle 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]

Red para el ordenamiento de burbuja.

Red para el ordenamiento por inserción.

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 ${\displaystyle 2n-3}$,[1] haciéndola poco práctica. Mejores construcciones son discutidas más abajo.

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 ${\displaystyle n!}$ permutaciones de números en una red de ${\displaystyle n}$ hilos, y probarlos todos tomaría una cantidad significativa de tiempo, especialmente cuando el valor de ${\displaystyle n}$ es grande. El número de casos de prueba puede ser reducido significativamente, hasta ${\displaystyle 2^{n}}$, usando el llamado principio cero-uno. Incluso manteniéndose exponencial, esto es menor que ${\displaystyle n!}$ para todo ${\displaystyle n\geq 4}$, y la diferencia crece rápidamente cuando ${\displaystyle n}$ se incrementa.

El principio cero-uno afirma que, si una red de ordenamiento puede correctamente ordenar todos las ${\displaystyle 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 ${\displaystyle f}$ es aplicada a las entradas, i.e., ${\displaystyle x}$ y ${\displaystyle y}$ son reemplazados por ${\displaystyle f(x)}$ y ${\displaystyle f(y)}$, entonces el comparador produce

${\displaystyle \min(f(x),f(y))=f(\min(x,y))}$

y

${\displaystyle \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 ${\displaystyle a_{1},\ldots ,a_{n}}$ en ${\displaystyle b_{1},\ldots ,b_{n}}$, entonces va a transformar ${\displaystyle f(a_{1}),\ldots ,f(a_{n})}$ en ${\displaystyle f(b_{1}),\ldots ,f(b_{n})}$. La demostración ahora procede por contradicción: suponga que cierta entrada ${\displaystyle a_{1},\ldots ,a_{n}}$ contiene dos elementos ${\displaystyle a_{i}<a_{j}}$, y la red incorrectamente intercambia estos valores a la salida. Entonces también incorrectamente ordenará ${\displaystyle f(a_{1}),\ldots ,f(a_{n})}$ para la función

${\displaystyle 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}

Para un tamaño pequeño, fijo de entradas ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle S(n)}$ se pueden deducir inductivamente usando un lema gracias a Van Voorhis: ${\displaystyle 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 ${\displaystyle n=9}$ y ${\displaystyle 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]

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]