Liczniki w sortowaniu przez wstawianie

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

Sortowanie przez wstawianie też porównuje i przenosi elementy, ale inaczej: każde porównanie `values[j] > x` kończy się albo **przesunięciem** elementu w prawo, albo zakończeniem wstawiania. Przesunięć jest tyle, ile inwersji (jak zamian w bąbelkowym), ale przesunięcie to jedno przypisanie, a zamiana dwa. Najważniejsza różnica: dla listy **posortowanej** każde wstawianie kończy się po jednym porównaniu, więc cała praca to `n - 1` porównań.

def insertion_stats(values):
    values = list(values)
    comparisons = 0
    shifts = 0
    for i in range(1, len(values)):
        x = values[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if values[j] > x:
                values[j + 1] = values[j]
                shifts += 1
                j -= 1
            else:
                break
        values[j + 1] = x
    return comparisons, shifts

print(insertion_stats([6, 2, 8, 4, 9, 1, 5]))
print(insertion_stats([1, 2, 3, 4, 5, 6, 7]))
print(insertion_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.