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: breakAnnettuna 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])) # 4Selitys: 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.