Clasificación de la biblioteca , o inserción gapped tipo es un algoritmo de clasificación que utiliza una ordenación por inserción , pero con vacíos en la matriz para acelerar inserciones subsiguientes. El nombre proviene de una analogía:
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | |
Rendimiento medio | |
Complejidad espacial en el peor de los casos |
Suponga que un bibliotecario almacenara sus libros alfabéticamente en un estante largo, comenzando con la As en el extremo izquierdo y continuando hacia la derecha a lo largo del estante sin espacios entre los libros hasta el final de la Z. Si el bibliotecario adquirió 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 la mitad de las B hasta las Zs para poder Haga espacio para el nuevo libro. Este es un tipo de inserción. Sin embargo, si dejara un espacio después de cada letra, siempre y cuando todavía hubiera espacio después de B, solo tendría que mover algunos libros para dejar espacio para el nuevo. Este es el principio básico de la clasificació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 orden de inserción en el que se basa, el orden de biblioteca es un orden de comparación ; sin embargo, se demostró que tiene una alta probabilidad de ejecutarse en el tiempo O (n log n) (comparable a la clasificación rápida ), en lugar de una clasificación de inserción O (n 2 ). No se proporciona una implementación completa en el documento, ni los algoritmos exactos de partes importantes, como la inserción y el reequilibrio. Se necesitaría más información para discutir cómo la eficiencia de la clasificación de bibliotecas se compara con la de otros métodos de clasificación en la realidad.
En comparación con el ordenamiento por inserción básico, el inconveniente del ordenamiento por biblioteca es que requiere espacio adicional para los huecos. La cantidad y distribución de ese espacio dependería de la implementación. En el documento, el tamaño de la matriz necesaria es (1 + ε) n , [2] pero sin más recomendaciones sobre cómo elegir ε. Además, no es ni adaptable ni estable. Para garantizar los límites de tiempo con alta probabilidad, se requiere permutar aleatoriamente la entrada, lo que cambia el orden relativo de elementos iguales y baraja cualquier entrada preclasificada. Además, el algoritmo utiliza una búsqueda binaria para encontrar el punto de inserción de cada elemento, lo que no aprovecha la entrada clasificada previamente.
Otro inconveniente es que no se puede ejecutar como un algoritmo en línea , porque no es posible mezclar aleatoriamente la entrada. Si se usa sin esta mezcla, podría degenerar fácilmente en un comportamiento cuadrático.
Una debilidad de la ordenación por inserción es que puede requerir una gran cantidad de operaciones de intercambio y ser costosa si la escritura en memoria es costosa. La clasificación de bibliotecas puede mejorar eso un poco en el paso de inserción, ya que es necesario 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 mergesort, ya que cada inserción de un conjunto de datos aleatorios puede acceder a la memoria que ya no está en la caché, especialmente con conjuntos de datos grandes.
Implementación
Algoritmo
Digamos que tenemos una matriz de n elementos. Elegimos el hueco que pretendemos dar. 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 lleguemos a un espacio vacío. Una vez que termina la ronda, reequilibramos la matriz final insertando espacios entre cada elemento.
A continuación se muestran tres pasos importantes del algoritmo:
- Búsqueda binaria : Encontrar la posición de inserción aplicando búsqueda binaria dentro de los elementos ya insertados. Esto se puede hacer moviéndose linealmente hacia el lado izquierdo o derecho de la matriz si golpea un espacio vacío en el elemento del medio.
- Inserción : Insertando el elemento en la posición encontrada e intercambiando los siguientes elementos por 1 posición hasta que se golpee un espacio vacío. Esto se hace en tiempo logarítmico, con alta probabilidad.
- Reequilibrio : Insertar espacios entre cada par de elementos en la matriz. El costo del reequilibrio es lineal en el número de elementos ya insertados. A medida que estas longitudes aumentan con las potencias de 2 para cada ronda, el costo total del reequilibrio también es lineal.
Pseudocódigo
el reequilibrio del procedimiento (A, begin, end) es r ← fin w ← fin ÷ 2 mientras r ≥ comenzar a hacer A [w + 1] ← espacio A [w] ← A [r] r ← r - 1 w ← w - 2
el tipo de procedimiento (A) es n ← longitud (A) S ← nueva matriz de n espacios para i ← 1 al piso (log2 (n) + 1) hacer para j ← 2 ^ i a 2 ^ (i + 1) hacer ins ← binarysearch (A [j], S, 2 ^ (i - 1)) inserte A [j] en S [ins]
Aquí, binarysearch(el, A, k)
realiza una búsqueda binaria en los primeros k elementos de A , saltándose los huecos, para encontrar un lugar donde ubicar el elemento el . La inserción debe favorecer los huecos sobre los elementos rellenados.
Referencias
- ^ Bender, Michael A .; Farach-Colton, Martín ; Mosteiro, Miguel A. (1 de julio de 2004). "El orden de inserción es O (n log n)". arXiv : cs / 0407003 .
- ^ a b Bender, Michael A .; Farach-Colton, Martín ; Mosteiro, Miguel A. (junio de 2006). "La clasificación por inserción es O (n log n)" (PDF) . Teoría de los sistemas informáticos . 39 (3): 391–397. arXiv : cs / 0407003 . doi : 10.1007 / s00224-005-1237-z . Archivado desde el original (PDF) el 8 de septiembre de 2017 . Consultado el 7 de septiembre de 2017 .