Usuario:Maaster9/Taller

En computación, Smoothsort es un algoritmo de algoritmo de ordenamiento basado en comparación. Una variante de heapsort, fue inventado y publicado por Edsger Dijkstra en 1981. Como heapsort, smoothsort es un algoritmo in-place con un límite superior de O(n log n) operaciones (ver notación big O),​ pero no es una ordenación estable.​​ La ventaja de smoothsort es que se acerca más a O(n) tiempo si la entrada ya está ordenada en cierto grado, mientras que heapsort promedia O(n' log n) independientemente del estado inicial ordenado.

Descripción general

Al igual que heapsort, smoothsort organiza la entrada en una cola de prioridad y luego extrae repetidamente el máximo. También como heapsort, la cola de prioridad es una estructura de datos implicita de montón (un heap-ordenado implícito árbol binario), que ocupa un prefijo del array. Cada extracción reduce el prefijo y añade el elemento extraído a un sufijo ordenado creciente. Cuando el prefijo se ha reducido a nada, la matriz está completamente ordenada.

Heapsort asigna el árbol binario a la matriz utilizando un recorrido de arriba hacia abajo del árbol; la matriz comienza con la raíz del árbol, luego sus dos hijos, luego cuatro nietos, y así sucesivamente. Cada elemento tiene una profundidad bien definida por debajo de la raíz del árbol, y cada elemento excepto la raíz tiene su padre antes en la matriz. Sin embargo, su altura sobre las hojas depende del tamaño de la matriz. Esto tiene la desventaja de que cada elemento debe moverse como parte del proceso de ordenación: debe pasar por la raíz antes de ser movido a su ubicación final.

Smoothsort utiliza un mapeo diferente, un recorrido post-orden de abajo a arriba. Un hijo izquierdo es seguido por el subárbol enraizado en su hermano, y un hijo derecho es seguido por su padre. Cada elemento tiene una altura bien definida por encima de las hojas, y cada elemento no hoja tiene sus hijos antes en el array. Su profundidad por debajo de la raíz, sin embargo, depende del tamaño del array. El algoritmo está organizado de forma que la raíz se encuentra al final del montón, y en el momento en que un elemento se extrae del montón ya se encuentra en su ubicación final y no es necesario moverlo. Además, un array ordenado ya es un montón válido, y muchos intervalos ordenados son subárboles válidos ordenados en el montón.

Más formalmente, cada posición i es la raíz de un único subárbol, cuyos nodos ocupan un intervalo contiguo que termina en i. Un prefijo inicial de la matriz (incluida toda la matriz), podría ser un intervalo de este tipo correspondiente a un subárbol, pero en general se descompone como la unión de varios intervalos sucesivos de subárboles de este tipo, que Dijkstra denomina "tramos". Todo subárbol sin padre (es decir, arraigado en una posición cuyo padre se encuentra más allá del prefijo considerado) da un tramo en la descomposición de ese intervalo, cuya descomposición es, por tanto, única. Cuando se añade un nuevo nodo al prefijo, se produce uno de estos dos casos: o bien la posición es una hoja y añade un tramo de longitud 1 a la descomposición, o bien se combina con los dos últimos tramos, convirtiéndose en el padre de sus respectivas raíces, sustituyendo así los dos tramos por un nuevo tramo que contiene su unión más la nueva posición (raíz).

Dijkstra observó que la regla obvia sería combinar tramos si y sólo si tienen el mismo tamaño, en cuyo caso todos los subárboles serían árboles binarios perfectos de tamaño 2^k-1. Sin embargo, eligió una regla diferente, que da más tamaños de árbol posibles. Esto tiene el mismo eficiencia asintótica,​ pero gana un pequeño factor constante en eficiencia al requerir menos tramos para cubrir cada intervalo.

La regla que usa Dijkstra es que los dos últimos tramos se combinan si y sólo si sus tamaños son números Leonardos consecutivos L(i+1)} y L(i) (en ese orden), cuyos números se definen recursivamente, de forma muy similar a los números Fibonaccis, como:

• L(0) = L(1) = 1}}
• L(k+2) = L(k+1) + L(k) + 1

En consecuencia, el tamaño de cualquier subárbol es un número Leonardo. La secuencia de tamaños de tramos que descomponen las primeras n posiciones, para cualquier n, puede hallarse de forma codiciosa: el primer tamaño es el mayor número Leonardo que no exceda de n, y el resto (si lo hay) se descompone recursivamente. Los tamaños de los tramos son decrecientes, de forma estricta salvo posiblemente para dos tamaños finales 1, y evitando números Leonardo sucesivos salvo posiblemente para los dos tamaños finales.

Además de que cada tramo es un árbol ordenado en el montón, las raíces de los árboles se mantienen ordenadas. De este modo, se añade un tercer hijo (que Dijkstra denomina "hijastro") a cada raíz, vinculándolo a la raíz anterior. De este modo, todos los árboles se combinan en un montón global, con el máximo global al final.

Aunque la ubicación del hijastro de cada nodo es fija, el enlace sólo existe para las raíces de los árboles, lo que significa que los enlaces se eliminan cada vez que se fusionan los árboles. Esto difiere de los hijos ordinarios, que están vinculados mientras exista el padre.

En la primera fase (de crecimiento del montón) de la ordenación, una parte inicial cada vez más grande del array se reorganiza de forma que el subárbol de cada uno de sus tramos sea un max-heap: la entrada en cualquier posición no hoja es al menos tan grande como las entradas en las posiciones que son sus hijos. Además, todas las raíces son al menos tan grandes como sus hijastros.

En la segunda fase (de reducción del montón), el nodo máximo se separa del final del conjunto (sin necesidad de moverlo) y se restablecen las invariantes del montón entre sus hijos. (En concreto, entre los hijastros recién creados).

En la práctica, a menudo es necesario calcular los números de Leonardo L(k). Dijkstra proporciona un código inteligente que utiliza un número fijo de variables enteras para calcular eficientemente los valores necesarios en el momento en que se necesitan. Alternativamente, si hay un límite finito N en el tamaño de las matrices a ordenar, una tabla precalculada de números Leonardo puede ser almacenada en O(log N) espacio.

Operaciones

Aunque las dos fases del procedimiento de ordenación son opuestas entre sí en lo que respecta a la evolución de la estructura de secuencias de montones, se implementan utilizando una primitiva central, equivalente a la operación "en un max-heap binario.

Clasificación descendente

La operación de barrido hacia abajo (que Dijkstra llama "trinkle") restaura la invariante del montón cuando es posible que sólo se viole en el nodo raíz. Si el nodo raíz es menor que cualquiera de sus hijos, se intercambia con su hijo mayor y se repite el proceso con el nodo raíz en su nuevo subárbol.

La diferencia entre smoothsort y un max-heap binario es que la raíz de cada tramo debe ordenarse con respecto a un tercer "hijastro": la raíz del tramo precedente. Por lo tanto, el procedimiento de tamizado hacia abajo comienza con una serie de comparaciones de cuatro vías (el nodo raíz y tres hijos) hasta que el hijastro no es el elemento máximo, luego una serie de comparaciones de tres vías (la raíz más dos hijos) hasta que el nodo raíz encuentra su hogar final y se restablecen los invariantes.

Cada árbol es un árbol binario completo: cada nodo tiene dos hijos o ninguno. No es necesario tratar el caso especial de un hijo que se da en un montón binario implícito estándar. (Pero el caso especial de los enlaces hijastro compensa con creces este ahorro).

Debido a que hay O(log n) tramos, cada uno de los cuales es un árbol de profundidad O(log n), el tiempo para realizar cada operación de tamizado hacia abajo está limitado por O(log n).

Crecimiento de la región del montón incorporando un elemento a la derecha

Cuando se considera la incorporación de un elemento adicional a la secuencia de tramos (lista de estructuras de montón disjuntas), o bien forma un nuevo tramo de un elemento, o bien combina los dos tramos situados más a la derecha convirtiéndose en el padre de las raíces de ambos y formando un nuevo tramo que sustituye a los dos en la secuencia. Cuál de los dos sucede depende sólo de los tamaños de los tramos actualmente presentes (y en última instancia sólo en el índice del elemento añadido); Dijkstra estipuló que los tramos se combinan si y sólo si sus tamaños son L(k+1) y L(k) para algunos k, es decir, números Leonardo consecutivos; el nuevo tramo tendrá tamaño L(k+2).

En cualquier caso, el nuevo elemento debe ser tamizado hasta su lugar correcto en la estructura del montón. Incluso si el nuevo nodo es un tramo de un elemento, todavía debe ser ordenado en relación con la raíz del tramo anterior.

Optimización

El algoritmo de Dijkstra ahorra trabajo al observar que la invariante completa del montón es necesaria al final de la fase de crecimiento, pero no lo es en cada paso intermedio. En concreto, el requisito de que un elemento sea mayor que su hijastro sólo es importante para los elementos que son las raíces finales del árbol.

Por lo tanto, cuando se añade un elemento, se calcula la posición de su futuro padre. Si está dentro del rango de valores restantes a ordenar, actúa como si no hubiera hijastro y sólo tamiza hacia abajo dentro del árbol actual.

Reducir la región del montón separando el elemento más a la derecha de este

Durante esta fase, la forma de la secuencia de tramos pasa por los cambios de la fase de crecimiento a la inversa. No es necesario hacer nada cuando se separa un nodo hoja, pero para un nodo no hoja sus dos hijos se convierten en raíces de nuevos tramos, y necesitan ser movidos a su lugar apropiado en la secuencia de raíces de tramos. Esto puede conseguirse aplicando dos veces la criba descendente: primero para el hijo izquierdo y luego para el hijo derecho (cuyo hijastro era el hijo izquierdo).

Dado que la mitad de todos los nodos de un árbol binario completo son hojas, esto realiza una media de una operación de tamizado hacia abajo por nodo.

Optimización

Se sabe que las raíces recién expuestas están correctamente ordenadas con respecto a sus hijos normales; lo que está en duda es la forma en que están ordenadas con respecto a sus hijastros. Por lo tanto, mientras se reduce el montón, el primer paso de la criba hacia abajo se puede simplificar a una sola comparación con el hijastro. Si se produce un intercambio, los pasos siguientes deben hacer la comparación completa de cuatro vías.

Análisis

Smoothsort tarda O(n) en procesar un array preclasificado, O(n log  n) en el peor de los casos, y alcanza un rendimiento casi lineal en muchas entradas casi-clasificadas. Sin embargo, no maneja todas las secuencias casi ordenadas de forma óptima. Empleando el recuento de inversiones como medida de falta de ordenación (el número de pares de índices i} y j con i < j} y A[i] > A[j]}; para una entrada ordenada aleatoriamente es aproximadamente n²/4), hay posibles secuencias de entrada con O(n log  n) inversiones que hacen que tarde Ω(n log n) tiempo, mientras que otros algoritmos de ordenación adaptativa pueden resolver estos casos en O(n log log n) tiempo. ​

El algoritmo smoothsort necesita ser capaz de mantener en memoria los tamaños de todos los árboles del montón Leonardo. Como están ordenados por orden y todos los órdenes son distintos, esto se suele hacer usando un vector de bits que indica qué órdenes están presentes. Además, como el orden más grande es como máximo O(log n), estos bits pueden codificarse en O(1) palabras máquina, suponiendo un modelo máquina transdichotómico.

Hay que tener en cuenta que O(1) palabras máquina no es lo mismo que una palabra máquina. Un vector de 32 bits sólo sería suficiente para tamaños inferiores a L(32) = 7049155. Un vector de 64 bits será suficiente para tamaños inferiores a L(64) = 34335360355129 ≈ 2⁴⁵. En general, se necesitan 1/log₂(φ) ≈ 1,44 bits de vector por bit de tamaño.

Ordenamiento Poplar

Un algoritmo más sencillo inspirado en smoothsort es poplar sort.​ Llamado así por las filas de árboles de tamaño decreciente que se ven a menudo en los pólders holandeses, realiza menos comparaciones que smoothsort para entradas que no están mayoritariamente ordenadas, pero no puede alcanzar un tiempo lineal para entradas ordenadas.

El cambio significativo realizado por poplar sort es que las raíces de los distintos árboles "no" se mantienen ordenadas; no hay enlaces "hijastros" que las unan en un único montón. En su lugar, cada vez que el montón se reduce en la segunda fase, las raíces se buscan para encontrar la entrada máxima.

Debido a que hay n pasos de encogimiento, cada uno de los cuales debe buscar O(log n) raíces de árbol para el máximo, el tiempo de ejecución en el mejor de los casos para la ordenación de álamo es O(n' log n).

Los autores también sugieren el uso de árboles binarios perfectos en lugar de árboles Leonardo para proporcionar una mayor simplificación, pero este es un cambio menos significativo.

La misma estructura se ha propuesto como una cola de prioridad de propósito general bajo el nombre de montón post-orden,​ consiguiendo O(1) amortizado tiempo de inserción en una estructura más simple que un montón binomial implícito.

Aplicaciones

La biblioteca de C musl utiliza smoothsort para su implementación de qsort().​​

Enlaces externos

• Transcripción comentada de EWD796a, 16-Ago-1981
• Explicación moderna detallada de Smoothsort
• wikibooks:Algorithm Implementation/Sorting/Smoothsort
• Descripción y ejemplo de implementación de Poplar heap
• Noshita, Kohei; Nakatani, Yoshinobu (Abril 1985). «Sobre la estructura de montón anidado en Smoothsort». Fundamentos matemáticos de la informática y sus aplicaciones (数理解析研究所講究録, Fundamentos matemáticos de la informática y sus aplicaciones^?) 556: 1–16.