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.