La clasificación en bloque , o clasificación por fusión en bloque , es un algoritmo de clasificación que combina al menos dos operaciones de fusión con una clasificación por inserción para llegar a O ( n log n ) (consulte la notación O grande ) en un tiempo de clasificación estable in situ . Recibe su nombre de la observación de que fusionar dos listas ordenadas, A y B , equivale a dividir A en bloques de tamaño uniforme , insertar cada bloque A en B según reglas especiales y fusionar pares AB .
Pok-Son Kim y Arne Kutzner propusieron un algoritmo práctico para la fusión in situ de O ( n log n ) en 2008. [1]
El bucle externo de clasificación de bloques es idéntico a una clasificación de combinación ascendente , donde cada nivel de la clasificación fusiona pares de subarreglos, A y B , en tamaños de 1, luego 2, luego 4, 8, 16, etc. hasta que ambos subarreglos combinados sean el arreglo mismo.
En lugar de fusionar A y B directamente como con los métodos tradicionales, un algoritmo de fusión basado en bloques divide A en bloques discretos de tamaño √ A (lo que resulta en √ A también una cantidad de bloques), [2] inserta cada bloque A en B de manera que el primer valor de cada bloque A es menor o igual (≤) al valor B inmediatamente después, luego fusiona localmente cada bloque A con cualquier valor B entre él y el siguiente bloque A.
Como las fusiones aún requieren un búfer separado lo suficientemente grande como para contener el bloque A que se va a fusionar, se reservan dos áreas dentro de la matriz para este propósito (conocidas como búferes internos ). [3] Los dos primeros bloques A se modifican para contener la primera instancia de cada valor dentro de A , con el contenido original de esos bloques desplazado si es necesario. Los bloques A restantes luego se insertan en B y se fusionan usando uno de los dos búferes como espacio de intercambio. Este proceso hace que se reorganicen los valores en ese búfer.
Una vez que cada bloque A y B de cada submatriz A y B se hayan fusionado para ese nivel de ordenación de combinación, los valores en ese búfer se deben ordenar para restaurar su orden original, por lo que se debe aplicar una ordenación por inserción. Luego, los valores de los buffers se redistribuyen a su primera posición ordenada dentro de la matriz. Este proceso se repite para cada nivel de la clasificación de combinación ascendente externa, momento en el cual la matriz se habrá ordenado de manera estable.
Los siguientes operadores se utilizan en los ejemplos de código:
Además, la clasificación de bloques se basa en las siguientes operaciones como parte de su algoritmo general:
Rotar (matriz, cantidad, rango) Invertir (matriz, rango) Invertir (matriz, [rango.inicio, rango.inicio + cantidad)) Invertir (matriz, [rango.inicio + cantidad, rango.fin))
PisoPoderDeDos (x) x = x | (x >> 1) x = x | (x >> 2) x = x | (x >> 4) x = x | (x >> 8) x = x | (x >> 16) si (este es un sistema de 64 bits ) x = x | (x >> 32) devolver x - (x >> 1)
Como se indicó anteriormente, el bucle externo de una clasificación por bloques es idéntico a una clasificación por combinación ascendente. Sin embargo, se beneficia de la variante que garantiza que cada subconjunto A y B tengan el mismo tamaño dentro de un elemento:
Ordenación de bloques (matriz) power_of_two = FloorPowerOfTwo (matriz.tamaño) escala = matriz.tamaño/potencia_de_dos // 1.0 ≤ escala < 2.0 // clasificación por inserción de 16 a 31 elementos a la vez para (fusionar = 0; fusionar < power_of_two; fusionar += 16) inicio = fusionar * escala fin = inicio + 16 * escala InsertionSort (matriz, [inicio, fin)) para (longitud = 16; longitud < potencia_de_dos; longitud += longitud) para (fusionar = 0; fusionar < potencia_de_dos; fusionar += longitud * 2) inicio = fusionar * escala medio = (fusionar + longitud) * escala final = (fusionar + longitud * 2) * escala if (array[end − 1] < array[start]) // los dos rangos están en orden inverso, por lo que una rotación es suficiente para fusionarlos Rotate (array, mid − start, [start, end)) else if (array [mid − 1] > array[mid]) Merge (array, A = [start, mid), B = [mid, end)) // de lo contrario, los rangos ya están ordenados correctamente
También se pueden utilizar matemáticas de punto fijo , representando el factor de escala como una fracción integer_part + numerator/denominator:
Ordenación de bloques (matriz) power_of_two = FloorPowerOfTwo (matriz.tamaño) denominador = potencia_de_dos/16 numerador_paso = matriz.tamaño % denominador paso_entero = piso (matriz.tamaño/denominador) // clasificación por inserción de 16 a 31 elementos a la vez mientras (paso_entero <matriz.tamaño) parte_entera = numerador = 0 while (integer_part <array.size) // obtiene los rangos para A y B inicio = parte_entero parte_entera += paso_entero numerador += numerador_paso si (numerador ≥ denominador) numerador −= denominador parte_entera++ medio = parte_entero parte_entera += paso_entero numerador += numerador_paso si (numerador ≥ denominador) numerador −= denominador parte_entera++ final = parte_entero if (matriz[fin − 1] < matriz[inicio]) Rotar (matriz, mitad − inicio, [inicio, fin)) else if (matriz[mediados − 1] > matriz[media]) Fusionar (matriz, A = [ inicio, mitad), B = [mitad, final)) paso_entero += paso_entero paso_numerador += paso_numerador si (paso_numerador ≥ denominador) paso_numerador −= denominador paso_entero++
Los dos buffers internos necesarios para cada nivel del paso de fusión se crean moviendo las primeras 2 √ A primeras instancias de sus valores dentro de un subarreglo A al inicio de A . Primero itera sobre los elementos en A y cuenta los valores únicos que necesita, luego aplica rotaciones de matriz para mover esos valores únicos al inicio. [6] Si A no contenía suficientes valores únicos para llenar los dos buffers (de tamaño √ A cada uno), B también se puede usar. En este caso, mueve la última instancia de cada valor al final de B , y esa parte de B no se incluye durante las fusiones.
mientras (paso_entero <matriz.tamaño) tamaño_bloque = √ paso_entero tamaño_búfer = paso_entero/tamaño_bloque + 1 [extraiga dos buffers de tamaño 'buffer_size' cada uno]
Si B tampoco contiene suficientes valores únicos, extrae la mayor cantidad de valores únicos que pudo encontrar, luego ajusta el tamaño de los bloques A y B de manera que el número de bloques A resultantes sea menor o igual al número de elementos únicos extraídos para el búfer. En este caso, solo se utilizará un búfer; el segundo búfer no existirá.
buffer_size = [número de valores únicos encontrados]tamaño_bloque = paso_entero/tamaño_búfer + 1 parte_entera = numerador = 0while (integer_part < array.size) [obtener los rangos para A y B] [ajustar A y B para no incluir los rangos utilizados por los buffers]
Una vez que se han creado uno o dos buffers internos, comienza a fusionar cada subarreglo A y B para este nivel del tipo de fusión. Para hacerlo, divide cada submatriz A y B en bloques de tamaño uniforme del tamaño calculado en el paso anterior, donde el primer bloque A y el último bloque B tienen un tamaño desigual si es necesario. Luego recorre cada uno de los bloques A de tamaño uniforme e intercambia el segundo valor con un valor correspondiente del primero de los dos buffers internos. Esto se conoce como etiquetar los bloques.
// bloqueA es el rango de los bloques A restantes, // y primeroA es el primer bloque A de tamaño desigualbloqueA = [A.inicio, A.fin)primeroA = [A.inicio, A.inicio + |bloqueA| % tamaño de bloque) // intercambia el segundo valor de cada bloque A con el valor en buffer1 for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size) Swap (array[buffer1.start + index] , matriz[índiceA]) índice++ últimoA = primeroAbloqueB = [B.inicio, B.inicio + mínimo (tamaño_bloque, |B|))blockA.start += |firstA|
Después de definir y etiquetar los bloques A de esta manera, los bloques A se desplazan a través de los bloques B intercambiando el primer bloque A de tamaño uniforme con el siguiente bloque B. Este proceso se repite hasta que el primer valor del bloque A con el valor de etiqueta más pequeño sea menor o igual al último valor del bloque B que acaba de intercambiarse con un bloque A.
En ese punto, el bloque A mínimo (el bloque A con el valor de etiqueta más pequeño) se intercambia al inicio de los bloques A rodantes y el valor etiquetado se restaura con su valor original del primer búfer. Esto se conoce como dejar caer un bloque atrás, ya que ya no rodará junto con los bloques A restantes. Luego, ese bloque A se inserta en el bloque B anterior, primero usando una búsqueda binaria en B para encontrar el índice donde el primer valor de A es menor o igual al valor en ese índice de B, y luego rotando A en B en ese índice.
minA = bloqueA.inicio índiceA = 0 while (verdadero) // si hay un bloque B anterior y el primer valor del bloque A mínimo es ≤ // el último valor del bloque B anterior, entonces deje ese bloque A mínimo detrás. // o si no quedan bloques B, sigue soltando los bloques A restantes. if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0) // descubre dónde dividir el bloque B anterior y gíralo en la división B_split = BinaryFirst (matriz, matriz [minA], últimoB) B_restante = lastB.end - B_split // cambia el bloque A mínimo al comienzo de los bloques A rodantes BlockSwap (array, blockA.start, minA, block_size) // restaurar el segundo valor para el intercambio del bloque A (matriz[bloqueA.start + 1], matriz[buffer1.start + indexA]) índiceA++ // rotar el bloque A al bloque B anterior Rotar (matriz, blockA.start - B_split, [B_split, blockA.start + block_size)) // fusionar localmente el bloque A anterior con los valores B que le siguen, // usando el segundo buffer interno como espacio de intercambio (si existe) if (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B_split), buffer2) más MergeInPlace (matriz, lastA, [lastA.end, B_split)) // actualiza el rango para los bloques A restantes, // y el rango restante del bloque B después de dividirlo últimoA = [bloqueA.inicio - B_restante, bloqueA.inicio - B_restante + tamaño_bloque) últimoB = [últimoA.fin, últimoA.fin + B_restante) // si no quedan más bloques A, este paso finaliza bloqueA.inicio = bloqueA.inicio + tamaño_bloque si (|bloqueA| = 0) romper minA = [nuevo bloque A mínimo] (ver más abajo) else if (|blockB| < block_size) // mueve el último bloque B, que tiene un tamaño desigual, // antes de los bloques A restantes, usando una rotación Rotate (matriz , bloqueB.inicio - bloqueA.inicio, [bloqueA.inicio, bloqueB.fin)) últimoB = [bloqueA.inicio, bloqueA.inicio + |bloqueB|) bloqueA.start += |bloqueB| bloqueA.end += |bloqueB| minA += |bloqueB| bloqueB.end = bloqueB.inicio else // rueda el bloque A más a la izquierda hasta el final intercambiándolo con el siguiente bloque B BlockSwap (array, blockA.start, blockB.start, block_size) últimoB = [bloqueA.inicio, bloqueA.inicio + tamaño_bloque) si (minA = bloqueA.inicio) minA = bloqueA.end bloqueA.start += tamaño_bloque bloqueA.end += tamaño_bloque blockB.start += tamaño_bloque // esto es equivalente al mínimo (blockB.end + block_size, B.end), // pero tiene el potencial de desbordarse si (blockB.end > B.end - block_size) bloqueB.end = B.fin demás bloqueB.end += tamaño_bloque // fusiona el último bloque A con los valores B restantes if (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B.end), buffer2) else MergeInPlace (array, lastA, [lastA.end, Doblar))
Una optimización que se puede aplicar durante este paso es la técnica del agujero flotante . [7] Cuando el bloque A mínimo se queda atrás y necesita rotarse al bloque B anterior, después de lo cual su contenido se intercambia en el segundo búfer interno para las fusiones locales, sería más rápido intercambiar el bloque A al búfer de antemano, y aprovechar el hecho de que el contenido de ese buffer no necesita conservar ningún orden. Entonces, en lugar de rotar el segundo búfer (que solía ser el bloque A antes del intercambio de bloques) al bloque B anterior en la posición index , los valores en el bloque B después del índice pueden simplemente intercambiarse en bloque con los últimos elementos del búfer.
El agujero flotante en este caso se refiere al contenido del segundo búfer interno que flota alrededor de la matriz y actúa como un agujero en el sentido de que los elementos no necesitan mantener su orden.
Una vez que el bloque A se ha rotado hacia el bloque B, el bloque A anterior se fusiona con los valores B que le siguen, utilizando el segundo búfer como espacio de intercambio. Cuando el primer bloque A se deja atrás, esto se refiere al bloque A de tamaño desigual al principio, cuando el segundo bloque A se deja atrás, significa el primer bloque A, y así sucesivamente.
MergeInternal (array, A, B, buffer) // bloquea el intercambio de los valores en A con los del 'buffer' BlockSwap (array, A.start, buffer.start, |A|) A_count = 0, B_count = 0, insertar = 0 while (A_count < |A| y B_count < |B|) if (matriz[buffer.start + A_count] ≤ matriz[B.start + B_count]) Intercambiar (matriz[A.start + insert], matriz[buffer.start + A_count]) A_count++ else Intercambiar (matriz[A.start + insert], matriz[B.start + B_count]) B_cuenta++ insertar++ // bloque intercambia la parte restante del buffer con la parte restante de la matriz BlockSwap (matriz, buffer.start + A_count, A.start + insert, |A| - A_count)
Si el segundo buffer no existe, se debe realizar una operación de fusión estrictamente in situ, como una versión basada en rotación del algoritmo de Hwang y Lin, [7] [8] el algoritmo de Dudzinski y Dydek, [9] o un búsqueda binaria repetida y rotación.
MergeInPlace (array, A, B) while (|A| > 0 and |B| > 0) // encuentra el primer lugar en B donde se debe insertar el primer elemento en A mid = BinaryFirst (array, array[A. inicio], B) // rotar A en su lugar cantidad = mitad - A.final Rotar (matriz, cantidad, [A.start, mid)) // calcula los nuevos rangos A y B B = [medio, B.final) A = [A.inicio + monto, mitad) A.inicio = BinaryLast (matriz, matriz [A.inicio], A)
Después de eliminar el bloque A mínimo y fusionar el bloque A anterior con los valores B que le siguen, el nuevo bloque A mínimo debe encontrarse dentro de los bloques que aún se están desplazando a través de la matriz. Esto se maneja ejecutando una búsqueda lineal a través de esos bloques A y comparando los valores de las etiquetas para encontrar el más pequeño.
minA = blockA.start for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size) if (matriz[findA + 1] < matriz[minA + 1]) minA = encontrarA
Estos bloques A restantes continúan rodando a través de la matriz y siendo soltados e insertados donde pertenecen. Este proceso se repite hasta que todos los bloques A se hayan soltado y girado hacia el bloque B anterior.
Una vez que el último bloque A restante se haya dejado atrás y se haya insertado en B, donde pertenece, debe fusionarse con los valores B restantes que le siguen. Esto completa el proceso de fusión para ese par particular de subarreglos A y B. Sin embargo, luego debe repetir el proceso para los subarreglos A y B restantes para el nivel actual de clasificación de combinación.
Tenga en cuenta que los buffers internos se pueden reutilizar para cada conjunto de subarreglos A y B para este nivel de clasificación de combinación, y no es necesario volver a extraerlos ni modificarlos de ninguna manera.
Después de fusionar todos los subarreglos A y B, aún quedan uno o dos buffers internos. El primer búfer interno se usó para etiquetar los bloques A, y su contenido todavía está en el mismo orden que antes, pero es posible que el contenido del segundo búfer interno se haya reorganizado cuando se usó como espacio de intercambio para las fusiones. Esto significa que el contenido del segundo búfer deberá ordenarse utilizando un algoritmo diferente, como la ordenación por inserción. Luego, los dos búferes deben redistribuirse nuevamente en la matriz utilizando el proceso opuesto al que se utilizó para crearlos.
Después de repetir estos pasos para cada nivel de la clasificación de combinación de abajo hacia arriba, se completa la clasificación de bloques.
La clasificación de bloques funciona extrayendo dos buffers internos, dividiendo los subarreglos A y B en bloques de tamaño uniforme, rodando y soltando los bloques A en B (usando el primer buffer para rastrear el orden de los bloques A), fusionando localmente usando el segundo buffer como intercambio. espacio, ordenando el segundo búfer y redistribuyendo ambos búfer. Si bien los pasos no cambian, estos subsistemas pueden variar en su implementación real.
Una variante de clasificación de bloques le permite utilizar cualquier cantidad de memoria adicional que se le proporcione, mediante el uso de este búfer externo para fusionar un subarreglo A o un bloque A con B siempre que A encaje en él. En esta situación sería idéntico a una especie de fusión.
Algunas buenas opciones para el tamaño del búfer incluyen:
En lugar de etiquetar los bloques A usando el contenido de uno de los buffers internos, se puede usar un buffer de imitación de movimiento indirecto. [1] [10] Este es un búfer interno definido como s1 t s2 , donde s1 y s2 son cada uno tan grandes como el número de bloques A y B, y t contiene cualquier valor inmediatamente después de s1 que sea igual al último valor de s1 (asegurando así que ningún valor en s2 aparezca en s1 ). Todavía se utiliza un segundo búfer interno que contiene √ A valores únicos. Los primeros valores √ A de s1 y s2 luego se intercambian entre sí para codificar información en el búfer sobre qué bloques son bloques A y cuáles son bloques B. Cuando un bloque A en el índice i se intercambia con un bloque B en el índice j (donde el primer bloque A de tamaño uniforme está inicialmente en el índice 0), s1[i] y s1[j] se intercambian con s2[i] y s2[ j], respectivamente. Esto imita los movimientos de los bloques A a través de B. Los valores únicos en el segundo búfer se utilizan para determinar el orden original de los bloques A a medida que avanzan a través de los bloques B. Una vez que se han eliminado todos los bloques A, el búfer de imitación de movimiento se usa para decodificar si un bloque determinado en la matriz es un bloque A o un bloque B, cada bloque A se gira hacia B y se usa el segundo búfer interno. como espacio de intercambio para las fusiones locales.
No es necesario etiquetar el segundo valor de cada bloque A; en su lugar se puede utilizar el primero, el último o cualquier otro elemento. Sin embargo, si el primer valor está etiquetado, los valores deberán leerse desde el primer búfer interno (donde se intercambiaron) al decidir dónde colocar el bloque A mínimo.
Se pueden utilizar muchos algoritmos de clasificación para ordenar el contenido del segundo búfer interno, incluidos tipos inestables como Quicksort , ya que se garantiza que el contenido del búfer será único. Sin embargo, todavía se recomienda la ordenación por inserción por su rendimiento situacional y su falta de recursividad.
Las implementaciones conocidas de clasificación de bloques incluyen:
La clasificación de bloques es una clase de algoritmos bien definida y comprobable, con implementaciones funcionales disponibles como combinación y clasificación. [11] [15] [12] Esto permite medir y considerar sus características.
La clasificación por bloques comienza realizando la clasificación por inserción en grupos de 16 a 31 elementos de la matriz. La clasificación por inserción es una operación, por lo que esto lleva a cualquier lugar desde hasta , que es una vez que se omiten los factores constantes . También debe aplicar una ordenación por inserción en el segundo búfer interno después de que se complete cada nivel de fusión. Sin embargo, como este búfer estaba limitado en tamaño, la operación también termina siendo .
A continuación, debe extraer dos búferes internos para cada nivel del tipo de combinación. Lo hace iterando sobre los elementos en los subarreglos A y B e incrementando un contador cada vez que cambia el valor, y al encontrar suficientes valores, los rota al inicio de A o al final de B. En el peor de los casos, esto terminará buscar en toda la matriz antes de encontrar valores únicos no contiguos, lo que requiere comparaciones y rotaciones de valores. Esto se resuelve en , o .
Cuando ninguno de los subarreglos A o B contenía valores únicos para crear los buffers internos, se realiza una operación de fusión in situ normalmente subóptima donde busca binariamente y rota repetidamente A en B. Sin embargo, la conocida falta de valores únicos dentro de cualquiera de los subarreglos impone un límite estricto en la cantidad de búsquedas binarias y rotaciones que se realizarán durante este paso, que nuevamente son elementos rotados hasta veces, o . El tamaño de cada bloque también se ajusta para que sea más pequeño en el caso de que encuentre valores únicos pero no 2 , lo que limita aún más el número de valores únicos contenidos en cualquier bloque A o B.
El etiquetado de los bloques A se realiza varias veces para cada subconjunto A, luego los bloques A se enrollan y se insertan en los bloques B hasta veces. Las fusiones locales conservan la misma complejidad de una fusión estándar, aunque con más asignaciones ya que los valores deben intercambiarse en lugar de copiarse. La búsqueda lineal para encontrar el nuevo bloque A mínimo se repite a lo largo de los bloques . Y el proceso de redistribución del buffer es idéntico a la extracción del buffer pero a la inversa, y por tanto tiene la misma complejidad.
Después de omitir toda la complejidad excepto la más alta y considerar que hay niveles en el bucle de fusión externo, esto conduce a una complejidad asintótica final de para los peores y promedios casos. En el mejor de los casos, cuando los datos ya están en orden, el paso de combinación realiza comparaciones para el primer nivel, luego ,,, etc. Esta es una serie matemática muy conocida que se resuelve como .
Como la clasificación de bloques no es recursiva y no requiere el uso de asignaciones dinámicas , esto conduce a un espacio de pila y montón constante. Utiliza memoria auxiliar O(1) en un modelo transdicotómico , que acepta que los bits O(log n ) necesarios para realizar un seguimiento de los rangos de A y B no pueden ser mayores que 32 o 64 en 32 o 64 bits. sistemas informáticos, respectivamente, y por lo tanto simplifica a O(1) el espacio para cualquier matriz que pueda asignarse de manera factible.
Aunque los elementos de la matriz se desordenan durante la clasificación de bloques, cada operación es completamente reversible y habrá restaurado el orden original de los elementos equivalentes al finalizar.
La estabilidad requiere que la primera instancia de cada valor en una matriz antes de ordenar siga siendo la primera instancia de ese valor después de ordenar. La ordenación en bloque mueve estas primeras instancias al inicio de la matriz para crear los dos buffers internos, pero cuando se completan todas las fusiones para el nivel actual de la ordenación en bloque, esos valores se distribuyen nuevamente a la primera posición ordenada dentro de la matriz. Esto mantiene la estabilidad.
Antes de pasar los bloques A a través de los bloques B, cada bloque A tiene su segundo valor intercambiado con un valor del primer búfer. En ese punto, los bloques A se mueven fuera de orden para pasar por los bloques B. Sin embargo, una vez que encuentra dónde debe insertar el bloque A más pequeño en el bloque B anterior, ese bloque A más pequeño se mueve nuevamente al inicio de los bloques A y se restaura su segundo valor. Cuando se hayan insertado todos los bloques A, los bloques A estarán en orden nuevamente y el primer búfer contendrá sus valores originales en el orden original.
El uso del segundo búfer como espacio de intercambio al fusionar un bloque A con algunos valores B hace que se reorganice el contenido de ese búfer. Sin embargo, como el algoritmo ya garantiza que el búfer solo contenga valores únicos, ordenar el contenido del búfer es suficiente para restaurar su orden estable original.
La clasificación por bloques es una clasificación adaptativa en dos niveles: primero, omite la fusión de los subarreglos A y B que ya están en orden. A continuación, cuando es necesario fusionar A y B y dividirlos en bloques de tamaño uniforme, los bloques A solo se hacen rodar a través de B tanto como sea necesario, y cada bloque solo se fusiona con los valores B inmediatamente siguientes. Cuanto más ordenados estuvieran originalmente los datos, menos valores B habrá que fusionar en A.
La clasificación por bloques es una clasificación estable que no requiere memoria adicional, lo cual es útil en casos en los que no hay suficiente memoria libre para asignar el búfer O(n). Cuando se utiliza la variante de búfer externo de clasificación de bloques, se puede escalar desde el uso de memoria O(n) hasta búferes progresivamente más pequeños según sea necesario, y seguirá funcionando de manera eficiente dentro de esas limitaciones.
La clasificación por bloques no explota rangos ordenados de datos en un nivel tan fino como otros algoritmos, como Timsort . [16] Solo verifica estos rangos ordenados en los dos niveles predefinidos: los subarreglos A y B, y los bloques A y B. También es más difícil de implementar y paralelizar en comparación con una ordenación por fusión.
