Ordenamiento bitónico

El 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.^[1]

Una sucesión ordenada es una sucesión monótonamente no-decreciente (o no-creciente). Una sucesión bitónica es una sucesión 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 la misma.

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 la salida del lado derecho. La red está 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, se comparan para asegurar que la flecha apunta hacia el mayor número. Si estos están desordenados, se intercambian. Los recuadros coloreados son solo ilustrativos y no tienen ningún 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, entonces el primer recuadro rojo lo llevará a la mitad correcta de la lista. Este entonces pasará a través 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 través de las columnas hasta que la última las mezcla en una sola lista ordenada. Debido 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 líneas 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 todavía 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 líneas 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();
    }
}

Referencias

↑ «Bitonic sorting network for n not a power of 2». Archivado desde el original el 4 de diciembre de 2016. Consultado el 27 de noviembre de 2015.

Enlaces externos

Una discusión de este algoritmo Archivado el 10 de enero de 2017 en Wayback Machine.
Código de referencia en NIST
Tutorial con imágenes animadas y código ejecutable
Análisis Experimental de Algoritmos de Ordenamiento Paralelo

Datos: Q4918918

[1] «Bitonic sorting network for n not a power of 2». Archivado desde el original el 4 de diciembre de 2016. Consultado el 27 de noviembre de 2015.

[1]