Dane prawie posortowane

Sortowanie przez wstawianie - Algorytmy z podstawy programowej (Python)

Gdy lista jest już prawie posortowana, wewnętrzna pętla prawie się nie wykonuje i algorytm działa w czasie bliskim liniowemu. Dla listy odwróconej każdy element wędruje na sam początek i liczba przesunięć jest największa: n(n-1)/2.

def wstawianie(dane):
    przesuniecia = 0
    for i in range(1, len(dane)):
        klucz = dane[i]
        j = i - 1
        while j >= 0 and dane[j] > klucz:
            dane[j + 1] = dane[j]
            j -= 1
            przesuniecia += 1
        dane[j + 1] = klucz
    return przesuniecia


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

Ł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.