Ordenamiento Desordenado (Oro)

Pensando en las oportunidades profesionales a largo plazo más allá de la granja, la vaca Bessie ha comenzado a aprender algoritmos en varios sitios web de programación en línea.

Su algoritmo favorito hasta ahora es el "bubble sort". Aquí está la implementación inicial de Bessie, en código vacuno, para ordenar un arreglo $A$ de longitud $n$:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Al parecer, el comando "moo" en código vacuno no hace nada excepto imprimir "moo". Curiosamente, Bessie insiste en incluirlo en varios lugares de su código.

Después de probar su código en varios arreglos, Bessie hace una observación interesante: mientras que los elementos grandes se mueven al final del arreglo muy rápidamente, los elementos pequeños pueden tardar mucho tiempo en "burbujear" hacia el frente (ella sospecha que así es como el algoritmo obtuvo su nombre). Para aliviar este problema, Bessie modifica su código de manera que cada iteración del bucle principal recorra el arreglo hacia adelante y luego hacia atrás, dando tanto a los elementos grandes como a los pequeños la oportunidad de moverse largas distancias en una sola iteración. Su código ahora se ve así:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = n-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         sorted = false

Dado el arreglo de entrada, predice cuántas veces el código modificado de Bessie imprimirá "moo".