En informática , la ordenación por paciencia es un algoritmo de ordenación inspirado en el juego de cartas paciencia , que recibe su nombre en honor a este . Una variante del algoritmo calcula de manera eficiente la longitud de la subsecuencia creciente más larga en una matriz dada .
El nombre del algoritmo deriva de una variante simplificada del juego de cartas de la paciencia. El juego comienza con una baraja de cartas mezclada. Las cartas se reparten una a una en una secuencia de pilas sobre la mesa, de acuerdo con las siguientes reglas. [2]
Este juego de cartas se convierte en un algoritmo de ordenamiento de dos fases, de la siguiente manera. Dado un arreglo de n elementos de un dominio totalmente ordenado , considere este arreglo como una colección de cartas y simule el juego de ordenamiento de paciencia. Cuando el juego termine, recupere la secuencia ordenada seleccionando repetidamente la carta visible mínima; en otras palabras, realice una fusión de k vías de las p pilas, cada una de las cuales está ordenada internamente.
La primera fase de la ordenación por paciencia, la simulación del juego de cartas, se puede implementar para tomar O ( n log n ) comparaciones en el peor de los casos para una matriz de entrada de n elementos: habrá como máximo n pilas y, por construcción, las cartas superiores de las pilas forman una secuencia creciente de izquierda a derecha, por lo que la pila deseada se puede encontrar mediante una búsqueda binaria . [1] La segunda fase, la fusión de pilas, también se puede realizar a tiempo utilizando una cola de prioridad . [1]
Cuando los datos de entrada contienen "ejecuciones" naturales, es decir, submatrices no decrecientes, entonces el rendimiento puede ser estrictamente mejor. De hecho, cuando la matriz de entrada ya está ordenada, todos los valores forman una única pila y ambas fases se ejecutan en tiempo O ( n ) . La complejidad del caso promedio sigue siendo O ( n log n ) : cualquier secuencia de valores uniformemente aleatoria producirá un número esperado de pilas [3] , que tardan tiempo en producirse y fusionarse. [1]
Chandramouli y Goldstein ofrecen una evaluación del rendimiento práctico de la ordenación por paciencia, y demuestran que una versión ingenua es aproximadamente diez a veinte veces más lenta que una ordenación rápida de última generación en su problema de referencia. Atribuyen esto a la relativamente pequeña cantidad de investigación dedicada a la ordenación por paciencia y desarrollan varias optimizaciones que reducen su rendimiento a un factor de dos del de la ordenación rápida. [1]
Si los valores de las cartas están en el rango 1, . . . , n , existe una implementación eficiente con un tiempo de ejecución en el peor de los casos para colocar las cartas en pilas, basándose en un árbol de Van Emde Boas . [3]
La clasificación por paciencia está estrechamente relacionada con un juego de cartas llamado el juego de Floyd. Este juego es muy similar al juego esbozado anteriormente: [2]
El objetivo del juego es terminar con la menor cantidad de montones posible. La diferencia con el algoritmo de clasificación por paciencia es que no existe el requisito de colocar una nueva carta en el montón más a la izquierda, donde está permitido. La clasificación por paciencia constituye una estrategia codiciosa para jugar a este juego.
Aldous y Diaconis sugieren definir 9 pilas o menos como un resultado ganador para n = 52 , lo que ocurre con aproximadamente un 5% de probabilidad. [4]
Primero, ejecute el algoritmo de ordenamiento como se describió anteriormente. El número de pilas es la longitud de la subsecuencia más larga. Siempre que se coloque una carta en la parte superior de una pila, coloque un puntero hacia atrás en la carta superior de la pila anterior (que, por supuesto, tiene un valor menor que el de la nueva carta). Al final, siga los punteros hacia atrás desde la carta superior de la última pila para recuperar una subsecuencia decreciente de la longitud más larga; su reverso es una respuesta al algoritmo de la subsecuencia creciente más larga.
S. Bespamyatnikh y M. Segal [3] describen una implementación eficiente del algoritmo, que no implica ningún costo asintótico adicional con respecto al de ordenamiento (ya que el almacenamiento, la creación y el recorrido de los punteros hacia atrás requieren tiempo y espacio lineales). Además, muestran cómo informar todas las subsecuencias crecientes más largas a partir de las mismas estructuras de datos resultantes .
El ordenamiento por paciencia fue bautizado por CL Mallows, quien atribuyó su invención a ASC Ross a principios de los años 1960. [1] Según Aldous y Diaconis, [4] el ordenamiento por paciencia fue reconocido por primera vez como un algoritmo para calcular la longitud de subsecuencia creciente más larga por Hammersley. [5] ASC Ross e independientemente Robert W. Floyd lo reconocieron como un algoritmo de ordenamiento. El análisis inicial fue realizado por Mallows. [6] El juego de Floyd fue desarrollado por Floyd en correspondencia con Donald Knuth . [2]
El algoritmo de ordenamiento por paciencia se puede aplicar al control de procesos . Dentro de una serie de mediciones, la existencia de una subsecuencia creciente larga se puede utilizar como marcador de tendencia. Un artículo de 2002 en la revista SQL Server incluye una implementación SQL, en este contexto, del algoritmo de ordenamiento por paciencia para la longitud de la subsecuencia creciente más larga. [7]
