Red de ordenamiento
Esta puede ser imaginada como una red de hilos y módulos comparadores.
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.
[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.
Se supone que los hilos operan de izquierda a derecha, transportando valores (uno por hilo) que atraviesan la red al unísono.
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.
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.
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).
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.
secuencias de ceros y unos, entonces es también válida para entradas arbitrariamente ordenadas.
El principio puede ser demostrado primeramente observando los siguientes hechos acerca de los comparadores: cuando una función monótona
, entonces el comparador produce 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
La demostración ahora procede por contradicción: suponga que cierta entrada
, y la red incorrectamente intercambia estos valores a la salida.
) 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.
[8] Aunque su tamaño tiene un valor constante mucho menor que aquel en la red AKS, su profundidad es
, 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).
[9] La siguiente tabla sumariza los valores de optimalidad conocidos: 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
se pueden deducir inductivamente usando un lema gracias a Van Voorhis:
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
[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.
