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 ${\displaystyle x}$ y el hilo inferior transporta ${\displaystyle y}$, entonces tras pasar por un comparador los hilos portan ${\displaystyle x'=\min(x,y)}$ y ${\displaystyle 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.

Summarize Timeline Top Qs Fact Check

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}

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).

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]

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}