Kuplajärjestäminen

Kuplajärjestäminen on järjestämisalgoritmi, joka koostuu vaihtelevasta määrästä kierroksia. Yhdellä kierroksella lista käydään läpi vasemmalta oikealle ja vierekkäisten lukujen paikkoja vaihdetaan keskenään, mikäli oikeanpuolimmainen on pienempi kuin vasemmanpuolimmainen. Kierroksia suoritetaan, kunnes lista on järjestyksessä.

Kuplajärjestäminen voidaan toteuttaa Pythonilla näin:

def bubble(t):
    while True:
        change = False
        for i in range(len(t)-1):
            if t[i] > t[i+1]:
                t[i], t[i+1] = t[i+1], t[i]
                change = True
        if not change:
            break

Annettuna on lista, jossa on jokin lukujen $1 \dots n$ permutaatio, ja tehtäväsi on selvittää, montako kierrosta kuplajärjestämisalgoritmi tarvitsee listan järjestämiseen. Huomaa, että tässä lasketaan vain kierrokset, joiden aikana listan järjestys muuttuu.

Voit olettaa, että listalla on enintään $10^5$ lukua. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.

Toteuta tiedostoon bubble.py funktio count, joka ilmoittaa, montako kierrosta kuplajärjestäminen tarvitsee listan järjestämiseen.

def count(t):
    # TODO

if __name__ == "__main__":
    print(count([1, 2, 3])) # 0
    print(count([2, 3, 4, 1])) # 3
    print(count([5, 1, 2, 3, 4])) # 1
    print(count([6, 2, 4, 1, 5, 3])) # 3
    print(count([2, 7, 4, 1, 9, 3, 8, 6, 5, 10])) # 4

Selitys: Lista $[1, 2, 3]$ on jo valmiiksi järjestyksessä, joten kierroksia ei tarvita lainkaan. Listan $[2, 3, 4, 1]$ järjestämiseen tarvitaan $3$ kierrosta: $[2, 3, 4, 1]$ $\rightarrow$ $[2, 3, 1, 4]$ $\rightarrow$ $[2, 1, 3, 4]$ $\rightarrow$ $[1, 2, 3, 4]$. Listan $[5, 1, 2, 3, 4]$ järjestämiseen riittää yksi kierros, sillä kun vierekkäisten alkioiden paikkoja vaihdetaan siirtyy luku $5$ aina askeleen oikealle ja päätyy listan loppuun jo ensimmäisellä kierroksella.