¿Cómo podemos llevar a cabo una combinación de 8 elementos con solo 16 comparaciones?

Question

Bueno, hice una pregunta sobre la clasificación hace unos días. Descubrí cómo demostrar que el menor número de comparaciones ordenando 8 elementos es 16 y entendí por qué. Pero mi algoritmo de ordenación por fusión cuenta 17 comparaciones y en mi caso es correcto. Para unir dos matrices ordenadas con longitud xey, necesitamos comparaciones (x + y) -1, de modo que en el orden de fusión obtenemos 17 comparaciones. Pero debe ser posible con 16 comparaciones, entonces ... ¿cómo? donde puedo guardar esa 1 comparación).

aquí es una imagen:

http://oeis.org/A001768

Gracias!

Answer 1

OP contiene una prueba clara de que fusión tipo de 8 elementos no es posible con menos de 17 comparaciones. Todavía es posible ordenar 8 elementos en 16 comparaciones con otro algoritmo. El algoritmo se describe en "El arte de la programación de computadoras" de D.Knuth, Vol.3, capítulo 5.3.1. Se llama merge insert.

El menor número de comparaciones no hace que este algoritmo sea el más rápido. Por ejemplo, Batcher odd–even mergesort con 19 comparaciones supera fácilmente a merge insert porque realiza la mayoría de las comparaciones en paralelo.

Answer 2

Solo puede obtener la menor solución cuando tiene que ordenar una cantidad impar de números.

Answer 3

Puede probar que 16 comparaciones no son suficientes probando todos los algoritmos posibles. Necesitaría un "algoritmo de generación de algoritmos" para esto.