Liczniki porównań i zamian

Porównanie metod sortowania: liczba porównań i zamian - Informatyka - technikum klasa 1 (Python)

Żeby porównać algorytmy, liczy się **operacje**, a nie sekundy (czas zależy od komputera). W sortowaniu bąbelkowym liczą się dwie: **porównania** sąsiadów i **zamiany**. Wystarczą dwa liczniki zwiększane w odpowiednich miejscach pętli. Funkcja `bubble_stats` sortuje kopię listy (`list(values)`), żeby nie zmieniać danych, i zwraca parę liczb.

def bubble_stats(values):
    values = list(values)
    n = len(values)
    comparisons = 0
    swaps = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            comparisons += 1
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
                swaps += 1
    return comparisons, swaps

print(bubble_stats([7, 3, 9, 1, 5, 8, 2]))
print(bubble_stats([1, 2, 3, 4, 5, 6, 7]))
print(bubble_stats([7, 6, 5, 4, 3, 2, 1]))

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

Wszystkie lekcje kursu Informatyka - technikum klasa 1·Zaloguj się, aby zapisać postęp na koncie.