FlashSort

FlashSort es otro de los algoritmos de ordenación por distribución que tiene raíz en el algoritmo del Casillero, pero Flash no trabaja en tiempo lineal. Lo publicó Karl-Dietrich Neubert en 1.997 y no debemos confundirlo con el algoritmo del mismo nombre propuesto por J. H. Reif y L.G. Valiant en 1.983, éste es para procesos en paralelo sin relación con el de Neubert. La idea en la cual se basa Flashsort es: En un conjunto de datos con una distribución conocida, en función del rango del conjunto, es fácil estimar dónde se debe colocar un elemento.

 

Rendimiento – Complejidad
Mejor caso Ω Peor caso O Media Θ Espacio
(n) (n2) (n + m) (0,1n)

El algoritmo realiza los siguientes pasos:

  1. Localiza los valores mínimo y máximo en el vector, con ellos determinará, aproximadamente, cuál sería la posición dónde ubicar cada elemento.
  2. Los elementos del vector se dividen, dependiendo de su valor, en m «Clases» (ubicación aproximada) y se cuentan sus apariciones, guardando esta información en un vector auxiliar. Ya sabemos cuántos elementos pertenecen a cada clase m, (parecido al algoritmo Counting sort). Por ejemplo: Si tenemos un conjunto de elementos uniforme donde el mínimo (Emin) es 1 y el máximo (Emax) es 1.000 y 511 es un elemento del vector, podemos suponer que 511 estaría cerca del medio después de su ordenación. Su ubicación aproximada «Clase», es el cuartil calculado con la siguiente función:    
    donde:
    C = Cuartil.
    E = Elemento del vector.
    m = Nº de clases.
    int = Valor entero de la operación [ ].
    i= Índice.
    min = valor mínimo en el vector
    max = valor máximo en el vector
  3. Ordena los elementos de cada clase. (por permutación de los elementos).
  4. Utiliza el algoritmo de Inserción para finalizar la ordenación.

 

La eficiencia del algoritmo depende de la elección del número de clases, empíricamente Neubert estableció su valor óptimo en m ≈ 0,42 n. En el supuesto de aumentar el número de clases, aumentamos el número de operaciones en la ordenación y reducimos el nº de operaciones en la inserción, algo que evaluaríamos después de ejecutar el algoritmo y nos diría cuál opción sería la mejor, pero ya no tiene sentido, tenemos ordenado el vector.

 

Ejemplo:

Vector

55 44 5 11 35 91 34 2 12 68

 

1) Obtenemos los valores máximo y mínimo en el vector.

Emin  = 2

Emax = 91

 

2) Calculamos a cuál clase pertenece cada elemento. (Función Cuartil).

Elemento 55 44 5 11 35 91 34 2 12 68
Cuartil 2 2 1 1 2 4 2 1 1 3

 Contamos cuántos elementos hay en cada clase y los acumulamos. En la siguiente etapa (Permutación) lo necesitamos.

Clase (Cuartil) 1 2 3 4
Cantidad 4 4 1 1
Acumulado 4 8 9 10

3) Antes de comenzar la permutación situamos el elemento de mayor valor (Emax =  91) en la 1ª posición.

91 55 44 5 11 35 34 2 12 68

Permutamos (ordenamos los elementos por clase).

(91, el primer elemento). Es de la clase 4 y su contador tiene valor 10, entonces lo ubicamos en la posición 10 y su contador de clase se reduce en 1 y queda en 9.

(68, estaba en la posición 10 que ahora lo ocupa el 91). Es de la clase 3 y su contador tiene valor 9, se le ubica en la posición 9 y su contador de clase se reduce en 1 queda en 8.

(12, ocupa la posición 8). Es de la clase 1 y su contador tiene valor 4, se le ubica en la posición 4 y su contador de clase se reduce en 1 (3)

(11, ocupaba la posición 4). Es de la clase 1 y su contador tiene valor 3, se le ubica en la posición 3 y su contador de clase se reduce en 1 (2).

 

Se reitera el proceso hasta obtener:

Elemento 5 11 2 12 55 44 35 34 68 91
Clase 1 1 1 1 2 2 2 2 3 4

El detalle de estos movimientos se puede ver en Counting sort.

 

4) Realizamos una ordenación por inserción y tenemos el vector ordenado:

Elemento 2 5 11 12 34 35 44 55 68 91
Clase 1 1 1 1 2 2 2 2 3 4

 

Implementación en lenguaje Java.

Estuve dando vueltas para ver cómo desarrollaba el algoritmo y no alcanzaba una solución óptima, no estaba concentrado, bueno, estaba alterado.

 

Paseando a mi perro, un BullMastiff de un año, una colgada del THC me dijo que mi perro había mordido al suyo. Algo improbable, la dije, la mayoría de las personas que pasean sus perros por el parque de la «Cuña Verde» saben que es inofensivo y que está tan socializado que cuando ve un conflicto se aleja de forma inmediata. Pues bueno, la del THC insistió convirtiendo la conversación en un hilarante alejamiento de la realidad. Si mi perro hubiese mordido al suyo, probablemente lo hubiesen llevado al «Último Parque», es un cementerio para animales.

 

No entendía que era lo que pretendía esa mujer, pero otro paseante me dió respuestas, me dijo: Juan, no te dejes llevar por esa tía, está buscando dinero y lo único que pretende es hacerte perder los nervios para que la agredas y sacará una pasta, no es la primera vez que lo intenta. Os cuento este episodio como advertencia a los paseantes anónimos. Por gente de la que os hablo hago mío el pensamiento de Diógenes de Sinope: «Cuanta más gente idiotas conozco, más quiero a mi perro», por otro lado, gracias a los que estuvieron allí: Firu, James, Maya, Mera, Nos, Rolo, …

 

Su nombre "J". Amable, juguetón, tremendamente fuerte, tranquilo, es un peluche
«J»

En estas circunstancias he decidido copiar el algoritmo de la página de Karl-Dietrich Neubert que está traducido a Java por Rosanne Zhang.

No sé si estoy transmitiendo mi nerviosismo al procesador o es que el algoritmo tiene algún error, pero en algunas de las comprobaciones se ha dejado algún elemento sin clasificar. Llevo parte de la tarde-noche tratando de identificar el porqué de esos errores y nada, no consigo resultado. Esperaré a que mis neurotransmisores se estabilicen y volveré a comenzar las pruebas.

 

public static int [] private static int[] OrdenaFlash(int [] a) {
        int n = a.length;
        int m = n;
        int [] l = new int[m];

        int i = 0, j = 0, k = 0;
        int anmin = a[0];
        int nmax = 0;

        for (i = 1; i < n; i++) {
            if (a[i] < anmin) anmin = a[i]; if (a[i] > a[nmax])
                nmax = i;

        }

        if (anmin == a[nmax])
            return a;

        double c1 = ((double) m - 1) / (a[nmax] - anmin);

        for (i = 0; i < n; i++) {
            k = (int) (c1 * (a[i] - anmin));
            l[k]++;

        }

        for (k = 1; k < m; k++){
            l[k] += l[k - 1];

        }

        int hold = a[nmax];
        a[nmax] = a[0];
        a[0] = hold;

        int nmove = 0;
        int flash;
        j = 0;
        k = m - 1;

        while (nmove < n - 1) { while (j > (l[k] - 1)) {
                j++;
                k = (int) (c1 * (a[j] - anmin));

            }

            flash = a[j];

            while (!(j == l[k])) {
                k = (int) (c1 * (flash - anmin));

                hold = a[l[k] - 1];
                a[l[k] - 1] = flash;
                flash = hold;

                l[k]--;
                nmove++;

            }
        }
		return a;
    }

 

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.

🔴 Pulsar sobre el gráfico para ampliar.

 

Flashsort rendimiento de 10 a 100 mil elementos

Flashsort rendimiento de 100 mil a 1 millón de elementos