Library sort

Library sort es un algoritmo de ordenación que usa ordenación por inserción, pero con espacios vacíos en el arreglo para acelerar inserciones subsiguientes. El nombre proviene de una analogía:

Suponga que un bibliotecario almacene sus libros alfabéticamente en una estante, empezando por la A desde la izquierda, y continuando a la derecha a lo largo del estante sin espacios entre los libros hasta que termine por la Z. Si el bibliotecario adquiere un libro nuevo que pertenece a la sección B, una vez que encuentra el espacio correcto en la sección B, tiene que mover cada libro a partir de ese hasta el último libro en la sección Z para abrir espacio al libro nuevo. Esto es ordenación por inserción. Sin embargo, si dejara un espacio vacío después de cada letra, mientras hubiera un espacio vacío después de B, sólo tendría que mover unos cuantos libros para poder ubicar el nuevo libro. Esto es el principio básico de Library Sort.

El algoritmo estuvo propuesto por Michael Un. Bender, Martín Farach-Colton, y Miguel Mosteiro en 2004 y estuvo publicado en 2006.​​

Como la ordenación por inserción, Library sort es un algoritmo de ordenamiento por comparación estable y puede ser corrido como un algoritmo en línea; aun así, ha mostrado tener una probabilidad alta de correr en un tiempo O(n log n) (comparable a quicksort), mejor que el tiempo de ordenación por inserción O(n2). El mecanismo utilizado para esta mejora es muy similar a aquello de un skip list.No hay una implementación completa escrita, ni los algoritmos exactos de partes importantes, como la inserción y el re-equilibrio. Sería necesaria más información para discutir cómo la eficiencia de Library sort se compara con otros métodos de ordenamiento en realidad.

Comparado a la ordenación por inserción básica, la desventaja de Library sort es que requiere espacio extra para los espacios vacíos. La cantidad y la distribución del espacio extra depende de la implementación. En principio, la medida del arreglo necesitada es (1 + ε)n, pero sin recomendaciones de cómo escoger ε.​

Una debilidad de ordenación por inserción es que puede requerir un número alto de operaciones de intercambio y ser costoso si la memoria de escritura es costosa. Library sort puede mejorar un poco en el paso de inserción, mientras necesite mover menos elementos para abrir el espacio, pero también está añadiendo un sobrecosto en el paso de re-equilibrio. Además, la ubicación de las referencias será pobre comparado a mergesort ya que cada inserción de un conjunto de datos aleatorio puede acceder a memoria que ya no está en la caché, especialmente con conjuntos de datos grande.

Implementación

Algoritmo

Tenemos una arreglo de n elementos. Escogemos el tamaño de espacio vacío que pretendemos dar. Entonces tendríamos una arreglo de medida (1 + ε)n. El algoritmo trabaja en log n rondas. En cada ronda insertamos tantos elementos como hayan, en el arreglo, antes del re-equilibrio de este. Para encontrar la posición donde insertar, aplicamos Búsqueda Binaria en el arreglo y entonces intercambiamos los elementos siguientes hasta que damos con un espacio vacío. Una vez la ronda terminada, nosotros balanceamos el arreglo insertando espacios entre cada elemento.

Siguiendo los tres pasos importantes del algoritmo:

1. Búsqueda binaria: Encontrando la posición de inserción aplicando búsqueda binaria dentro de los elementos ya insertados. Esto puede ser hecho moviéndose por las partes izquierda o derecha de forma recursiva y viendo si encontramos un espacio vacío en el medio.

2. Inserción: Insertando el elemento en la posición encontrada e intercambiando los elementos siguientes 1 por 1 hasta que choquemos con un espacio vacío.

3. Re-Equilibrando: Insertando espacios entre cada par de elementos en el arreglo. Esto toma tiempo lineal, y producto que hay log n rondas en el algoritmo, el re-equilibrio total toma O(n logn).

Pseudocódigo

proc rebalance(A, begin, end)
    r ← end
    w ← end * 2
    while r >= begin
        A[w+1] ← gap
        A[w] ← A[r]
        r ← r - 1
        w ← w - 2

proc sort(A)
    n ← length(A)
    S ← new array of n gaps
    for i ← 1 to floor(log2(n) + 1)
        for j ← 2^i to 2^(i+1)
            ins ← binarysearch(A[j], S, 2^(i-1))
            insert A[j] at S[ins]

Aquí, binarysearch(A, k) efectua búsqueda binaria en los primeros k elementos de A de la ubicación donde se insertará el elemento A[j], saltándose los vacíos. La inserción tendría que favorecer los vacíos sobre los ocupados.

Enlaces externos

• Gapped Insertion Sort[1]

• Datos: Q3495147