Una clasificación de 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 los dos elementos debe aparecer primero en el lista ordenada final. El único requisito es que el operador forme un preorden total sobre los datos, con:
- si un ≤ b y b ≤ c entonces un ≤ c (transitividad)
- para todos un y b , un ≤ b o b ≤ un ( conexidad ).
Es posible que tanto un ≤ b y b ≤ una ; en este caso, cualquiera de los dos 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.
Una metáfora para pensar en tipos de comparación es que alguien tiene un conjunto de pesos sin etiquetar y una balanza . Su objetivo es alinear los pesos en orden por su peso sin ninguna información excepto la obtenida al colocar dos pesos en la báscula y ver cuál es más pesado (o si pesan lo mismo).
Ejemplos de
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 de caso promedio de operaciones de comparación Ω ( n log n ), [1] que se conoce como tiempo linealítmico . Esto es una consecuencia de la limitada información disponible a través de las comparaciones únicamente 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. Los tipos de no comparación (como los ejemplos que se analizan a continuación) pueden lograr un rendimiento O ( n ) mediante el uso de operaciones distintas de las comparaciones, lo que les permite eludir este límite inferior (asumiendo que los elementos tienen un tamaño constante).
Las clasificaciones de 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 de Ω ( 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é de la computadora relativamente rápida , o la aplicación puede beneficiarse de métodos de clasificación donde los datos ordenados comienzan a aparecer al usuario rápidamente (y luego la velocidad del usuario). lectura será el factor limitante) en contraposición a los métodos de ordenación donde no hay salida disponible hasta que se ordena toda la lista.
A pesar de estas limitaciones, los tipos de comparación ofrecen la notable ventaja práctica de que el control sobre la función de comparación permite clasificar 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 uno puede ordenar una lista de tuplas en orden lexicográfico simplemente creando una función de comparación que compare cada parte en secuencia:
function tupleCompare ((lefta, leftb, leftc), (righta, rightb, rightc)) if lefta ≠ righta return compare (lefta, righta) else if leftb ≠ rightb return compare (leftb, rightb) else return compare (leftc, rightc)
La notación ternaria equilibrada permite realizar comparaciones en un solo paso, cuyo resultado será "menor que", "mayor que" o "igual a".
Los tipos de comparación generalmente se adaptan más fácilmente a órdenes complejos, como el orden de los números de coma flotante . Además, una vez que se escribe una función de comparación, se puede utilizar cualquier tipo de comparación sin modificaciones; Los tipos de no 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 los tipos de 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 de Ω ( n log n ) para la clasificación por comparación mediante el uso de clasificaciones sin comparación ; un ejemplo es la ordenació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 ordenación de enteros, como la ordenación por base , no son asintóticamente más rápidos que la ordenació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 toma O ( n ² log n ) tiempo, pero solo O ( n ²) comparaciones.
Número de comparaciones necesarias para ordenar una lista
norte | Mínimo | |
---|---|---|
1 | 0 | 0 |
2 | 1 | 1 |
3 | 3 | 3 |
4 | 5 | 5 |
5 | 7 | 7 |
6 | 10 | 10 |
7 | 13 | 13 |
8 | dieciséis | dieciséis |
9 | 19 | 19 |
10 | 22 | 22 |
11 | 26 | 26 |
12 | 29 | 30 [2] [3] |
13 | 33 | 34 [4] [5] [6] |
14 | 37 | 38 [6] |
15 | 41 | 42 [7] [8] [9] |
dieciséis | 45 | 45 o 46 [10] |
17 | 49 | 49 o 50 |
18 | 53 | 53 o 54 |
19 | 57 | 58 [9] |
20 | 62 | 62 |
21 | 66 | 66 |
22 | 70 | 71 [6] |
norte | ||
10 | 22 | 19 |
100 | 525 | 521 |
1000 | 8530 | 8 524 |
10000 | 118 459 | 118 451 |
100 000 | 1 516 705 | 1 516 695 |
1 000 000 | 18 488 885 | 18 488 874 |
El número de comparaciones que requiere un algoritmo de clasificación de comparación aumenta en proporción a , dónde es el número de elementos a ordenar. Este límite es asintóticamente estrecho .
Dada una lista de números distintos (podemos asumir esto porque este es 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 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,
- , o equivalente
Mirando el primero factores de , obtenemos
Esto proporciona la parte de límite inferior de la reivindicación. Se puede dar un mejor límite a través de la aproximación de Stirling .
Un límite superior idéntico se deriva de la existencia de los algoritmos que alcanzan este límite en el peor de los casos, como heapsort y mergesort .
El argumento anterior proporciona un límite inferior absoluto , en lugar de solo asintótico, en el número de comparaciones, a sabercomparaciones. Este límite inferior es bastante bueno (se puede abordar dentro de una tolerancia lineal mediante una simple combinación de clasificació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.
Determinar el número exacto de comparaciones necesarias para ordenar un número dado de entradas es un problema computacionalmente difícil incluso para n pequeños , y no se conoce una 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 medio de comparaciones
Se aplica un límite similar al número medio de comparaciones. Asumiendo que
- todas las claves son distintas, es decir, cada comparación dará ya sea una > b o un < b , y
- la entrada es una permutación aleatoria, elegida uniformemente del conjunto de todas las posibles permutaciones 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 de 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 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 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 similar a una función de valor real que limita el límite inferior de una función entera. Sin embargo, esto no es exactamente correcto cuando se considera el caso promedio.
Para descubrir qué sucede al analizar el caso promedio, la clave es ¿a qué se refiere 'promedio'? ¿Promediando sobre qué? Con algún 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 para todos los casos individuales.
Para buscar el límite inferior relacionado con la imposibilidad de alcanzar las 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 muestra es el límite inferior de la longitud promedio de las rutas de raíz a hoja de un-hoja árbol binario (en el que cada hoja corresponde a una permutación). Sería convencido decir que un árbol binario completo equilibrado alcanza el mínimo de la longitud media. 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
Por ejemplo, para n = 3 , el límite inferior de la teoría 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 puedan tener 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.
Ordenar una lista ordenada previamente
Si una lista ya está ordenada previamente, el número de comparaciones necesarias para ordenar la lista suele ser menor. La noción de lista preordenada se puede formalizar con varias medidas de preclasificación . Dada tal medida, existe una noción de (débilmente) -Algoritmo de clasificación óptimo.
Notas
- ^ 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, Procesamiento de información 65 (Actas del Congreso de la IFIP de 1965), 497–498, 1966.
- ^ Mark Wells, Elementos de la informática 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.
- ^ a b c Marcin Peczarski, Nuevos resultados en la clasificación por comparación mínima, Algorithmica 40 (2), 133-145, 2004.
- ^ Marcin Peczarski, Investigación asistida por computadora de posets, tesis doctoral, Universidad de Varsovia, 2006.
- ^ Peczarski, Marcin (2007). "El algoritmo de Ford-Johnson sigue invicto por menos de 47 elementos". Inf. Proceso. Lett . 101 (3): 126-128. doi : 10.1016 / j.ipl.2006.09.001 .
- ^ a b Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; 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]. Journal of Frontiers of Computer Science and Technology (en chino). 1 (3): 305–313.
- ^ Peczarski, Marcin (3 de agosto de 2011). "Hacia una clasificación óptima de 16 elementos". Acta Universitatis Sapientiae . 4 (2): 215–224. arXiv : 1108.0866 . Código Bibliográfico : 2011arXiv1108.0866P .
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.