Creo que no lo es, porque hay $10!$ permutaciones de elementos de $10$ y $10! \gt 2^{20}$.
¿Alguien me puede señalar cómo probar rigurosamente?
Respuestas
¿Demasiados anuncios?
Construir un árbol cuyos nodos interiores decir que las comparaciones por pares se realizan: el nodo raíz se dice que dos elementos se comparan en primer lugar, y luego se procede a uno de sus dos hijos en función del resultado de esa comparación. Cada nodo interior del árbol tiene exactamente dos niños. Cada hoja tiene la etiqueta con las instrucciones para cambiar los elementos de la lista en el orden basado en los resultados de las anteriores comparaciones. Cualquier comparación de ordenación se puede poner en este formulario, y una comparación de ordenación que se hace en la mayoría de los 20 comparaciones se puede poner en la forma de un árbol con una profundidad de 20 y por lo tanto sólo se $2^{20}=1048576$ hojas.
Para obtener una lista con 10 elementos, hay $10! = 3628800$ posible entrada de listas y por lo tanto, para cualquier comparación de ordenación, dos listas deben llegar a la misma hoja, y la especie, por lo tanto utiliza la misma secuencia de swaps para ordenar los elementos de ambas listas. Pero esto debe dejar al menos uno de ellos fuera de orden.
Todo esto supone que el 20 elementos de la lista de entrada son todas diferentes. Pero usted puede asumir que porque una comparación de ordenación que podría funcionar para cualquier lista de 20 elementos, como un caso especial de trabajo para cualquier lista de 20 distintos elementos.
Es interesante considerar el caso de radix sort, para que este análisis no se aplica.
Hagen von Eitzen
Puntos
171160
Está a la derecha y dar la correcta razón. Ya a partir de este simple aspecto de ello se desprende que, al menos, $22$ comparaciones son necesarios, si que es posible, a continuación, no es tan sencillo decidir. El flujo del algoritmo (incluyendo las entradas que obtener intercambiado y con la que se obtienen en comparación siguiente) está totalmente determinado por los resultados de las comparaciones. Por el pigeon-hole principio, dos de las $10!$ permutaciones posibles de $\{1,2,\ldots,10\}$ producir el mismo de $2^{20}$ secuencias posibles de los resultados de la comparación, por tanto, producen el mismo flujo y el mismo swaps - que no puede ordenar tanto.
