Tome una matriz de orden inverso y aplique la
clasificación con inserciones simples .
Vea con qué crujido se inserta el siguiente elemento en el lugar correcto. Para ello, debe liberar el lugar de inserción, por lo que debe cambiar todos los elementos insertados anteriormente.
¡Y qué bueno sería si hubiera espacios vacíos entre los elementos que se insertaron anteriormente! Entonces uno no tendría que arrastrar las filas de elementos solo por insertar uno.
En 2004, tres expertos en informática - Michael Bender, Martin Farah-Colton y Miguel Mostiro - decidieron modificar la clasificación con inserciones simples de esta manera. Sugirieron formar una parte ordenada de la matriz, dejando espacios entre los elementos insertados.
El bibliotecario necesita que los libros estén ordenados alfabéticamente en un estante largo: comenzando a la izquierda de la letra "A", los libros están uno al lado del otro "I". Si la biblioteca recibió un nuevo libro relacionado con la sección "B", entonces para colocarlo en el estante en el lugar correcto, debe mover cada libro, comenzando desde el medio de la sección "B" hasta la última "I". Esto se ordena por inserciones simples. Sin embargo, si el bibliotecario reservó el espacio libre en cada sección, le bastaba con mover solo unos pocos libros para dejar espacio a las novedades de libros. Este es el principio básico de la clasificación de bibliotecas.
Algoritmo
- 1. Cree una matriz auxiliar vacía, varias veces más grande que la principal.
- 2. Para el siguiente elemento, buscamos el lugar de inserción en la matriz auxiliar.
- 2.1. Si encuentra un lugar para insertar, transfiera el artículo y regrese al paso 2.
- 2.2. Si no hay lugar para la inserción, vuelva a equilibrar la matriz auxiliar y regrese al punto 2.
- 3. Después de procesar todos los elementos, transfiéralos nuevamente a la matriz principal.
A primera vista, parece que la clasificación es fácil y sencilla. Para disipar esta ilusión, consideramos los puntos clave del algoritmo con más detalle.
Tamaño de matriz auxiliar
Si bien no existe una opinión establecida, cuántas veces la matriz auxiliar debe ser más grande que la principal.
Si toma demasiado, entonces habrá mucho espacio entre los elementos, sin embargo, la búsqueda del sitio de inserción y el reequilibrio serán más lentos, debido a las grandes distancias entre los elementos. El reequilibrio ocurrirá con menos frecuencia, pero tendrán que gastar más recursos en ellos. Si toma muy poco, entonces buscar y reequilibrar será más barato, pero tendrá que reformatear la matriz con más frecuencia. En general, aún debe probarse con diferentes valores y el método de búsqueda científica determina la mejor opción.
Si decidimos cuántas veces la matriz auxiliar es más grande que la matriz principal, entonces la fórmula para determinar el número exacto de elementos para ella se ve así:
NewSize = ε × (Tamaño + 1) - 1NewSize: el número de elementos en la matriz auxiliar
ε: cuántas veces la matriz auxiliar es más grande que la matriz principal
Tamaño: el número de elementos en la matriz principalSi simplemente multiplicamos el tamaño por un factor:
NewSize = Size × ε , entonces para una distribución uniforme no tendremos suficientes celdas en la cantidad de
ε - 1 piezas. Es decir, es posible organizarlos de manera uniforme, pero la primera celda llena o la última se ubicarán cerca del borde de la matriz auxiliar. Y necesitamos que los lugares vacíos en las celdas llenas se reserven desde todos los lados, incluso antes del primer elemento y después del último.
Parece un poco, pero de hecho es importante para el reequilibrio, para garantizar lugares libres para la inserción en cualquier lugar, incluso cuando se procesan los últimos elementos de la matriz principal.
Busque el lugar de inserción en la matriz auxiliar
Por supuesto, aquí necesitas una búsqueda binaria. Sin embargo, la implementación clásica no funcionará para nosotros.
En primer lugar, la matriz auxiliar consiste principalmente en vacío. Por lo tanto, dicotomizando recursivamente la estructura, en su mayor parte nos encontraremos con celdas sin rellenar. En estos casos, debe ir un poco hacia la izquierda o hacia la derecha, hasta la celda no vacía más cercana. Luego, al final del segmento, habrá elementos significativos que le permitirán calcular la media aritmética y continuar la búsqueda binaria en profundidad.
En segundo lugar, no te olvides de los bordes. Si necesita insertar un elemento mínimo o máximo, entonces una búsqueda binaria entre los elementos insertados anteriormente no conducirá a nada. Por lo tanto, vale la pena considerar los casos límite: primero verifique si es necesario colocar un elemento cerca del borde izquierdo o derecho de la matriz y, si no, use la búsqueda binaria.
En tercer lugar, teniendo en cuenta los detalles de la aplicación, vale la pena realizar modificaciones adicionales para minimizar el número de reequilibrios de matriz. Si el elemento insertado es igual al valor en uno de los extremos del segmento, entonces quizás no debería insertarlo en el medio del segmento. Es más lógico poner al lado de un elemento de igual valor. Esto llenará más eficientemente el espacio vacío de la matriz auxiliar.
Cuarto, quinto, y así sucesivamente. La calidad de la búsqueda de la ubicación de inserción afecta directamente la velocidad de clasificación, ya que la selección de ubicaciones de inserción sin éxito conduce a un reequilibrio innecesario. Por ejemplo, puede valer la pena dividir los segmentos no exactamente en el medio, sino más cerca del borde izquierdo o derecho del segmento, dependiendo de qué borde el elemento de inserción tiene un valor más cercano.
El algoritmo de búsqueda binario en sí está lleno de trampas, y teniendo en cuenta los matices adicionales mencionados anteriormente, finalmente no se convierte en una tarea no trivial.
Reequilibrio de matrices
La búsqueda binaria no es lo más difícil de implementar en esta clasificación. Todavía hay reequilibrio.
Cuando no hay lugar para la inserción (se encontraron elementos similares, pero no había celdas libres entre ellos), debe sacudir la matriz auxiliar para liberar el lugar de inserción. Este temblor de la matriz está reequilibrando.
Además, el reequilibrio es
local o
completo .
Reequilibrio local
Cambiamos tantos elementos como sea necesario para liberar el punto de inserción. La implementación de dicho equilibrio es muy simple, solo necesita encontrar la celda vacía más cercana desde el punto de inserción y usarla para mover varios elementos.
Hay posibles matices. Por ejemplo, ¿qué manera de buscar el lugar vacante más cercano? Para evitar la situación cuando un cambio es imposible (es decir, si en algún lado todas las celdas están ocupadas hasta el borde de la matriz), puede centrarse en la posición del punto de inserción en relación con el centro de la matriz. Si necesita insertar en el lado izquierdo de la matriz, luego cambie a la derecha, si está a la derecha, a la izquierda. Si
ε ≥ 2, entonces este enfoque elimina la situación en la que un cambio es imposible (porque en la mitad de la matriz auxiliar hay espacio más que suficiente para todos los elementos).
En la interpretación del autor del algoritmo, el reequilibrio local está implícito.
Reequilibrio completo
Una alternativa interesante al local es el reequilibrio completo. Es decir, en la matriz auxiliar, cambie todos los elementos disponibles para que haya (casi) los mismos espacios entre ellos.
Probé ambas opciones y hasta ahora estoy observando que con el reequilibrio local el algoritmo funciona 1.5-2 veces más rápido que con uno completo. Sin embargo, un reequilibrio completo aún puede ser útil. Por ejemplo, si tiene que hacer un reequilibrio local con demasiada frecuencia, esto significa que en la matriz en algunas áreas se han acumulado muchos "coágulos de sangre" que inhiben todo el proceso. Un reequilibrio completo realizado una vez, le permite deshacerse de toda congestión local de una sola vez.
Veamos cómo reequilibrar por completo.
Primero debe calcular cuántas celdas máximas podemos asignar para cada elemento en la matriz auxiliar. Debe recordarse que las celdas vacías deben ser ambas antes de la primera y después de la última celda llena. La formula es:
M: el número de celdas que se pueden asignar a cada elemento
NewSize - tamaño de la matriz auxiliar
Recuento: el número actual de elementos no vacíos en la matriz auxiliarEsta fracción debe reducirse a un valor entero (es decir, redondeado hacia abajo). Es obvio por la fórmula que cuantos más elementos ya se transfieren a la matriz auxiliar, menos celdas podemos seleccionar para la vecindad de cada elemento.
Conociendo
M , obtenemos fácilmente la posición exacta de cada elemento no vacío en la matriz auxiliar en la que debe ubicarse después de completar el reequilibrio.
NewPos = Número × MNewPos: nueva posición del elemento después del reequilibrio
Número: cuál es el elemento no vacío en la matriz auxiliar (1 ≤ Número ≤ Recuento)
M: el número de celdas que se asigna a cada elementoSe conocen nuevas posiciones, ¿puede simplemente ordenar elementos no vacíos en la matriz auxiliar y transferirlos a otros lugares? Oh no, no te apresures. No solo es necesario transferir elementos, es importante mantener su orden. Y como resultado de la búsqueda e inserción binarias, los elementos pueden quedar muy a la izquierda y a la derecha de la posición en la que deberían estar después del reequilibrio. Y en el lugar donde desea moverse, puede haber otro elemento que también debe adjuntarse en algún lugar. Además, no puede transferir un elemento si hay otros elementos entre sus posiciones antiguas y nuevas en la matriz auxiliar; de lo contrario, los elementos se mezclarán y es extremadamente importante para nosotros no mezclar el orden.
Por lo tanto, para reequilibrar no será suficiente pasar por el ciclo habitual y simplemente cambiar cada elemento de un bolsillo a otro. Todavía es necesario usar la recursividad. Si un elemento no se puede mover a un lugar nuevo (aparecieron otros elementos entre sus posiciones antiguas y nuevas), primero debe descubrir (recursivamente) estos invitados no invitados. Y luego todo se organizará correctamente.
Caso degenerado
Para la mayoría de las clasificaciones por inserciones, una matriz de orden inverso es la peor situación. Y ordenar un bibliotecario, por desgracia, no es una excepción.
Los elementos tienden al borde izquierdo de la matriz auxiliar, como resultado de lo cual los espacios vacíos se agotan rápidamente. Tienes que reequilibrar la matriz muy a menudo.
Por cierto, si tomamos una matriz casi ordenada (el mejor caso para ordenar por inserciones simples), entonces tenemos el mismo problema. Los elementos recién llegados no obstruirán la izquierda, sino el lado derecho de la matriz auxiliar, lo que también conducirá a un reequilibrio demasiado frecuente.
La ordenación de bibliotecas maneja conjuntos de datos aleatorios de manera eficiente. El pedido parcial (tanto directo como inverso) perjudica el rendimiento de la velocidad.
Complejidad Algorítmica
En grandes conjuntos de datos aleatorios, el algoritmo da la complejidad temporal O (
n log
n ). ¡Nada mal!
En conjuntos de datos únicos aleatorios (o en su mayoría únicos) con la selección correcta del coeficiente
ε y la implementación exitosa de la búsqueda binaria, el número de reequilibrios se puede minimizar o incluso evitar. Se puede argumentar que el algoritmo tiene la mejor complejidad de tiempo O (
n ).
Un gran porcentaje de datos que se repiten en valor, así como la presencia en la matriz de subsecuencias ordenadas (en orden directo o inverso) conduce a un reequilibrio frecuente de la matriz auxiliar y, como resultado, a la degradación de la complejidad del tiempo a O
(n 2 ) en los casos más desfavorables.
La desventaja del algoritmo, por supuesto, es que la matriz auxiliar requiere O (
n ) memoria adicional.
Posibles formas de mejorar
Aunque el algoritmo en sí mismo es instructivo y eficiente en datos aleatorios, en una década y media, pocos han mostrado interés en él.
Si buscas en Google la solicitud "ordenamiento de biblioteca", encontrarás un artículo superficial en la Wikipedia en inglés, el PDF del autor (del cual se entiende poco) y una rara publicación de esta escasa información. Además, hay una buena visualización en YouTube, donde las matrices principal y auxiliar se combinaron originalmente. Todos los enlaces están al final del artículo.
La búsqueda de "clasificación de bibliotecas" es aún más divertida: en la muestra encontrará las diferentes clasificaciones incluidas en diferentes bibliotecas, sin embargo, estos algoritmos no estarán relacionados con la
clasificación de bibliotecas auténtica .
Y hay algo que mejorar:
- Selección empírica del coeficiente óptimo ε .
- Modificación (teniendo en cuenta los detalles del algoritmo general) de la búsqueda binaria para la determinación más eficiente del punto de inserción.
- Minimizando los costos de reequilibrio.
Si pules estos lugares, ¿entonces quizás la clasificación de la biblioteca en velocidad sea igual a la clasificación rápida?
Código fuente
No logré preparar la implementación en Python, hay una versión que funciona en PHP.
Algoritmo básicofunction LibrarySort($arr) { global $arr_new;
La nueva posición del elemento en la matriz adicional después del reequilibrio completo Búsqueda binaria de lugar de inserción en matriz auxiliar Si durante la búsqueda el elemento es igual a uno de los extremos del segmento Reequilibrio local de una matriz adicional Reequilibrio completo de la matriz adicional Movimiento del elemento hacia la izquierda con reequilibrio total Tuve que codificar desde cero, basado en una descripción general del método. No vi una velocidad cercana a la ordenación rápida; mi opción de ordenación de la biblioteca ordena 10-20 veces más lento que la ordenación rápida. Pero la razón, por supuesto, es que mi implementación es demasiado cruda, no se ha tenido mucho en cuenta.
Me gustaría ver una versión de los creadores del algoritmo. Escribiré hoy a los autores (y les arrojaré un enlace a este habrastatu), de repente responderán. Aunque ... recuerdo, intenté contactar a Allen Beachich (
clasificación ABC ) y Jason Morrison (
clasificación J ), pero el resultado fue el mismo que si escribiera en Sportloto.
UPD Martin Farah-Colton me respondió que nunca hicieron la implementación:Me temo que nunca implementamos esos algoritmos.
Lo principal es la idea :)Características del algoritmo
Referencias
Ordenación de la biblioteca
Visualización del algoritmo de ordenación de biblioteca
El orden de inserción es O (n log n)Autores del algoritmo:
Michael A. Bender
Martin Farah-Colton
Miguel Mostiro
Artículos de la serie:
Ordenar agregado a AlgoLab. Para que pueda experimentar con pequeños conjuntos de datos.
En este caso, puede decidir cuántas veces la matriz auxiliar es más grande que la principal. Para seleccionar el coeficiente ε, puede hacer clic con el botón derecho en la celda con “Clasificación de biblioteca” y seleccionar “Cambiar nota”. Y en la nota, establezca cuidadosamente el valor entero para e de 2 a 5. Si ingresa algo más en lugar de estos números, se usará el valor predeterminado = 2.
También puede seleccionar el tipo de reequilibrio. Si establece local = 1, se utilizará el reequilibrio local. Si local = 0 - lleno.
Y no olvide establecer la escala óptima para la hoja de proceso antes de comenzar la visualización, de lo contrario, la matriz auxiliar no se ajustará en la pantalla.