Número mínimo de comparaciones necesarias para ordenar (ordenar) 5 elementos

Encuentre la menor cantidad de comparaciones necesarias para ordenar (ordenar) cinco elementos e idee un algoritmo que clasifique estos elementos usando esta cantidad de comparaciones.

Solución : ¡ Hay 5! = 120 resultados posibles. Por lo tanto, un árbol binario para el procedimiento de clasificación tendrá al menos 7 niveles. De hecho, ≥ 120 implica h ≥ 7. Pero 7 comparaciones no son suficientes. El menor número de comparaciones necesarias para ordenar (ordenar) cinco elementos es 8.$2^h$$h$

Aquí está mi pregunta real: encontré un algoritmo que lo hace en 8 comparaciones, pero ¿cómo puedo demostrar que no se puede hacer en 7 comparaciones?

La solución está mal. Demuth [1; a través de 2, sec. 5.3.1] muestra que se pueden ordenar cinco valores utilizando solo siete comparaciones, es decir, que el límite inferior "teórico de la información" es estricto en este caso.

La respuesta es un método adaptado a , no un algoritmo general. Tampoco es muy agradable. Este es el esquema:$n=5$

1. Ordena los dos primeros pares.

2. Ordene los pares con su respectivo elemento más grande.

   $[a,b,c,d,e]$$a<b<d$$c<d$

3. $e$$[a,b,d]$

4. $c$

$c<d$$c$

Como no veo cómo escribir un pseudocódigo "agradable" de esto, vea aquí una implementación probada (y con suerte legible).

1. Doctor en Filosofía. tesis (Universidad de Stanford) por HB Demuth (1956)

   Ver también Clasificación electrónica de datos por HB Demuth (1985)

2. Ordenar y buscar por Donald E. Knuth; El arte de la programación de computadoras vol. 3 (2a ed., 1998)

$\log(n!)$$n$$<$$>$$n!$$\log(5!) \approx 6.91$

$5!= 120$$2^7= 128$

No es un código bonito o corto, y probablemente debería usar métodos de generación de código para crear el árbol de decisión y los intercambios en lugar de codificarlo a mano, pero funciona; y probablemente funciona para cualquier posible permutación de 5 elementos, lo que demuestra que puede clasificar 5 elementos en no más de 7 comparaciones.

Estaba pensando en la clasificación rápida. selecciona como pivote el elemento que resulta ser el elemento del medio. compare el pivote con los 4 elementos restantes, lo que da como resultado dos pilas para ordenar. cada una de esas pilas se pueden clasificar en 1 comparación. a menos que haya cometido un error terrible, los 5 elementos se clasificaron por completo en solo 6 comparaciones y creo que esa es la menor cantidad de comparaciones necesarias para hacer el trabajo. La pregunta original era encontrar el menor número de comparaciones para ordenar 5 elementos.

Si puede probar el algoritmo, pruébelo en todas las combinaciones de números. Si tienes muchos números, prueba en muchas combinaciones aleatorias. No es preciso, pero es más rápido que todas las combinaciones.

Mínimo
a <b <c = 2
a <b <c <d = 3
a <b <c <d <e = 4

Máximo
3 ^ 3
4 ^ 4
5 ^ 5

Inserte en el medio use 3-6 para 4 números.
Combinación de uso 4-5 para 4 números.
La comparación mínima por wiki es 5 para 4 números :) Para 5 es 7. Usas 8, aún así.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
Si sabe todo antes de las comparaciones, puede ir abajo con las comparaciones. Mi promedio para 4 números es 3.96 / 1024 todas las combinaciones.