# your code goes here
def bubble_sort(lista):
    n = len(lista)
    for i in range(n):
        # Flaga wskazująca, czy podczas tej iteracji była jakakolwiek zamiana
        swapped = False
        for j in range(0, n - i - 1):
            if lista[j] > lista[j + 1]:
                # Zamiana elementów, jeśli są w złej kolejności
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                swapped = True
        # Jeśli nie było zamian, lista jest już posortowana
        if not swapped:
            break
    return lista

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiBidWJibGVfc29ydChsaXN0YSk6CiAgICBuID0gbGVuKGxpc3RhKQogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgIyBGbGFnYSB3c2thenVqxIVjYSwgY3p5IHBvZGN6YXMgdGVqIGl0ZXJhY2ppIGJ5xYJhIGpha2Frb2x3aWVrIHphbWlhbmEKICAgICAgICBzd2FwcGVkID0gRmFsc2UKICAgICAgICBmb3IgaiBpbiByYW5nZSgwLCBuIC0gaSAtIDEpOgogICAgICAgICAgICBpZiBsaXN0YVtqXSA+IGxpc3RhW2ogKyAxXToKICAgICAgICAgICAgICAgICMgWmFtaWFuYSBlbGVtZW50w7N3LCBqZcWbbGkgc8SFIHcgesWCZWoga29sZWpub8WbY2kKICAgICAgICAgICAgICAgIGxpc3RhW2pdLCBsaXN0YVtqICsgMV0gPSBsaXN0YVtqICsgMV0sIGxpc3RhW2pdCiAgICAgICAgICAgICAgICBzd2FwcGVkID0gVHJ1ZQogICAgICAgICMgSmXFm2xpIG5pZSBiecWCbyB6YW1pYW4sIGxpc3RhIGplc3QganXFvCBwb3NvcnRvd2FuYQogICAgICAgIGlmIG5vdCBzd2FwcGVkOgogICAgICAgICAgICBicmVhawogICAgcmV0dXJuIGxpc3Rh