Ordenación por comparación

Una ordenación por comparación es un tipo de algoritmo de ordenació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 los dos elementos debe aparecer primero en la lista ordenada final. El único requisito es que el operador forme un preordenamiento 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 ( conexidad ).

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

Los ordenamientos por comparación estudiados en la literatura están "basados en la comparación". ^[1] Los elementos a y b pueden intercambiarse o reorganizarse de otro modo mediante el algoritmo 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 puede derivarse mediante el cierre transitivo de estos resultados de comparación anteriores.

En el caso de las ordenaciones 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 temporal, el número de comparaciones ejecutadas se utiliza para determinar estimaciones de límite superior para el número de operaciones básicas ejecutadas, como intercambios o asignaciones. ^[1]

Una metáfora para pensar en los tipos de comparación es que alguien tiene un conjunto de pesas sin etiquetar y una balanza . Su objetivo es alinear las pesas en orden según su peso sin ninguna información excepto la que se obtiene al colocar dos pesas en la balanza y ver 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 desempeño de los ordenamientos por comparación. Un ordenamiento por comparación debe tener un límite inferior de caso promedio de Ω ( n log n ) operaciones de comparación, ^[2] lo que se conoce como tiempo linealítmico . Esto es una consecuencia de la información limitada disponible a través de comparaciones únicamente —o, para decirlo de otra manera, de la vaga estructura algebraica de los 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 descuida otras operaciones. Los ordenamientos sin comparación (como los ejemplos discutidos a continuación) pueden lograr un desempeño O ( n ) al usar operaciones distintas a las comparaciones, lo que les permite eludir este límite inferior (asumiendo que los elementos son de tamaño constante).

Los ordenamientos por comparación pueden ejecutarse más rápido en algunas listas; muchos ordenamientos adaptativos , como el ordenamiento 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 una memoria caché de computadora relativamente rápida , o la aplicación puede beneficiarse de métodos de clasificación en los que los datos ordenados comienzan a aparecer para el usuario rápidamente (y luego la velocidad de lectura del usuario será el factor limitante) en oposición a métodos de clasificación en los que no hay salida disponible hasta que se ordena toda la lista.

A pesar de estas limitaciones, las ordenaciones 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 en sentido inverso; 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 tuplaComparar((izquierdaa, izquierdab, izquierdac), (derechaa, 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 ordenamientos por 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 que se escribe una función de comparación, se puede utilizar cualquier ordenamiento por comparación sin modificaciones; los ordenamientos sin comparación generalmente requieren versiones especializadas para cada tipo de datos.

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

Alternativas

Algunos problemas de ordenamiento admiten una solución estrictamente más rápida que el límite $Ω(n log n)$ para el ordenamiento por comparación mediante el uso de ordenamientos sin comparación ; un ejemplo es el ordenamiento 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 ),$ el ordenamiento por conteo es un algoritmo de ejemplo que se ejecuta en tiempo lineal. Otros algoritmos de ordenamiento de números enteros, como el ordenamiento por radix , no son asintóticamente más rápidos que el ordenamiento 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: Usando 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}}

La cantidad de comparaciones que requiere un algoritmo de ordenamiento por comparación aumenta en proporción a , donde es la cantidad de elementos a ordenar. Este límite es asintóticamente estricto . ${\estilo de visualización n\log(n)}$ ${\estilo de visualización n}$

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

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

, o equivalentemente

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

Observando los primeros factores de , obtenemos ${\estilo de visualización n/2}$ $n!=n(n-1)\cpuntos 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 del límite inferior de la afirmación. 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 a partir de la aproximación de Stirling, se deduce de la existencia de algoritmos que alcanzan este límite en el peor de los casos, como la ordenación por fusión .

El argumento anterior proporciona un límite inferior absoluto , en lugar de solo asintótico, para el número de comparaciones, es decir, comparaciones. Este límite inferior es bastante bueno (se puede alcanzar dentro de una tolerancia lineal mediante una simple ordenación por fusió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 una cantidad dada de entradas es un problema computacionalmente difícil incluso para valores n pequeños , y no se conoce ninguna fórmula simple para la solución. Para algunos de los pocos valores concretos que se han calculado, consulte OEIS : A036604 .

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

Un límite similar se aplica al número promedio de comparaciones. Suponiendo que

Todas las claves son distintas, es decir, cada comparación dará como resultado 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 se encuentra la entrada con menos de $log 2 (n!)$ comparaciones en promedio.

Esto se puede ver más fácilmente usando 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 solo 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 a través de la teoría de la información se expresa como "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 de la teoría de la información de un problema puede incluso estar lejos del límite inferior verdadero. Por ejemplo, el límite inferior de la teoría de la información de la selección es mientras que las comparaciones son necesarias para un argumento adversario. La interacción entre el límite inferior de la teoría de la información y el límite inferior verdadero es muy similar 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$ ${\estilo de visualización n-1}$

Para descubrir lo que ocurre al analizar el caso promedio, la clave es saber a qué se refiere "promedio". ¿Promedio sobre qué? Con un cierto conocimiento de la teoría de la información, el límite inferior de la teoría de la información promedia sobre 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 sobre todos los casos individuales.

Para buscar el límite inferior relacionado con la inalcanzabilidad de las computadoras, adoptamos el modelo de árbol de decisión . Reformulemos un poco 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 2 hojas (en el que cada hoja corresponde a una permutación). La longitud promedio mínima de un árbol binario con un número dado de hojas se logra mediante un árbol binario completo balanceado, porque cualquier otro árbol binario puede tener su longitud de camino reducida moviendo un par de hojas a una posición más alta. Con algunos cálculos cuidadosos, para un árbol binario completo balanceado con hojas, la longitud promedio de los caminos de raíz a hoja está dada por ${\estilo de visualización n!}$ ${\estilo de visualizació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 a través del modelo de árbol de decisión es 8/3, aproximadamente 2,67.

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

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

Se puede calcular fácilmente un algoritmo real de fusión de listas ordenadas (las matrices están ordenadas en n bloques con tamaño 1, se fusionan en 1–1 en 2, se fusionan 2–2 en 4...).

(1) = = = = = = = =(2) = = = = // máx. 1 compara (tamaño1+tamaño2-1), 4x se repite para concatenar 8 matrices con tamaño 1 y 1 === === === ===(3) = = // máx. 7 comparaciones, 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órmula:n = 256 = 2^8 (tamaño de la 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)On = 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 = norteEn = 8*n - (n - 1)En = (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, En ~= 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 ordenación, la cantidad de comparaciones necesarias para ordenarla puede ser menor. Una ordenación adaptativa aprovecha esta "ordenación previa" y se ejecuta más rápidamente en entradas casi ordenadas, a menudo manteniendo al mismo tiempo un límite de tiempo en el peor de los casos. Un ejemplo es la ordenación adaptativa por montículos , un algoritmo de ordenación basado en árboles cartesianos . Lleva tiempo , donde es el promedio, sobre todos los valores de la secuencia, de la cantidad de veces que la secuencia salta de abajo a arriba o viceversa. ^[12] $O(n\log n)$ $O(n\log k)$ ${\estilo de visualización k}$ ${\estilo de visualización x}$ ${\estilo de visualización x}$ ${\estilo de visualización x}$

Notas

^[13]

Notas

^ ab Wilkes, MV (1974-11-01). "El arte de la programación informática, volumen 3, ordenación y búsqueda". The Computer Journal . 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 computación 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, Ordenar 13 elementos requiere 34 comparaciones, LNCS 2461, 785–794, 2002.
^ abc Marcin Peczarski, Nuevos resultados en ordenamiento 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 siendo imbatible para menos de 47 elementos". Inf. Process. 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 ordenar 16, 17 y 18 elementos. En Actas del Simposio sobre Ingeniería de Algoritmos y Experimentos (ALENEX) de 2023 (págs. 201-213). Sociedad de Matemáticas Industriales y Aplicadas
^ Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adaptado para archivos preordenados", 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.) Ordenación y búsqueda. Estados Unidos: 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: Ordenación y búsqueda , segunda edición. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Sección 5.3.1: Ordenación por comparación mínima, págs. 180-197.