Luis Azua

Luis Azua

Red de ordenación bitónica con ocho entradas.
Class	Algoritmo de ordenación
Data structure	Array
Worst-case performance	$O(\log(n)^{2})$ tiempo paralelo
Best-case performance	$O(\log(n)^{2})$ tiempo paralelo
Average performance	$O(\log(n)^{2})$ tiempo paralelo
Worst-case space complexity	$O(n\log(n)^{2})$ comparadores
Optimal	No

Ordenamiento bitónico es un algoritmo paralelo de ordenamiento. También se usa como método de construcción de una red de ordenamiento. El algoritmo fue diseñado por Ken Batcher. Las redes de ordenamiento resultantes consisten en $O(n\log(n)^{2})$ comparadores y tienen un costo temporal de $O(\log(n)^{2})$, donde $n$ es el número de elementos a ser ordenados.

Una secuencia ordenada es una secuencia monótonamente no-decreciente (o no-creciente). Una secuencia bitónica es una secuencia con $x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}$ para algún $k,0\leq k<n$, o un cambio circular de tal secuencia.

Como trabaja el algoritmo

La siguiente es una red bitónica de 16 entradas:

Los 16 números ingresan por la entrada a la izquierda, se mueven a lo largo de cada una de las 16 líneas horizontales, y terminan en el salida del lado derecho. La red esta diseñada para ordenar los elementos, con el mayor número hacia abajo.

Las flechas son comparadores. Cada vez que dos números alcanzan los extremos de una flecha, son comparados para asegurar que la flecha apunta hacia el mayor número. Si estos estan desordenados, son intercambiados. Los recuadros coloreados son solo ilustrativos y no tienen ningun efecto en el algoritmo.

Cada recuadro rojo tiene la misma estructura: la entrada de la mitad superior es comparada con la entrada correspondiente de la mitad inferior, con todas las flechas apuntando hacia abajo (rojo oscuro) o todas apuntando hacia arriba (rojo claro). Si la entrada llega a ser una secuencia bitónica, entonces la salida serán dos secuencias bitónicas. La mitad superior de la salida será bitónica, así como la mitad inferior, con cada elemento de la parte superior menor o igual que cada elemento de la inferior (para los rojo oscuros) o viceversa (para los rojos claros). Este teorema no es obvio, pero puede ser verificado considerando cuidadosamente todos los casos de como las diferentes entradas pueden ser comparadas, usando el principio cero-uno.

Los recuadros rojos se combinan para formar los recuadros azules y verdes. Cada uno de estos tienen la misma estructura: un recuadro rojo es aplicado a toda la secuencia de entrada, luego para cada mitad del resultado, luego para cada cuarto de esos resultados y así sucesivamente. Todas las flechas apuntan hacia abajo (azules) o todas apuntan hacia arriba (verdes). Esta estructura es conocida como red mariposa. Si la entrada a este recuadro es bitónica, entonces la salida será ordenada de forma ascendente (azules) o forma descendente (verde). Si un número entra al recuadro azul o verde, entoces el primer recuadro rojo lo llevará a la mitad correcta de la lista. Este entoces pasará a traves de un recuadro rojo menor que lo coloca en la mitad correcta de la lista dentro de esa mitad. Este proceso continúa hasta que llega a su posición correcta. Por consiguiente, la salida de los recuadros verdes o azules termina completamente ordenada.

Los recuadros azules y verdes se combinan para formar la red de ordenamiento entera. Cualquier secuencia de entrada arbitraria, es ordenada correctamente por la red con el mayor hacia el fondo. La salida de cada recuadro azul o verde será una secuencia ordenada, así 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 recuadros azules o verdes toman N secuencias ordenadas y las concatena en pares para formar N/2 secuencias bitónicas, que son ordenadas por los recuadros en esa columna para formar N/2 secuencias ordenadas. Este proceso empieza con cada entrada en forma de una lista ordenada de un elemento, y continúa a traves de las columnas hasta que la última las mezcla en una sola lista ordenada. Devido a que la última etapa fue azul, esta lista final tendrá el elemento mayor hacia el fondo.

Cada recuadro verde realiza la misma operación que los azules, solo que ordenan en direcciones opuestas. Así, cada recuadro verde puede ser remplazado por uno azul seguido por un cruzamiento donde todos los cables unidos por flechas se mueven a la posición contraria. Esto posibilita que todas las flechas apunten en la misma dirección, pero hará que las lineas horizontales no sean rectas. Sin embargo, un cruzamiento puede ser colocado a la derecha de la mitad inferior de las salidas de cualquier recuadro rojo, y la ordenación todavia funcionaría correctamente, porque el reverso de una secuencia bitónica sigue siendo bitónico. Si un recuadro rojo tiene un cruzamiento antes y después de este, puede ser reordenado internamente de forma tal que los dos cruzamientos se cancelan, por lo que las lineas vuelven a ser rectas. Por eso, el siguiente diagrama es equivalente al anterior, donde cada recuadro verde se vuelve azul con un cruzamiento, y cada recuadro naranja es uno rojo que absorve dos cruzamientos:

Las puntas de las flechas no se dibujan dado que cada comparador ordena en la misma dirección. Los bloques azules y rojos realizan las mismas operaciones de antes. Los bloques naranjas son equivalentes a los bloques rojos, donde el orden de la secuencia se revierte para la mitad inferior de su entrada y la mitad inferior de su salida. Esta es la representación más común de una red de ordenación bitónica.

Código de ejemplo

El siguiente código es una implementación en Python del algoritmo de ordenamiento de mezcla bitónica. La entrada es un valor booleano up, y una lista x de longitud potencia de 2. La salida es una lista ordenada que es ascendente si up es true o descendente en otro caso.

def bitonic_sort(up, x):
    if len(x) <= 1:
        return x
    else: 
        first = bitonic_sort(True, x[:len(x) / 2])
        second = bitonic_sort(False, x[len(x) / 2:])
        return bitonic_merge(up, first + second)

def bitonic_merge(up, x): 
    # assume input x is bitonic, and sorted list is returned 
    if len(x) == 1:
        return x
    else:
        bitonic_compare(up, x)
        first = bitonic_merge(up, x[:len(x) / 2])
        second = bitonic_merge(up, x[len(x) / 2:])
        return first + second

def bitonic_compare(up, x):
    dist = len(x) / 2
    for i in range(dist):  
        if (x[i] > x[i + dist]) == up:
            x[i], x[i + dist] = x[i + dist], x[i] #swap

>>> bitonic_sort(True, [10, 30, 11, 20, 4, 330, 21, 110])
[4, 10, 11, 20, 21, 30, 110, 330]
>>> bitonic_sort(False, [10, 30, 11, 20, 4, 330, 21, 110])
[330, 110, 30, 21, 20, 11, 10, 4]

El siguiente es otra implementación en Java.

public class BitonicSort {
    static void kernel(int[] a, final int p, final int q) {
        final int d = 1 << (p-q);

        for(int i=0;i<a.length;i++) {
            boolean up = ((i >> p) & 2) == 0;

            if ((i & d) == 0 && (a[i] > a[i | d]) == up) {
                int t = a[i]; a[i] = a[i | d]; a[i | d] = t;
            }
        }
    }

    static void bitonicSort(final int logn, int[] a) {
        assert a.length == 1 << logn;

        for(int i=0;i<logn;i++) {
            for(int j=0;j<=i;j++) {
                kernel(a, i, j);
            }
        }
    }

    public static void main(String[] args) {
        final int logn = 5, n = 1 << logn;

        int[] a0 = new int[n];
        for(int i=0;i<n;i++) a0[i] = (int)(Math.random() * 1000);

        for(int k=0;k<a0.length;k++) System.out.print(a0[k] + " ");
        System.out.println();

        bitonicSort(logn, a0);

        for(int k=0;k<a0.length;k++) System.out.print(a0[k] + " ");
        System.out.println();
    }
}

Véase también

• Batcher odd–even mergesort

Enlaces externos

• Una discusión de este algoritmo
• Código de referencia en NIST
• Tutorial con imágenes animadas y código ejecutable
• Análisis Experimental de Algoritmos de Ordenamiento Paralelo