Wersja z flagą: koniec, gdy nie było zamian

Sortowanie bąbelkowe - Algorytmy z podstawy programowej (Python)

Jeśli w całym przebiegu nie było ani jednej zamiany, lista jest już posortowana i dalsze przebiegi nic nie zmienią. Flaga `zamiana` pozwala wtedy przerwać pracę. Dla listy prawie posortowanej oszczędza to większość pracy.

def babelkowe(dane):
    n = len(dane)
    przebiegi = 0
    for i in range(n - 1):
        zamiana = False
        przebiegi += 1
        for j in range(n - 1 - i):
            if dane[j] > dane[j + 1]:
                dane[j], dane[j + 1] = dane[j + 1], dane[j]
                zamiana = True
        if not zamiana:
            break
    return przebiegi


lista = [1, 2, 3, 5, 4, 6, 7, 8]
print(babelkowe(lista), lista)
lista = [8, 7, 6, 5, 4, 3, 2, 1]
print(babelkowe(lista), lista)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.