Considere el siguiente 'juego'. tienes una lista de$N$números enteros ordenados en orden descendente de$N$a$1$. El objetivo del juego es ordenar la lista de nuevo en orden ascendente.

Normas:

• Solo puede comparar 2 números a la vez.

• Al comparar dos números en la lista, si$n_i$Es mas grande que$n_j$(dónde$i$<$j$) entonces$n_j$se mueve 'arriba' en la lista a$n_{j-1}$.

• De lo contrario, no hay cambio.

Mi intuición me dice que la cantidad mínima de movimientos necesarios para reordenar la lista en orden ascendente es la misma que la cantidad de movimientos que requiere un algoritmo de clasificación de burbujas. Esta lista de enteros de$N$a$1$es la peor posición inicial posible para una ordenación de burbujas, por lo que requeriría$N^2$se mueve ¿Estoy en lo correcto?

Cuando las comparaciones se eligen al azar

La pregunta anterior sobre el número mínimo de movimientos se aplica cuando puedes elegir qué 2 números comparar y el orden en el que eliges los pares de números para comparar. Pero, ¿qué pasa si extiendo la pregunta para decir que no tienes elección sobre cómo se hacen las comparaciones? Es decir,$i$y$j$(es decir, los índices que estamos comparando) se eligen aleatoriamente en cada movimiento (aunque$i$<$j$todavía se aplica). ¿Hay alguna forma de calcular cuánto tiempo tomaría en promedio volver a una lista ordenada ascendente? ¿Hay alguna manera de demostrar que se necesitaría un número finito de movimientos? Además, ¿cómo depende el tiempo que tarda en$N$? Este parece un problema realmente interesante, ¿se ha estudiado antes?

Resultados de la simulación

He intentado escribir un código para investigar esto. por ejemplo, para$N=10$, toma mi script (que usa un generador de números aleatorios para elegir los índices$i$y$j$para comparar) alrededor de 350 movimientos para alcanzar el orden ascendente. Como referencia, calculé el 'ordenamiento' usando la fórmula de esta respuesta: https://math.stackexchange.com/a/3201037/668220 .

Pero para$N=30$se necesitan alrededor de 10,000 movimientos

Para$N=100$parece tomar más de 100,000 movimientos

Me interesaría mucho saber si hay una manera de describir matemáticamente este comportamiento.