Ordenación suave

En informática , smoothsort es un algoritmo de ordenamiento basado en comparación . Una variante de heapsort , fue inventada y publicada por Edsger Dijkstra en 1981. ^[1] Al igual que heapsort, smoothsort es un algoritmo in situ con un límite superior de O ( n log  n ) operaciones (ver notación O grande ), ^[2] pero no es un ordenamiento estable . ^{[3] [ ¿ fuente autopublicada? ] [4]} La ventaja de smoothsort es que se acerca al tiempo O ( n ) si la entrada ya está ordenada hasta cierto punto , mientras que heapsort promedia O ( n log  n ) independientemente del estado ordenado inicial.

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 de montón implícita (un árbol binario implícito ordenado por montón ), que ocupa un prefijo de la matriz. Cada extracción reduce el prefijo y agrega el elemento extraído a un sufijo ordenado en crecimiento. Cuando el prefijo se ha reducido a nada, la matriz está completamente ordenada.

Heapsort asigna el árbol binario a la matriz mediante un recorrido de arriba hacia abajo en amplitud 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 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 de orden posterior de abajo a arriba en profundidad . A un hijo izquierdo le sigue el subárbol con raíz en su hermano, y a un hijo derecho le sigue su padre. Cada elemento tiene una altura bien definida por encima de las hojas, y cada elemento que no es hoja tiene sus hijos antes en la matriz. Sin embargo, su profundidad por debajo de la raíz depende del tamaño de la matriz. El algoritmo está organizado de modo que la raíz esté al final del montón, y en el momento en que se extrae un elemento del montón ya está en su ubicación final y no necesita ser movido. Además, una matriz ordenada ya es un montón válido, y muchos intervalos ordenados son subárboles ordenados por montón válidos.

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

Dijkstra señaló ^[1] que la regla obvia sería combinar estiramientos si y solo 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 árboles posibles. Esto tiene la misma eficiencia asintótica ^[2] , pero gana un pequeño factor constante en eficiencia al requerir menos estiramientos para cubrir cada intervalo.

La regla que utiliza Dijkstra es que los dos últimos tramos se combinan si y solo si sus tamaños son números de Leonardo consecutivos L ( i +1) y L ( i ) (en ese orden), números que se definen recursivamente, de una manera muy similar a los números de Fibonacci , 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 de Leonardo. La secuencia de tamaños de estiramiento que descompone las primeras n posiciones, para cualquier n , se puede encontrar de manera voraz: el primer tamaño es el número de Leonardo más grande que no exceda n , y el resto (si lo hay) se descompone de manera recursiva. Los tamaños de los estiramientos son decrecientes, estrictamente excepto posiblemente para dos tamaños finales 1, y evitando números de Leonardo sucesivos excepto posiblemente para los dos tamaños finales.

Además de que cada tramo es un árbol ordenado por heap, las raíces de los árboles se mantienen en orden ordenado. Esto efectivamente agrega un tercer hijo (al que Dijkstra llama "hijastro") a cada raíz, vinculándola con la raíz anterior. Esto combina todos los árboles en un heap global, con el máximo global al final.

Aunque la ubicación del hijastro de cada nodo es fija, el vínculo solo existe para las raíces de los árboles, lo que significa que los vínculos se eliminan cuando se fusionan los árboles. Esto es diferente de los hijos comunes, que están vinculados mientras exista el padre.

En la primera fase (crecimiento del montón) de la ordenación, se reorganiza una parte inicial cada vez más grande de la matriz de modo que el subárbol de cada uno de sus tramos sea un montón máximo: la entrada en cualquier posición que no sea una 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 (reducción del montón), el nodo máximo se separa del extremo de la matriz (sin necesidad de moverlo) y los invariantes del montón se restablecen entre sus hijos (en concreto, entre los hijastros recién creados).

La implementación práctica frecuentemente necesita calcular números de Leonardo L ( k ) . Dijkstra proporciona un código inteligente que utiliza un número fijo de variables enteras para calcular de manera eficiente 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 que se deben ordenar, se puede almacenar una tabla precalculada de números de Leonardo en el espacio O (log  N ) .

Si bien las dos fases del procedimiento de ordenamiento son opuestas entre sí en lo que respecta a la evolución de la estructura de secuencia de montones, se implementan utilizando un primitivo central, equivalente a la operación de "seleccionar" en un montón máximo binario.

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

La diferencia entre smoothsort y un montículo máximo binario es que la raíz de cada tramo debe ordenarse con respecto a un tercer "hijastro": la raíz del tramo anterior. Por lo tanto, el procedimiento de tamizado comienza con una serie de comparaciones de cuatro vías (el nodo raíz y tres hijos) hasta que el hijastro no sea 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 encuentre su ubicación final y se restablezcan los invariantes.

Cada árbol es un árbol binario completo : cada nodo tiene dos hijos o ninguno. No es necesario lidiar con el caso especial de un hijo que ocurre en un montón binario implícito estándar . (Pero el caso especial de los enlaces hijastros 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 selección está limitado por O (log  n ) .

Cuando se considera incorporar un elemento adicional a la secuencia de extensiones (lista de estructuras de montón disjuntas), forma una nueva extensión de un elemento o combina las dos extensiones más a la derecha convirtiéndose en el padre de ambas raíces y formando una nueva extensión que reemplaza a las dos en la secuencia. Cuál de las dos cosas ocurre depende solo de los tamaños de las extensiones actualmente presentes (y, en última instancia, solo del índice del elemento agregado); Dijkstra estipuló que las extensiones se combinan si y solo si sus tamaños son L ( k +1) y L ( k ) para algunos k , es decir, números de Leonardo consecutivos; la nueva extensión tendrá tamaño L ( k +2) .

En cualquier caso, el nuevo elemento debe clasificarse hasta su lugar correcto en la estructura del montón. Incluso si el nuevo nodo es una extensión de un solo elemento, debe ordenarse en relación con la raíz de la extensión anterior.

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

Por lo tanto, cuando se agrega un elemento, se calcula la posición de su futuro padre. Si está dentro del rango de valores restantes que se deben ordenar, se actúa como si no hubiera ningún hijastro y se realiza un filtrado descendente dentro del árbol actual.

Durante esta fase, la forma de la secuencia de tramos pasa por los cambios de la fase de crecimiento en sentido inverso. No se necesita ningún trabajo al separar 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 se puede obtener aplicando el cribado dos veces: 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 un promedio de una operación de selección por nodo.

Ya se sabe que las raíces recién expuestas están ordenadas correctamente con respecto a sus hijos normales; lo único que está en cuestión es el orden relativo a sus hijastros. Por lo tanto, al reducir el montón, el primer paso de cribado se puede simplificar a una única comparación con el hijastro. Si se produce un intercambio, los pasos posteriores deben realizar la comparación completa de cuatro vías.

Smoothsort tarda O ( n ) tiempo en procesar una matriz preordenada, O ( n log  n ) en el peor de los casos, y logra un rendimiento casi lineal en muchas entradas casi ordenadas. Sin embargo, no maneja todas las secuencias casi ordenadas de manera óptima. Usando el recuento de inversiones como una medida de falta de ordenación (la cantidad de pares de índices i y j con i < j y A [ i ] > A [ j ] ; para una entrada ordenada aleatoriamente esto es aproximadamente n ² /4 ), hay posibles secuencias de entrada con O ( n log  n ) inversiones que hacen que tome Ω( n log  n ) tiempo, mientras que otros algoritmos de ordenación adaptativos pueden resolver estos casos en O ( n log log  n ) tiempo. ^[2]

El algoritmo smoothsort debe poder almacenar en memoria los tamaños de todos los árboles en el montón de Leonardo. Dado que están ordenados por orden y todos los órdenes son distintos, esto se hace generalmente utilizando un vector de bits que indica qué órdenes están presentes. Además, dado que el orden más grande es como máximo O (log  n ) , estos bits se pueden codificar en O (1) palabras de máquina, suponiendo un modelo de máquina transdicotómico .

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

Un algoritmo más simple inspirado en smoothsort es poplar sort . ^[5] Llamado así por las filas de árboles de tamaño decreciente que suelen verse en los polders holandeses , realiza menos comparaciones que smoothsort para entradas que no están mayoritariamente ordenadas, pero no puede lograr un tiempo lineal para entradas ordenadas.

El cambio significativo que introduce la clasificación de álamos es que las raíces de los distintos árboles no se mantienen en un orden ordenado; no hay vínculos "hijastros" que los unan en un solo montón. En cambio, cada vez que se reduce el montón en la segunda fase, se buscan las raíces para encontrar la entrada máxima.

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

Los autores también sugieren utilizar árboles binarios perfectos en lugar de árboles de 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 de postorden , ^[6] logrando un tiempo de inserción amortizado de O (1) en una estructura más simple que un montón binomial implícito .

La biblioteca C musl utiliza smoothsort para su implementación de qsort(). ^{[7] [8]}

• Transcripción comentada de EWD796a, 16 de agosto de 1981
• Explicación moderna y detallada de Smoothsort
• wikilibros:Implementación de algoritmos/Ordenamiento/Ordenamiento suave
• Descripción y ejemplo de implementación del montón de Poplar
• Noshita, Kohei; Nakatani, Yoshinobu (abril de 1985). "Sobre la estructura del montón anidado en Smoothsort". Fundamentos matemáticos de la informática y sus aplicaciones ( japonés :数理解析研究所講究録) . 556 : 1–16. hdl :2433/98975.