Clasificación suave

En informática, smoothsort es un algoritmo de clasificación basado en la comparación. Edsger Dijkstra inventó y publicó una variante de heapsort en 1981. Al igual que heapsort, smoothsort es un algoritmo in situ con un límite superior de O(n log n), pero no es una ordenación estable. 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.

Resumen

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 creciente. Cuando el prefijo se ha reducido a nada, la matriz se ordena por completo.

Heapsort asigna el árbol binario a la matriz mediante un recorrido del árbol de arriba hacia abajo en anchura; 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 clasificación: debe pasar por la raíz antes de moverse a su ubicación final.

Smoothsort utiliza un mapeo diferente, un recorrido posterior al orden de profundidad de abajo hacia 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 sobre las hojas, y cada elemento que no es una 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 para 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 (incluida toda la matriz) podría ser un intervalo de este tipo correspondiente a un subárbol, pero en general se descompone como una unión de varios intervalos de subárbol sucesivos, que Dijkstra llama "estiramientos". Cualquier subárbol sin un padre (es decir, enraizado en una posición cuyo padre se encuentra más allá del prefijo en consideración) da un tramo en la descomposición de ese intervalo, cuya descomposición es, por lo tanto, única. Cuando se agrega un nuevo nodo al prefijo, ocurre uno de dos casos: o la posición es una hoja y agrega un tramo de longitud 1 a la descomposición, o se combina con los dos últimos tramos, convirtiéndose en el padre de sus respectivas raíces, reemplazando así los dos tramos por un nuevo tramo que contiene su unión más la nueva posición (raíz).

Dijkstra señaló que la regla obvia sería combinar extensiones 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, pero gana un pequeño factor constante en la eficiencia al requerir menos tramos para cubrir cada intervalo.

La regla que usa 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), cuyos números 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

Como consecuencia, el tamaño de cualquier subárbol es un número de Leonardo. La secuencia de tamaños de extensión que descomponen las primeras n posiciones, para cualquier n, se puede encontrar de manera codiciosa: 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 recursivamente. Los tamaños de los tramos son decrecientes, en sentido estricto 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 montones, las raíces de los árboles se mantienen ordenadas. Esto efectivamente agrega un tercer hijo (al que Dijkstra llama "hijastro") a cada raíz vinculándola a la raíz anterior. Esto combina todos los árboles 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 solo existe para las raíces de los árboles, lo que significa que los enlaces se eliminan cada vez que se fusionan los árboles. Esto es diferente de los niños ordinarios, que están vinculados mientras exista el padre.

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

La implementación práctica frecuentemente necesita 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 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 ordenarán, se puede almacenar una tabla precalculada de números de Leonardo en el espacio O(log N).

Operaciones

Si bien las dos fases del procedimiento de clasificación son opuestas entre sí en lo que se refiere a la evolución de la estructura de secuencia de montones, se implementan utilizando una primitiva básica, equivalente a la "tamizar" operación en un max-heap binario.

Tamizar

La operación de tamizado central (que Dijkstra llama "trinkle") restaura el invariante del montón cuando posiblemente se viole solo 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 max-heap binario es que la raíz de cada tramo debe ordenarse con respecto a un tercer "hijastro": la raíz del tramo anterior. Entonces, 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 es el elemento máximo, luego una serie de comparaciones de tres vías (la raíz más dos hijos) hasta que la raíz el nodo encuentra su hogar final y las invariantes se restablecen.

Cada árbol es un árbol binario completo: cada nodo tiene dos hijos o ninguno. No hay necesidad de tratar con el caso especial de un niño que ocurre en un montón binario implícito estándar. (Pero el caso especial de los enlaces de hijastros compensa con creces este ahorro).

Porque hay tramos O(log n), cada uno de los cuales es un árbol de profundidad O(log n), el tiempo para realizar cada operación de cribado está limitado por O(registro n).

Hacer crecer la región del montón incorporando un elemento a la derecha

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

En cualquiera de los dos casos, el nuevo elemento debe tamizarse hasta su lugar correcto en la estructura del montón. Incluso si el nuevo nodo es una extensión de un elemento, debe ordenarse en relación con la raíz de la extensión anterior.

Optimización

El algoritmo de Dijkstra ahorra trabajo al observar que se requiere el invariante de montón completo al final de la fase de crecimiento, pero no se requiere 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, calcule la posición de su futuro padre. Si esto está dentro del rango de valores restantes para ordenar, actúe como si no hubiera un hijastro y solo evalúe dentro del árbol actual.

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

Durante esta fase, la forma de la secuencia de tramos pasa por los cambios de la fase de crecimiento a la inversa. No se necesita ningún trabajo para separar un nodo de hoja, pero para un nodo que no es de hoja, sus dos hijos se convierten en raíces de nuevos tramos y deben moverse a su lugar adecuado en la secuencia de raíces de tramos. Esto se puede obtener aplicando el tamizado dos veces: primero para el hijo izquierdo y luego para el hijo derecho (cuyo hijastro era el hijo izquierdo).

Debido a que la mitad de todos los nodos en un árbol binario completo son hojas, esto realiza un promedio de una operación de cribado por nodo.

Optimización

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

Análisis

Smoothsort toma O(n) tiempo para 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 de manera óptima todas las secuencias casi ordenadas. Usar el recuento de inversiones como una medida de falta de clasificación (el número de pares de índices i y j con i < j y A[i] > A[j]; para entradas ordenadas 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 clasificación adaptativa pueden resolver estos casos en O(n log log n) tiempo.

El algoritmo smoothsort debe poder almacenar en la memoria los tamaños de todos los árboles en el montón de Leonardo. Dado que están ordenadas por orden y todas las órdenes son distintas, esto generalmente se hace usando 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, asumiendo 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 inferiores a L(32) = 7049155. Un vector de 64 bits servirá para tamaños inferiores a L(64) = 34335360355129 ≈ 2⁴⁵. En general, toma 1/log₂(φ) ≈ 1,44 bits de vector por bit de tamaño.

Clase de álamo

Un algoritmo más simple 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ólderes holandeses, realiza menos comparaciones que la ordenación suave para las entradas que en su mayoría no están ordenadas, pero que no pueden lograr un tiempo lineal para las entradas ordenadas.

El cambio significativo realizado por la clasificación de álamos en el sentido de que las raíces de los diversos árboles no se mantienen ordenadas; no hay "hijastro" enlaces que los unen 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.

Porque hay n pasos de reducción, 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 álamos es O(n registro n).

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

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

Aplicaciones

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