Diagrama interactivo de redes de ordenamiento con animacion paso a paso
Una red de ordenamiento es una red de comparadores de estructura fija que ordena cualquier secuencia de entrada usando una disposicion predeterminada de operaciones de comparacion e intercambio. A diferencia de algoritmos adaptativos como quicksort, una red de ordenamiento realiza exactamente las mismas comparaciones independientemente de los datos de entrada.
Cada comparador conecta dos cables (posiciones i y j) y dirige el valor menor al cable superior y el mayor al inferior. Si los valores ya estan ordenados, no cambia nada; si no, se intercambian.
La profundidad de una red de ordenamiento es el numero maximo de capas desde la entrada hasta la salida. Los comparadores en la misma profundidad no tienen dependencias de datos y pueden ejecutarse simultaneamente en paralelo.
Los algoritmos de ordenamiento tradicionales deciden la siguiente comparacion basandose en resultados previos. Las redes de ordenamiento predeterminan todas las comparaciones, haciendolas ideales para implementacion en hardware y computacion paralela en GPU.
Las redes de ordenamiento se usan ampliamente en: ordenamiento en GPU (bitonic sort es la base del ordenamiento CUDA), diseno de circuitos de ordenamiento en hardware, ordenamiento oblato en computacion segura, optimizacion de consultas de bases de datos y ordenamiento de paquetes de red.
Para N pequeno, los conteos optimos conocidos son: N=4 requiere 5 comparadores, N=5 necesita 9, N=6 necesita 12, N=7 necesita 16, N=8 necesita 19, N=9 necesita 25, N=10 necesita 29, N=16 necesita 60. El principio 0-1 demuestra que verificar todas las 2^N entradas binarias es suficiente para confirmar la correccion de la red.