Tengo que modelar el plan de ejecución de ordenar una lista de 5 elementos, en python, usando el número mínimo de comparaciones entre elementos. Aparte de eso, la complejidad es irrelevante.Clasificando 5 elementos con una comparación mínima de elementos
El resultado es una lista de pares que representa las comparaciones necesarias para ordenar la lista en otro momento.
Sé que hay un algoritmo que hace esto en 7 comparaciones (entre elementos, siempre, sin complejidad), pero no puedo encontrar una versión legible (para mí).
¿Cómo puedo ordenar los 5 elementos en 7 comparaciones, y crear un "plan de ejecución" para el género?
PD: no tarea.
Peor caso, mejor caso, caso promedio? –
No era lo que estaba buscando, pero tenía curiosidad, así que acabo de comprobar: en las 120 permutaciones de rango (5), el número de permutaciones para las que el 'ordenado 'incorporado utiliza cada número de comparaciones son: 4: 2, 6: 5, 7: 33, 8: 56, 9: 24. – Dougal
Simplemente curioso, ¿qué tiene que ver Knuth con esto? – Yunchi