Ordenación adaptativa - Adaptive sort

Un algoritmo de clasificación entra en la familia de clasificación adaptativa si aprovecha el orden existente en su entrada. Se beneficia de la clasificación previa en la secuencia de entrada - o una cantidad limitada de desorden para varias definiciones de medidas de desorden - y ordena más rápido. La clasificación adaptativa se realiza normalmente modificando los algoritmos de clasificación existentes.

Motivación

Los algoritmos de clasificación basados ​​en la comparación tradicionalmente se han ocupado de lograr un límite óptimo de O ( n log n ) cuando se trata de la complejidad del tiempo . La ordenación adaptativa aprovecha el orden existente de la entrada para tratar de lograr mejores tiempos, de modo que el tiempo que tarda el algoritmo en ordenar sea una función de crecimiento suave del tamaño de la secuencia y el desorden en la secuencia. En otras palabras, cuanto más preclasificada esté la entrada, más rápido se debería ordenar.

Este es un algoritmo atractivo porque las secuencias casi ordenadas son comunes en la práctica. Por lo tanto, el rendimiento de los algoritmos de clasificación existentes se puede mejorar teniendo en cuenta el orden existente en la entrada.

Tenga en cuenta que la mayoría de los algoritmos de clasificación en el peor de los casos que funcionan de manera óptima en el peor de los casos, en particular la clasificación por pila y la clasificación por combinación , no tienen en cuenta el orden existente dentro de su entrada, aunque esta deficiencia se corrige fácilmente en el caso de la clasificación por combinación al verificar 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 fusión puede ser reemplazada por una simple concatenación, una modificación que está dentro del alcance de hacer que un algoritmo sea adaptable .

Ejemplos

Un ejemplo clásico de un algoritmo de ordenación adaptativa es la ordenación por inserción directa . En este algoritmo de clasificación, escaneamos la entrada de izquierda a derecha, encontrando repetidamente la posición del elemento actual y la insertamos en una matriz de elementos previamente ordenados.

En forma de pseudocódigo , el algoritmo de ordenación por inserción directa podría verse así (la matriz X está basada en cero): 

procedure Straight Insertion Sort (X):
    for j := 1 to length(X) - 1 do
        t := X[j]
        i := j
        while i > 0 and X[i - 1] > t do
            X[i] := X[i - 1]
            i := i - 1
        end
        X[i] := t
    end

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 (en relación con el número de inversiones), la clasificación por inserción directa lleva menos tiempo para clasificar cuanto más cerca está de ser clasificada.

Otros ejemplos de algoritmos de clasificación adaptativa son la clasificación de pila adaptativa , la clasificación de fusión adaptativa , la clasificación de paciencia , Shellsort , smoothsort , splaysort y Timsort .

Ver también

Referencias

  • Hagerup, Torben; Jyrki Katjainen (2004). Teoría de algoritmos - SWAT 2004 . Berlín Heidelberg: Springer-Verlag. págs. 221–222. ISBN   3-540-22339-8 .
  • Mehta, Dinesh P .; Sartaj Sahni (2005). Estructuras de datos y aplicaciones . Estados Unidos: Chapman & Hall / CRC. págs. 11‑8–11‑9. ISBN   1-58488-435-5 .
  • Estivill-Castro, Vladmir; Wood, Derick (diciembre de 1992). "Una encuesta de algoritmos de clasificación adaptativos". ACM . Nueva York, NY, Estados Unidos. 24 (4): 441–476. CiteSeerX   10.1.1.45.8017 . doi : 10.1145 / 146370.146381 . ISSN   0360-0300 . S2CID   1540978 .
  • Petersson, Ola; Alistair Moffat (1992). "Un marco para la clasificación adaptativa". Apuntes de conferencias en informática. 621 . Berlín: Springer Berlin / Heidelberg: 422–433. doi : 10.1007 / 3-540-55706-7_38 . ISBN   978-3-540-55706-7 . ISSN   1611-3349 . Citar diario requiere |journal= ( ayuda )