Ordenación por comparación

Una clasificación por comparación es un tipo de algoritmo de clasificación que solo lee los elementos de la lista a través de una única operación de comparación abstracta (a menudo un operador "menor o igual a" o una comparación de tres vías ) que determina cuál de dos elementos debe aparecer primero en la lista. lista ordenada final. El único requisito es que el operador realice una reserva total sobre los datos, con:

si a ≤ b y b ≤ c entonces a ≤ c (transitividad)
para todos a y b , a ≤ b o b ≤ a ( conexión ).

Es posible que tanto a ≤ b como b ≤ a ; en este caso cualquiera de ellos puede aparecer primero en la lista ordenada. En una clasificación estable , el orden de entrada determina el orden de clasificación en este caso.

Los tipos de comparación estudiados en la literatura están "basados en comparación". ^[1] El algoritmo puede intercambiar o reorganizar los elementos a y b de otro modo solo cuando el orden entre estos elementos se ha establecido en función de los resultados de comparaciones anteriores. Este es el caso cuando el orden entre a y b se puede derivar mediante el cierre transitivo de estos resultados de comparación anteriores.

Para las clasificaciones basadas en comparaciones, la decisión de ejecutar operaciones básicas distintas de las comparaciones se basa en el resultado de las comparaciones. Por lo tanto, en un análisis de tiempo, el número de comparaciones ejecutadas se utiliza para determinar estimaciones del límite superior para el número de operaciones básicas ejecutadas, como swaps o asignaciones. ^[1]

Una metáfora para pensar en tipos de comparación es que alguien tiene un juego de pesas sin etiquetar y una balanza . Su objetivo es alinear las pesas por su peso sin ninguna información excepto la que se obtiene colocando dos pesas en la báscula y viendo cuál pesa más (o si pesan lo mismo).

Ejemplos

Algunos de los tipos de comparación más conocidos incluyen:

Límites de rendimiento y ventajas de las diferentes técnicas de clasificación.

Existen límites fundamentales en el rendimiento de los tipos de comparación. Una clasificación de comparación debe tener un límite inferior promedio de operaciones de comparación Ω ( n log n ), ^[2] que se conoce como tiempo linealítmico . Esto es consecuencia de la información limitada disponible únicamente a través de comparaciones o, para decirlo de otra manera, de la vaga estructura algebraica de conjuntos totalmente ordenados. En este sentido, mergesort, heapsort e introsort son asintóticamente óptimos en términos del número de comparaciones que deben realizar, aunque esta métrica ignora otras operaciones. Las clasificaciones sin comparación (como los ejemplos que se analizan a continuación) pueden lograr un rendimiento O ( n ) mediante el uso de operaciones distintas a las comparaciones, lo que les permite eludir este límite inferior (suponiendo que los elementos sean de tamaño constante).

Las clasificaciones de comparación pueden ejecutarse más rápido en algunas listas; Muchas clasificaciones adaptativas , como la clasificación por inserción, se ejecutan en tiempo O ( n ) en una lista ya ordenada o casi ordenada. El límite inferior Ω ( n log n ) se aplica solo al caso en el que la lista de entrada puede estar en cualquier orden posible.

Es posible que las medidas del mundo real de la velocidad de clasificación deban tener en cuenta la capacidad de algunos algoritmos para utilizar de manera óptima la memoria caché relativamente rápida de la computadora , o la aplicación puede beneficiarse de métodos de clasificación en los que los datos ordenados comienzan a aparecer rápidamente para el usuario (y luego la velocidad del usuario). de lectura será el factor limitante) en contraposición a los métodos de clasificación en los que no hay salida disponible hasta que se ordene toda la lista.

A pesar de estas limitaciones, los ordenamientos por comparación ofrecen la notable ventaja práctica de que el control sobre la función de comparación permite ordenar muchos tipos de datos diferentes y un control preciso sobre cómo se ordena la lista. Por ejemplo, invertir el resultado de la función de comparación permite ordenar la lista al revés; y se puede ordenar una lista de tuplas en orden lexicográfico simplemente creando una función de comparación que compare cada parte en secuencia:

función tuplaCompare((izquierdaa, izquierdab, izquierdac), (derecha, derechab, derechac)) si izquierdaa ≠ derechaa devuelve comparar(izquierdaa, derechaa) de lo contrario si izquierdab ≠ derechab devuelve comparar(izquierdab, derechab) de lo contrario  devuelve comparar(izquierdac, derechac)

Los tipos de comparación generalmente se adaptan más fácilmente a órdenes complejos como el orden de los números de punto flotante . Además, una vez escrita una función de comparación, se puede utilizar cualquier tipo de comparación sin modificaciones; Las clasificaciones sin comparación suelen requerir versiones especializadas para cada tipo de datos.

Esta flexibilidad, junto con la eficiencia de los algoritmos de clasificación por comparación anteriores en las computadoras modernas, ha llevado a una preferencia generalizada por la clasificación por comparación en la mayoría de los trabajos prácticos.

Alternativas

Algunos problemas de clasificación admiten una solución estrictamente más rápida que el límite $Ω (n log n)$ para la clasificación por comparación mediante el uso de clasificaciones sin comparación ; un ejemplo es la clasificación de números enteros , donde todas las claves son números enteros. Cuando las claves forman un rango pequeño (en comparación con $n$ ), la ordenación por conteo es un algoritmo de ejemplo que se ejecuta en tiempo lineal. Otros algoritmos de clasificación de enteros, como la clasificación por base , no son asintóticamente más rápidos que la clasificación por comparación, pero pueden ser más rápidos en la práctica.

El problema de ordenar pares de números por su suma tampoco está sujeto al límite $Ω(n ² log n)$ (el cuadrado resultante del emparejamiento); el algoritmo más conocido todavía requiere $O(n ² log n)$ tiempo, pero sólo $O(n ²)$ comparaciones.

Número de comparaciones necesarias para ordenar una lista

Arriba: una comparación del límite inferior con el número mínimo real de comparaciones (de OEIS : A036604 ) necesarias para ordenar una lista de n elementos (para el peor de los casos). Abajo: Utilizando la aproximación de Stirling , este límite inferior está bien aproximado por .

\left\lceil \log _ {2}(n!)\right\rceil

n\log _{2}n-{\frac {n}{\ln 2}}

El número de comparaciones que requiere un algoritmo de ordenación por comparación aumenta en proporción a , donde es el número de elementos a ordenar. Esta cota es asintóticamente estrecha . $n\log(n)$ $n$

Dada una lista de números distintos (podemos asumir esto porque se trata de un análisis del peor de los casos), hay permutaciones factoriales , exactamente una de las cuales es la lista en orden ordenado. El algoritmo de clasificación debe obtener suficiente información de las comparaciones para identificar la permutación correcta. Si el algoritmo siempre se completa después de la mayoría de los pasos, no puede distinguir más que casos porque las claves son distintas y cada comparación tiene solo dos resultados posibles. Por lo tanto, $n$ $f(n)$ $2^{f(n)}$

2^{f(n)}\geq n!

, o equivalente

f(n)\geq \log _ {2}(n!).

Observando los primeros factores de , obtenemos $n/2$ $n!=n(n-1)\cdots 1$

\log _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2} }\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).

\log _{2}(n!)=\Omega (n\log n).

Esto proporciona la parte inferior del reclamo. Se puede dar un límite más preciso mediante la aproximación de Stirling . Un límite superior de la misma forma, con el mismo término principal que el límite obtenido de la aproximación de Stirling, se deriva de la existencia de algoritmos que alcanzan este límite en el peor de los casos, como merge sort .

El argumento anterior proporciona un límite inferior absoluto , en lugar de sólo asintótico, para el número de comparaciones, es decir, comparaciones. Este límite inferior es bastante bueno (se puede aproximar a él dentro de una tolerancia lineal mediante una simple ordenación por combinación), pero se sabe que es inexacto. Por ejemplo , pero se ha demostrado que el número mínimo de comparaciones para ordenar 13 elementos es 34. $\left\lceil \log _ {2}(n!)\right\rceil$ $\left\lceil \log _ {2}(13!)\right\rceil =33$

Determinar el número exacto de comparaciones necesarias para ordenar un número determinado de entradas es un problema computacional difícil incluso para n pequeño , y no se conoce ninguna fórmula simple para la solución. Para conocer algunos de los pocos valores concretos que se han calculado, consulte OEIS : A036604 .

Límite inferior para el número promedio de comparaciones

Se aplica un límite similar al número promedio de comparaciones. Asumiendo que

todas las claves son distintas, es decir, cada comparación dará a > b o a < b , y
la entrada es una permutación aleatoria, elegida uniformemente del conjunto de todas las permutaciones posibles de n elementos,

es imposible determinar en qué orden está la entrada con menos de $log 2 (n!)$ comparaciones en promedio.

Esto se puede ver más fácilmente utilizando conceptos de la teoría de la información . La entropía de Shannon de tal permutación aleatoria es $log 2 (n!)$ bits. Dado que una comparación sólo puede dar dos resultados, la cantidad máxima de información que proporciona es 1 bit. Por lo tanto, después de k comparaciones, la entropía restante de la permutación, dados los resultados de esas comparaciones, es al menos $log 2 (n!) - k$ bits en promedio. Para realizar la clasificación, se necesita información completa, por lo que la entropía restante debe ser 0. De ello se deduce que k debe ser al menos $log 2 (n!)$ en promedio.

El límite inferior derivado de la teoría de la información se denomina "límite inferior de la teoría de la información". El límite inferior de la teoría de la información es correcto, pero no es necesariamente el límite inferior más fuerte. Y en algunos casos, el límite inferior teórico de la información de un problema puede incluso estar lejos del verdadero límite inferior. Por ejemplo, el límite inferior de selección de la teoría de la información es mientras que las comparaciones son necesarias para un argumento contradictorio. La interacción entre el límite inferior de la teoría de la información y el límite inferior verdadero es muy parecida a una función de valor real que limita inferiormente una función entera. Sin embargo, esto no es exactamente correcto cuando se considera el caso promedio. $\left\lceil \log _ {2}(n)\right\rceil$ $n-1$

Para descubrir qué sucede al analizar el caso promedio, la clave es ¿a qué se refiere "promedio"? ¿Promediando sobre qué? Con cierto conocimiento de la teoría de la información, el límite inferior de la teoría de la información promedia el conjunto de todas las permutaciones en su conjunto. Pero cualquier algoritmo informático (según lo que se cree actualmente) debe tratar cada permutación como una instancia individual del problema. Por lo tanto, el límite inferior promedio que estamos buscando se promedia en todos los casos individuales.

Para buscar el límite inferior relacionado con la imposibilidad de lograr computadoras, adoptamos el modelo de árbol de decisión . Reformulemos un poco cuál es nuestro objetivo. En el modelo de árbol de decisión , el límite inferior que se mostrará es el límite inferior de la longitud promedio de los caminos de raíz a hoja de un árbol binario de hojas (en el que cada hoja corresponde a una permutación). La longitud promedio mínima de un árbol binario con un número determinado de hojas se logra mediante un árbol binario completo equilibrado, porque cualquier otro árbol binario puede reducir su longitud de trayectoria moviendo un par de hojas a una posición más alta. Con algunos cálculos cuidadosos, para un árbol binario completo equilibrado con hojas, la longitud promedio de los caminos de raíz a hoja viene dada por $n!$ $n!$

{\frac {(2n!-2^{\lfloor \log _{2}n!\rfloor +1})\cdot \lceil \log _{2}n!\rceil +(2^{\ lfloor \log _{2}n!\rfloor +1}-n!)\cdot \lfloor \log _{2}n!\rfloor }{n!}}=\lceil \log _{2}n!\ rceil +1-{\frac {2^{\lceil \log _{2}n!\rceil }}{n!}}

Por ejemplo, para $n = 3$ , el límite inferior teórico de la información para el caso promedio es aproximadamente 2,58, mientras que el límite inferior promedio derivado mediante el modelo de árbol de decisión es 8/3, aproximadamente 2,67.

En el caso de que varios elementos puedan tener la misma clave, no existe una interpretación estadística obvia para el término "caso promedio", por lo que no se puede aplicar un argumento como el anterior sin hacer suposiciones específicas sobre la distribución de claves.

n log n número máximo de comparaciones para el tamaño de la matriz en formato 2^k

Puede calcular fácilmente la combinación de listas ordenadas de algoritmos reales (las matrices están ordenadas en n bloques con tamaño 1, se combinan de 1 a 1 a 2, se combinan de 2 a 2 a 4...).

(1) = = = = = = = = =(2) = = = = // max 1 compara (tamaño1+tamaño2-1), 4 veces se repite para concatenar 8 matrices con tamaño 1 y 1 === === === ===(3) = = // max 7 compara, 2x repeticiones para concatenar 4 matrices con tamaño 2 y 2 === ===  ===== ===== ======= =======(4) // máximo 15 comparaciones, 1x repeticiones para concatenar 2 matrices con tamaño 4 y 4Extracción de fórmulas:n = 256 = 2^8 (tamaño de matriz en formato 2^k, para simplificar)En = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32- 1) + 64(n/64-1) + 128(n/128-1)En = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128)En = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128) | 1+2+4... = fórmula para la secuencia geométrica Sn = a1 * (q^i - 1) / (n - 1), n es el número de elementos, a1 es el primer elementoActivado = 8*n - 1 * (2^8 - 1) / (2 - 1)Activado = 8*n - (2^8 - 1) | 2^8 = norteEncendido = 8*n - (n - 1)Activado = (8-1)*n + 1 | 8 = ln(n)/ln(2) = ln(256)/ln(2)En = (ln(n)/ln(2) - 1) * n + 1Ejemplo:n = 2^4 = 16, En ~= 3*nn = 2^8 = 256, En ~= 7*nn = 2^10 = 1,024, activado ~= 9*nn = 2^20 = 1.048.576, activado ~= 19*n

Ordenar una lista preordenada

Si una lista ya está casi ordenada, según alguna medida de clasificación, el número de comparaciones necesarias para ordenarla puede ser menor. Una clasificación adaptativa aprovecha esta "clasificación previa" y se ejecuta más rápidamente en entradas casi ordenadas, a menudo manteniendo un límite de tiempo en el peor de los casos. Un ejemplo es la clasificación de montón adaptativa , un algoritmo de clasificación basado en árboles cartesianos . Se necesita tiempo , donde es el promedio, sobre todos los valores de la secuencia, del número de veces que la secuencia salta de abajo hacia arriba o viceversa. ^[12] $O(n\log n)$ $O(n\log k)$ $k$ $x$ $x$ $x$

Notas

^[13]

Notas

^ ab Wilkes, MV (1 de noviembre de 1974). "El arte de la programación informática, volumen 3, clasificación y búsqueda". La revista informática . 17 (4): 324–324. doi : 10.1093/comjnl/17.4.324. ISSN 0010-4620.
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. págs. 191-193. ISBN 0-262-03384-4.
^ Mark Wells, Aplicaciones de un lenguaje para la informática en combinatoria, Information Processing 65 (Actas del Congreso IFIP de 1965), 497–498, 1966.
^ Mark Wells, Elementos de computación combinatoria, Pergamon Press, Oxford, 1971.
^ Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Se requieren treinta y cuatro comparaciones para ordenar 13 elementos, LNCS 792, 260-269, 1994.
^ Marcin Peczarski, Clasificar 13 elementos requiere 34 comparaciones, LNCS 2461, 785–794, 2002.
^ abc Marcin Peczarski, Nuevos resultados en la clasificación por comparación mínima, Algorithmica 40 (2), 133-145, 2004.
^ Marcin Peczarski, Investigación de posets asistida por computadora, tesis doctoral, Universidad de Varsovia, 2006.
^ Peczarski, Marcin (2007). "El algoritmo Ford-Johnson sigue invicto por menos de 47 elementos". inf. Proceso. Lett . 101 (3): 126-128. doi :10.1016/j.ipl.2006.09.001.
^ ab Cheng, Weiyi; Liu, Xiaoguang; Wang, pandilla; Liu, Jing (octubre de 2007). "最少比较排序问题中S（15）和S（19）的解决" [Los resultados de S(15) y S(19) al problema de clasificación de comparación mínima]. Revista de Fronteras de la Informática y la Tecnología (en chino). 1 (3): 305–313.
^ abc Stober, F. y Weiß, A. (2023). Límites inferiores para clasificar 16, 17 y 18 elementos. En 2023, Actas del Simposio sobre experimentos e ingeniería de algoritmos (ALENEX) (págs. 201-213). Sociedad de Matemáticas Industriales y Aplicadas
^ Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adaptado para archivos preclasificados", WADS '89: Actas del taller sobre algoritmos y estructuras de datos , Lecture Notes in Computer Science, vol. 382, Londres, Reino Unido: Springer-Verlag, págs. 499–509, doi :10.1007/3-540-51542-9_41.
^ Knuth, Donald E. (1998). El arte de la programación informática, volumen 3: (2ª ed.) clasificación y búsqueda. EE.UU.: Addison Wesley Longman Publishing Co., Inc. ISBN 978-0-201-89685-5.

Referencias

Donald Knuth . El arte de la programación informática , volumen 3: clasificación y búsqueda , segunda edición. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Sección 5.3.1: Clasificación por comparación mínima, págs. 180-197.