Düzensizliklerden Kurtulmak (Altın)

Çiftlik dışındaki uzun vadeli kariyer fırsatlarını göz önünde bulundurarak, inek Bessie çeşitli çevrimiçi kodlama sitelerinde algoritma öğrenmeye başlamıştır.

Şimdiye kadarki favori algoritması "kabarcık sıralama" (bubble sort). İşte Bessie'nin $n$ uzunluğundaki bir $A$ dizisini sıralamak için inek-kodunda yazdığı ilk uygulaması:

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

Görünüşe göre, inek-kodundaki "moo" komutu "moo" yazdırmak dışında hiçbir şey yapmıyor. Tuhaf bir şekilde, Bessie kodunun çeşitli yerlerine bu komutu eklemekte ısrar ediyor.

Kodunu birkaç dizi üzerinde test ettikten sonra, Bessie ilginç bir gözlemde bulunur: büyük elemanlar dizinin sonuna çok hızlı bir şekilde taşınırken, küçük elemanların başa "kabarması" çok uzun zaman alabiliyor (bunun algoritmanın adını nereden aldığını açıklayan şey olduğundan şüpheleniyor). Bu sorunu hafifletmek için, Bessie kodunu ana döngünün her bir yinelemesinin diziyi önce ileri sonra geri taraması için değiştiriyor; bu sayede hem büyük hem de küçük elemanlara tek bir yinelemede uzun mesafeler kat etme şansı veriliyor. Kodu artık şöyle görünüyor:

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

Verilen giriş dizisi için, Bessie'nin değiştirilmiş kodunun kaç kez "moo" yazdıracağını tahmin edin.