La ordenación por inserción con huecos o por biblioteca es un algoritmo de ordenación que utiliza una ordenación por inserción , pero con huecos en la matriz para acelerar las inserciones posteriores. El nombre proviene de una analogía:
Supongamos que un bibliotecario tuviera que almacenar sus libros en orden alfabético en un estante largo, comenzando con las letras A en el extremo izquierdo y continuando hacia la derecha a lo largo del estante sin espacios entre los libros hasta el final de las letras Z. Si el bibliotecario adquiriera un libro nuevo que pertenece a la sección B, una vez que encuentre el espacio correcto en la sección B, tendrá que mover todos los libros, desde el medio de las letras B hasta las letras Z para hacer lugar para el nuevo libro. Se trata de una ordenación por inserción. Sin embargo, si tuviera que dejar un espacio después de cada letra, siempre que todavía hubiera espacio después de la letra B, solo tendría que mover unos pocos libros para hacer lugar para el nuevo. Este es el principio básico de la ordenación de bibliotecas.
El algoritmo fue propuesto por Michael A. Bender , Martín Farach-Colton y Miguel Mosteiro en 2004 [1] y fue publicado en 2006. [2]
Al igual que el ordenamiento por inserción en el que se basa, el ordenamiento por biblioteca es un ordenamiento por comparación ; sin embargo, se ha demostrado que tiene una alta probabilidad de ejecutarse en un tiempo O(n log n) (comparable al ordenamiento rápido ), en lugar del O(n 2 ) de un ordenamiento por inserción. En el artículo no se proporciona una implementación completa, ni los algoritmos exactos de partes importantes, como la inserción y el reequilibrio. Se necesitaría más información para analizar cómo se compara la eficiencia del ordenamiento por biblioteca con la de otros métodos de ordenamiento en la realidad.
En comparación con la ordenación por inserción básica, la desventaja de la ordenación por biblioteca es que requiere espacio adicional para los espacios vacíos. La cantidad y distribución de ese espacio dependería de la implementación. En el artículo, el tamaño de la matriz necesaria es (1 + ε)n , [2] pero no hay más recomendaciones sobre cómo elegir ε. Además, no es ni adaptativo ni estable. Para garantizar los límites de tiempo de alta probabilidad, debe permutar aleatoriamente la entrada, lo que cambia el orden relativo de los elementos iguales y baraja cualquier entrada preclasificada. Además, el algoritmo utiliza la búsqueda binaria para encontrar el punto de inserción de cada elemento, lo que no aprovecha la entrada preclasificada.
Otro inconveniente es que no se puede ejecutar como un algoritmo en línea , porque no es posible mezclar aleatoriamente la entrada. Si se utiliza sin esta mezcla, podría degenerar fácilmente en un comportamiento cuadrático.
Una debilidad del ordenamiento por inserción es que puede requerir una gran cantidad de operaciones de intercambio y ser costoso si la escritura en la memoria es costosa. El ordenamiento por biblioteca puede mejorar esto un poco en el paso de inserción, ya que se necesitan mover menos elementos para hacer espacio, pero también agrega un costo adicional en el paso de reequilibrio. Además, la localidad de referencia será deficiente en comparación con el ordenamiento por combinación , ya que cada inserción de un conjunto de datos aleatorio puede acceder a la memoria que ya no está en la memoria caché, especialmente con conjuntos de datos grandes.
Digamos que tenemos una matriz de n elementos. Elegimos el espacio que queremos dejar. Entonces tendríamos una matriz final de tamaño (1 + ε)n. El algoritmo funciona en log n rondas. En cada ronda insertamos tantos elementos como ya haya en la matriz final, antes de reequilibrar la matriz. Para encontrar la posición de inserción, aplicamos la búsqueda binaria en la matriz final y luego intercambiamos los siguientes elementos hasta que llegamos a un espacio vacío. Una vez que termina la ronda, reequilibramos la matriz final insertando espacios entre cada elemento.
A continuación se presentan tres pasos importantes del algoritmo:
El procedimiento rebalance(A, begin, end) es r ← fin w ← fin × 2 mientras r ≥ empezar hacer A[w] ← A[r] A[w-1] ← brecha r ← r − 1 y ← y − 2
El procedimiento sort(A) es n ← longitud(A) S ← nueva matriz de n huecos para i ← 1 a floor(log2(n-1)) hacer reequilibrar(S, 1, 2^(i-1))) para j ← 2^(i-1) a 2^i hacer ins ← búsqueda binaria(A[j], S, 2^i) Insertar A[j] en S[ins]
Aquí, binarysearch(el, A, k)se realiza una búsqueda binaria en los primeros k elementos de A , omitiendo los espacios vacíos, para encontrar un lugar donde ubicar el elemento el . La inserción debe favorecer los espacios vacíos sobre los elementos llenos.