Flashsort es un algoritmo de ordenamiento de distribución que presenta una complejidad computacional lineal O ( n ) para conjuntos de datos distribuidos uniformemente y un requerimiento de memoria adicional relativamente bajo. El trabajo original fue publicado en 1998 por Karl-Dietrich Neubert. [1]
Flashsort es una implementación eficiente en el lugar de la ordenación por histograma , que es en sí misma un tipo de ordenación por cubos . Asigna cada uno de los n elementos de entrada a uno de los m cubos , reorganiza eficientemente la entrada para colocar los cubos en el orden correcto y luego ordena cada cubo. El algoritmo original ordena una matriz de entrada A de la siguiente manera:
Los pasos 1 a 3 y 6 son comunes a cualquier ordenamiento por cubos y se pueden mejorar utilizando técnicas genéricas para ordenamientos por cubos. En particular, el objetivo es que los cubos tengan un tamaño aproximadamente igual ( n / m elementos cada uno), [1] siendo el ideal la división en m cuantiles . Si bien el algoritmo básico es un ordenamiento por interpolación lineal , si se sabe que la distribución de entrada no es uniforme, una división no lineal se aproximará más a este ideal. Del mismo modo, el ordenamiento final puede utilizar cualquiera de varias técnicas, incluido un ordenamiento flash recursivo.
Lo que distingue a la clasificación flash es el paso 5: un algoritmo eficiente de O ( n ) en el lugar para recopilar los elementos de cada grupo juntos en el orden relativo correcto utilizando solo m palabras de memoria adicional.
La fase de reorganización de Flashsort funciona en ciclos . Los elementos comienzan como "no clasificados", luego se mueven al contenedor correcto y se consideran "clasificados". El procedimiento básico es elegir un elemento no clasificado, encontrar su contenedor correcto, intercambiarlo con un elemento no clasificado allí (que debe existir, porque contamos el tamaño de cada contenedor con anticipación), marcarlo como clasificado y luego repetir con el elemento no clasificado recién intercambiado. Finalmente, el elemento se intercambia consigo mismo y el ciclo termina.
Los detalles son fáciles de entender si se utilizan dos variables (del tamaño de una palabra) por contenedor. La parte inteligente es la eliminación de una de esas variables, lo que permite utilizar el doble de contenedores y, por lo tanto, dedicar la mitad del tiempo a la clasificación final O ( n 2 ) .
Para entenderlo con dos variables por contenedor, supongamos que hay dos matrices de m palabras adicionales: K b es el límite superior (fijo) del contenedor b (y K 0 = 0 ), mientras que L b es un índice (móvil) en el contenedor b , por lo que K b −1 ≤ L b ≤ K b .
Mantenemos la invariancia del bucle de que cada contenedor está dividido por L b en un prefijo no clasificado ( A i para K b −1 < i ≤ L b aún no se han movido a sus contenedores de destino) y un sufijo clasificado ( A i para L b < i ≤ K b están todos en el contenedor correcto y no se moverán nuevamente). Inicialmente L b = K b y todos los elementos están sin clasificar. A medida que avanza la clasificación, los L b se decrementan hasta que L b = K b −1 para todos los b y todos los elementos se clasifican en el contenedor correcto.
Cada ronda comienza encontrando el primer grupo c que no está clasificado de forma completa (que tiene K c −1 < L c ) y tomando el primer elemento no clasificado en ese grupo A i donde i = K c −1 + 1 . (Neubert llama a esto el "líder del ciclo"). Copie A i a una variable temporal t y repita:
Cuando se implementa de esta manera con dos variables por cubeta, la elección del punto de inicio i de cada ronda es, de hecho, arbitraria; cualquier elemento no clasificado puede usarse como líder del ciclo. El único requisito es que los líderes del ciclo puedan encontrarse de manera eficiente.
Aunque la descripción anterior utiliza K para encontrar los líderes del ciclo, de hecho es posible prescindir de él, lo que permite eliminar toda la matriz de m palabras. (Una vez completada la distribución, los límites de los cubos se pueden encontrar en L ).
Supongamos que hemos clasificado todos los elementos hasta i −1 y estamos considerando a A i como un nuevo líder de ciclo potencial. Es fácil calcular su grupo objetivo b . Por el invariante de bucle, se clasifica si L b < i ≤ K b , y no se clasifica si i está fuera de ese rango. La primera desigualdad es fácil de probar, pero la segunda parece requerir el valor K b .
Resulta que la hipótesis de inducción de que todos los elementos hasta i −1 están clasificados implica que i ≤ K b , por lo que no es necesario probar la segunda desigualdad.
Consideremos el grupo c en el que cae la posición i . Es decir, K c −1 < i ≤ K c . Por la hipótesis de inducción, todos los elementos por debajo de i , que incluye todos los grupos hasta K c −1 < i , están completamente clasificados. Es decir, ningún elemento que pertenezca a esos grupos permanece en el resto de la matriz. Por lo tanto, no es posible que b < c .
El único caso restante es b ≥ c , lo que implica K b ≥ K c ≥ i , QED
Al incorporar esto, el algoritmo de distribución flashsort comienza con L como se describió anteriormente e i = 1. Luego procede: [1] [2]
Si bien ahorra memoria, Flashsort tiene la desventaja de que vuelve a calcular el contenedor para muchos elementos ya clasificados. Esto ya se hace dos veces por elemento (una vez durante la fase de conteo de contenedores y una segunda vez al mover cada elemento), pero la búsqueda del primer elemento no clasificado requiere un tercer cálculo para la mayoría de los elementos. Esto podría resultar costoso si los contenedores se asignan utilizando una fórmula más compleja que la interpolación lineal simple. Una variante reduce el número de cálculos de casi 3 n a un máximo de 2 n + m − 1 al tomar el último elemento no clasificado en un contenedor inacabado como líder del ciclo:
La mayoría de los elementos tienen sus contenedores calculados solo dos veces, excepto el último elemento de cada contenedor, que se utiliza para detectar la finalización del contenedor siguiente. Se puede lograr una pequeña reducción adicional manteniendo un recuento de elementos sin clasificar y deteniéndose cuando llega a cero.
Los únicos requisitos de memoria adicionales son el vector auxiliar L para almacenar los límites de los contenedores y la cantidad constante de otras variables utilizadas. Además, cada elemento se mueve (a través de un búfer temporal, por lo que se requieren dos operaciones de movimiento) solo una vez. Sin embargo, esta eficiencia de memoria tiene la desventaja de que se accede a la matriz de forma aleatoria, por lo que no se puede aprovechar una caché de datos más pequeña que la matriz completa.
Al igual que con todas las ordenaciones por cubetas, el rendimiento depende críticamente del equilibrio de las cubetas. En el caso ideal de un conjunto de datos equilibrado, cada cubeta tendrá aproximadamente el mismo tamaño. Si la cantidad m de cubetas es lineal en el tamaño de entrada n , cada cubeta tiene un tamaño constante, por lo que ordenar una sola cubeta con un algoritmo O ( n 2 ) como la ordenación por inserción tiene una complejidad O (1 2 ) = O (1) . Por lo tanto, el tiempo de ejecución de las ordenaciones por inserción finales es m ⋅ O(1) = O ( m ) = O ( n ) .
La elección de un valor para m , el número de contenedores, compensa el tiempo empleado en clasificar elementos ( m alto ) y el tiempo empleado en el paso final de ordenación por inserción ( m bajo ). Por ejemplo, si se elige m proporcional a √ n , entonces el tiempo de ejecución de las ordenaciones por inserción finales es, por lo tanto, m ⋅ O( √ n 2 ) = O ( n 3/2 ) .
En los peores casos, donde casi todos los elementos están en unos pocos contenedores, la complejidad del algoritmo está limitada por el rendimiento del método de ordenación de contenedores final, por lo que se degrada a O ( n 2 ) . Las variaciones del algoritmo mejoran el rendimiento en el peor de los casos mediante el uso de ordenaciones de mejor rendimiento, como quicksort o flashsort recursivo en contenedores que exceden un cierto límite de tamaño. [2] [3]
Para m = 0,1 n con datos aleatorios distribuidos uniformemente, flashsort es más rápido que heapsort para todos los n y más rápido que quicksort para n > 80. Se vuelve aproximadamente el doble de rápido que quicksort en n = 10000. [ 1] Tenga en cuenta que estas mediciones se tomaron a fines de la década de 1990, cuando las jerarquías de memoria dependían mucho menos del almacenamiento en caché.
Debido a la permutación in situ que realiza flashsort en su proceso de clasificación, flashsort no es estable . Si se requiere estabilidad, es posible utilizar una segunda matriz para que los elementos se puedan clasificar secuencialmente. Sin embargo, en este caso, el algoritmo requerirá O ( n ) memoria adicional.