Un algoritmo de ordenación pertenece a la familia de ordenación adaptativa si aprovecha el orden existente en su entrada. Se beneficia de la preclasificación en la secuencia de entrada (o de una cantidad limitada de desorden para varias definiciones de medidas de desorden) y ordena más rápido. La ordenación adaptativa se realiza generalmente modificando algoritmos de ordenación existentes.
Los algoritmos de ordenamiento basados en comparaciones se han ocupado tradicionalmente de lograr un límite óptimo de O ( n log n ) cuando se trabaja con complejidad temporal . El ordenamiento adaptativo aprovecha el orden existente de la entrada para intentar lograr mejores tiempos, de modo que el tiempo que tarda el algoritmo en ordenar es una función de crecimiento suave del tamaño de la secuencia y del desorden en la secuencia. En otras palabras, cuanto más preordenada esté la entrada, más rápido debería ordenarse.
Esta es una característica atractiva para un algoritmo de ordenamiento porque las secuencias que casi están ordenadas son comunes en la práctica. Por lo tanto, el rendimiento de los algoritmos de ordenamiento existentes se puede mejorar teniendo en cuenta el orden existente en la entrada.
La mayoría de los algoritmos de ordenamiento en el peor de los casos que funcionan óptimamente bien en el peor de los casos, en particular el ordenamiento por montículo y el ordenamiento por combinación , no tienen en cuenta el orden existente dentro de su entrada, aunque esta deficiencia se rectifica fácilmente en el caso del ordenamiento por combinación verificando si el último elemento del grupo de la izquierda es menor (o igual) que el primer elemento del grupo de la derecha, en cuyo caso una operación de combinación puede reemplazarse por una concatenación simple, una modificación que está dentro del alcance de hacer que un algoritmo sea adaptativo.
Un ejemplo clásico de un algoritmo de ordenamiento adaptativo es el ordenamiento por inserción . [1] En este algoritmo de ordenamiento, la entrada se escanea de izquierda a derecha, encontrando repetidamente la posición del elemento actual e insertándolo en una matriz de elementos previamente ordenados.
A continuación se muestra el pseudocódigo para el algoritmo de ordenamiento por inserción (la matriz X está basada en cero ):
procedimiento Ordenamiento por inserción (X): para j = 1 a longitud (X) - 1 hacer t ← X[j] yo ← j mientras i > 0 y X[i - 1] > t lo hacen X[i] ← X[i - 1] yo ← yo - 1 fin X[i] ← t fin
El rendimiento de este algoritmo se puede describir en términos de la cantidad de inversiones en la entrada, y entonces será aproximadamente igual a , donde es la cantidad de inversiones. Al usar esta medida de preclasificación (que es relativa a la cantidad de inversiones), la ordenación por inserción tarda menos tiempo en ordenarse cuanto más cerca esté la matriz de datos de ser ordenada.
Otros ejemplos de algoritmos de ordenamiento adaptativo son el ordenamiento de montón adaptativo , el ordenamiento de combinación adaptativo , el ordenamiento por paciencia , [2] Shellsort , smoothsort , splaysort , Timsort y el ordenamiento de árbol cartesiano . [3]
