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.