El algoritmo de ordenación por fusión bitónica es un algoritmo paralelo . También se utiliza como método de construcción para construir una red de ordenación . El algoritmo fue ideado por Ken Batcher . Las redes de ordenación resultantes consisten en comparadores y tienen un retraso de , donde es el número de elementos que se ordenarán. [1] Esto lo convierte en una opción popular para ordenar grandes cantidades de elementos en una arquitectura que contiene una gran cantidad de unidades de ejecución paralelas que se ejecutan al unísono , como una GPU típica .
Una secuencia ordenada es una secuencia monótona no decreciente (o no creciente). Una secuencia bitónica es una secuencia con para algún , o un desplazamiento circular de dicha secuencia.
Sea y .
Del algoritmo de construcción se desprende claramente que el número de rondas de comparaciones paralelas viene dado por .
De ello se deduce que el número de comparadores está acotado (lo que establece un valor exacto para cuando es una potencia de 2).
Aunque el número absoluto de comparaciones suele ser mayor que el ordenamiento par-impar de Batcher , muchas de las operaciones consecutivas en un ordenamiento bitónico conservan una localidad de referencia , lo que hace que las implementaciones sean más amigables con el caché y típicamente más eficientes en la práctica.
La siguiente es una red de clasificación bitónica con 16 entradas:
Los 16 números entran como entradas en el extremo izquierdo, se deslizan a lo largo de cada uno de los 16 cables horizontales y salen por las salidas en el extremo derecho. La red está diseñada para ordenar los elementos, con el número más grande en la parte inferior.
Las flechas son comparadores. Cuando dos números llegan a los dos extremos de una flecha, se comparan para garantizar que la flecha apunte hacia el número mayor. Si están fuera de orden, se intercambian. Los cuadros de colores son solo para ilustrar y no tienen ningún efecto en el algoritmo.
Cada caja roja tiene la misma estructura: cada entrada en la mitad superior se compara con la entrada correspondiente en la mitad inferior, con todas las flechas apuntando hacia abajo (rojo oscuro) o hacia arriba (rojo claro). Si las entradas forman una secuencia bitónica (una secuencia única no decreciente seguida de una única no creciente o viceversa), entonces la salida formará dos secuencias bitónicas. La mitad superior de la salida será bitónica y la mitad inferior será bitónica, con cada elemento de la mitad superior menor o igual que cada elemento de la mitad inferior (para el rojo oscuro) o viceversa (para el rojo claro). Este teorema no es obvio, pero se puede verificar considerando cuidadosamente todos los casos de cómo podrían compararse las diversas entradas, utilizando el principio cero-uno , donde una secuencia bitónica es una secuencia de 0 y 1 que no contiene más de dos subsecuencias "10" o "01".
Los cuadros rojos se combinan para formar cuadros azules y verdes. Cada uno de estos cuadros tiene la misma estructura: se aplica un cuadro rojo a toda la secuencia de entrada, luego a cada mitad del resultado, luego a cada mitad de cada uno de esos resultados, y así sucesivamente. Todas las flechas apuntan hacia abajo (azul) o hacia arriba (verde). Esta estructura se conoce como red mariposa . Si la entrada a este cuadro es bitónica, entonces la salida se ordenará completamente en orden creciente (azul) o en orden decreciente (verde). Si un número entra en el cuadro azul o verde, entonces el primer cuadro rojo lo ordenará en la mitad correcta de la lista. Luego pasará a través de un cuadro rojo más pequeño que lo ordenará en el cuarto correcto de la lista dentro de esa mitad. Esto continúa hasta que se ordena exactamente en la posición correcta. Por lo tanto, la salida del cuadro verde o azul estará completamente ordenada.
Los cuadros verdes y azules se combinan para formar la red de ordenación completa. Para cualquier secuencia arbitraria de entradas, las ordenará correctamente, con la más grande en la parte inferior. La salida de cada cuadro verde o azul será una secuencia ordenada, por lo que la salida de cada par de listas adyacentes será bitónica, porque la superior es azul y la inferior es verde. Cada columna de cuadros azules y verdes toma N secuencias ordenadas y las concatena en pares para formar N/2 secuencias bitónicas, que luego son ordenadas por los cuadros en esa columna para formar N/2 secuencias ordenadas. Este proceso comienza con cada entrada considerada como una lista ordenada de un elemento, y continúa a través de todas las columnas hasta que la última las fusiona en una sola lista ordenada. Debido a que la última etapa fue azul, esta lista final tendrá el elemento más grande en la parte inferior.
Cada caja verde, en el diagrama anterior, realiza la misma operación que una caja azul, pero con la ordenación en la dirección opuesta. Por lo tanto, cada caja verde podría ser reemplazada por una caja azul seguida de un cruce donde todos los cables se mueven a la posición opuesta. Esto permitiría que todas las flechas apunten en la misma dirección, pero evitaría que las líneas horizontales sean rectas. Sin embargo, un cruce similar podría colocarse a la derecha de la mitad inferior de las salidas de cualquier bloque rojo, y la ordenación seguiría funcionando correctamente, porque el reverso de una secuencia bitónica sigue siendo bitónica. Si una caja roja tiene un cruce antes y después de ella, se puede reorganizar internamente para que los dos cruces se cancelen, de modo que los cables vuelvan a ser rectos. Por lo tanto, el siguiente diagrama es equivalente al anterior, donde cada caja verde se ha convertido en una azul más un cruce, y cada caja naranja es una caja roja que absorbió dos de esos cruces:
Las puntas de flecha no están dibujadas, porque cada comparador ordena en la misma dirección. Los bloques azul y rojo realizan las mismas operaciones que antes. Los bloques naranjas son equivalentes a los bloques rojos donde el orden de secuencia se invierte para la mitad inferior de sus entradas y la mitad inferior de sus salidas. Esta es la representación más común de una red de ordenamiento bitónico. A diferencia de la interpretación anterior, debido a que los elementos permanecen ordenados lógicamente, es fácil extender esta representación a un caso que no sea de potencia de dos (donde cada comparación e intercambio ignora cualquier caso donde el índice más grande esté fuera de rango).
La siguiente es una implementación sin recursión de la ordenación por fusión bitónica cuando la longitud de la matriz es una potencia de dos: [2]
// dado un array arr de longitud n, este código lo ordena en su lugar // todos los índices van de 0 a n-1 for ( k = 2 ; k <= n ; k *= 2 ) // k se duplica en cada iteración for ( j = k / 2 ; j > 0 ; j /= 2 ) // j se reduce a la mitad en cada iteración, con truncamiento de partes fraccionarias for ( i = 0 ; i < n ; i ++ ) l = bitwiseXOR ( i , j ); // en lenguajes como C esto es "i ^ j" if ( l > i ) if ( ( bitwiseAND ( i , k ) == 0 ) AND ( arr [ i ] > arr [ l ]) OR ( bitwiseAND ( i , k ) != 0 ) AND ( arr [ i ] < arr [ l ]) ) intercambia los elementos arr [ i ] y arr [ l ]