Un algoritmo de clasificación pertenece a la familia de clasificació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 clasificación adaptativa generalmente se realiza modificando los algoritmos de clasificación existentes.
Los algoritmos de clasificación basados en comparaciones se han ocupado tradicionalmente de lograr un límite óptimo de O ( n log n ) cuando se trata de complejidad temporal . La clasificación adaptativa 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 que crece suavemente 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á ordenarse.
Esta es una característica atractiva para un algoritmo de clasificación porque las secuencias casi ordenadas son comunes en la práctica. Por tanto, el rendimiento de los algoritmos de clasificación existentes se puede mejorar teniendo en cuenta el orden existente en la entrada.
La mayoría de los algoritmos de clasificación en el peor de los casos que funcionan óptimamente en el peor de los casos, en particular la clasificación en montón y la clasificación por combinación , no tienen en cuenta el orden existente dentro de sus entradas, aunque esta deficiencia se rectifica fácilmente en el caso de la ordenación por fusión comprobando si el 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 fusión puede ser reemplazada por una simple concatenación, una modificación que está dentro del alcance de hacer que un algoritmo sea adaptativo. .
Un ejemplo clásico de algoritmo de clasificación adaptativo es la clasificación por inserción . [1] En este algoritmo de clasificación, la entrada se escanea de izquierda a derecha, buscando 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 ordenación por inserción (la matriz X tiene base cero ):
procedimiento Ordenación 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 hacer X[yo] ← X[yo - 1] yo ← yo - 1 fin X[yo] ← t fin
El rendimiento de este algoritmo se puede describir en términos del número de inversiones en la entrada, y luego será aproximadamente igual a , donde es el número de inversiones. Al utilizar esta medida de clasificación previa (relativa al número de inversiones), la ordenación por inserción requiere menos tiempo para ordenar cuanto más cerca esté la matriz de datos de ser ordenada.
Otros ejemplos de algoritmos de clasificación adaptativa son la clasificación de montón adaptativo , la clasificación de fusión adaptativa , la clasificación de paciencia , [2] Shellsort , smoothsort , splaysort , Timsort y la clasificación de árbol cartesiano . [3]
