Solo lea los dos primeros párrafos si solo quiere una pista. Hay una solución eficiente para esto (a menos que haya cometido un error, por supuesto). Primero ordena la lista. Ahora podemos escribir la lista original como una lista de productos de ciclos disjuntos.
Por ejemplo 5,3,4,2,1 tiene dos ciclos, (5,1) y (3,4,2). Se puede pensar que el ciclo comienza en 3, 4 en el punto 3, 2 en el punto 4 y 4 en 3. lugar. El objetivo final es 1,2,3,4,5 o (1) (2) (3) (4) (5), cinco ciclos disjuntos.
Si cambiamos dos elementos de diferentes ciclos, digamos 1 y 3, entonces obtenemos: 5,1,4,2,3 y en notación de ciclo (1,5,3,4,2). Los dos ciclos se unen en un ciclo, esto es lo opuesto a lo que queremos hacer.
Si cambiamos dos elementos del mismo ciclo, digamos 3 y 4, obtenemos: 5,4,3,2,1 en notación de ciclo (5,1) (2,4) (3). El ciclo único se divide en dos ciclos más pequeños. Esto nos acerca al objetivo de todos los ciclos de longitud 1. Observe que cualquier cambio de dos elementos en el mismo ciclo divide el ciclo en dos ciclos.
Si podemos descifrar el algoritmo óptimo para cambiar un ciclo, podemos aplicarlo para todos los ciclos y obtener un algoritmo óptimo para todo el género. Un algoritmo es tomar el elemento mínimo en el ciclo y cambiarlo por la posición en la que se encuentra. Entonces, para (3,4,2), cambiaríamos 2 por 4. Esto nos deja con un ciclo de longitud 1 (el elemento simplemente cambió a la posición correcta) y un ciclo de tamaño uno más pequeño que antes. Entonces podemos aplicar la regla nuevamente. Este algoritmo cambia la longitud del ciclo del elemento más pequeño -1 veces y cada otro elemento una vez.
Para transformar un ciclo de longitud n en ciclos de longitud 1 se requieren n - 1 operaciones. Cada elemento debe ser operado al menos una vez (piense en cada elemento a clasificar, debe moverse a su posición correcta). El algoritmo que propuse opera en cada elemento una vez, lo que todos los algoritmos deben hacer, luego cada otra operación se realizó en el elemento mínimo. Ningún algoritmo puede hacerlo mejor.
Este algoritmo toma O (n log n) para ordenar luego O (n) para mezclar ciclos. La resolución de un ciclo toma O (duración del ciclo), la longitud total de todos los ciclos es n, por lo que el costo de las operaciones del ciclo es O (n). El tiempo de ejecución final es O (n log n).
Tiene la idea correcta, pero se ha perdido un truco. (No publicarlo como respuesta porque el póster original solo quería una pista). Aquí hay una sugerencia para * usted * - vea cómo ordenar (1 8 9 7 6) con un costo de solo 41, no 42 :-) [Sugerencia: tiene que usar el 1 aunque esté en el lugar correcto.] – ShreevatsaR
El caso 18976 presenta la excepción cubierta en mi solución, en el sentido de que un número "temp" suficientemente pequeño es más eficiente de usar para intercambiar otros números individualmente que usar un un número extra individual de un ciclo dos veces, en algunos casos. – Sparr
También falla para 8 4 5 3 2 7 o incluso 3 1 2. Esta respuesta minimiza el número de intercambios, pero no las sumas. – xan