Splaysort

En ciencias de la computación , splaysort es un algoritmo de ordenación por comparación adaptativo basado en la estructura de datos de árbol splay . ^{[ 1 ]}

Los pasos del algoritmo son:

1. Inicializa un árbol splay vacío
2. Para cada elemento de datos en el orden de entrada, insértelo en el árbol splay.
3. Recorre el árbol splay para encontrar el orden ordenado de los datos.

Por lo tanto, el algoritmo puede considerarse una forma de ordenación por inserción o de ordenación por árbol , que utiliza un árbol splay para acelerar cada inserción.

Basándonos en el análisis amortizado de los árboles splay, el tiempo de ejecución en el peor de los casos de splaysort, en una entrada con n elementos de datos, es O ( n  log n ), lo que coincide con los límites de tiempo de algoritmos no adaptativos eficientes como quicksort , heap sort y merge sort . 

Para una secuencia de entrada en la que la mayoría de los elementos se colocan cerca de su predecesor en el orden ordenado, o están fuera de orden con solo un pequeño número de otros elementos, splaysort puede ser más rápido que O ( n  log n ), lo que demuestra que es un ordenamiento adaptativo . Para cuantificar esto, sea d _x el número de posiciones en la entrada que separan a x de su predecesor, y sea i _x el número de elementos que aparecen a un lado de x en la entrada y al otro lado de x en la salida (el número de inversiones que involucran a x ). Entonces, del teorema del dedo dinámico para árboles splay se deduce que el tiempo total para splaysort está acotado por 

${\displaystyle \sum _{x}\log d_{x}}$

y por

${\displaystyle \sum _{x}\log i_{x}}$. ^{[ 2 ]}

También se puede demostrar que Splaysort se adapta a la entropía de la secuencia de entrada. ^{[ 3 ]}

En experimentos realizados por Moffat, Eddy y Petersson (1996) , splaysort fue entre 1,5 y 2 veces más lento que quicksort en tablas de números aleatorios, y por factores menores que mergesort. Para datos que consistían en registros más grandes, también en orden aleatorio, la cantidad adicional de movimiento de datos realizada por quicksort lo ralentizó significativamente en comparación con los algoritmos basados ​​en punteros, y los tiempos de splaysort y mergesort fueron muy similares. Sin embargo, para secuencias de entrada casi preordenadas (medidas en términos del número de subsecuencias monótonas contiguas en los datos, el número de inversiones, el número de elementos que deben eliminarse para formar una subsecuencia ordenada o el número de subsecuencias monótonas no contiguas en las que se puede particionar la entrada), splaysort se volvió significativamente más eficiente que los otros algoritmos. ^{[ 1 ]}

Elmasry y Hammad (2005) compararon splaysort con varios otros algoritmos que se adaptan al número total de inversiones en la entrada, así como con quicksort. Descubrieron que, en las entradas que tenían pocas inversiones como para que un algoritmo adaptativo fuera más rápido que quicksort, splaysort era el algoritmo más rápido. ^{[ 4 ]}

Saikkonen y Soisalon-Soininen (2012) modifican splaysort para que sea más adaptable al número de subsecuencias monótonas contiguas en la entrada, e informan sobre experimentos que muestran que el algoritmo resultante es más rápido en entradas que están casi preordenadas según esta medida. ^{[ 5 ]}