Liczba porównań i zamian

Sortowanie przez wybieranie - Algorytmy z podstawy programowej (Python)

Sortowanie przez wybieranie zawsze wykonuje tyle samo porównań: n(n-1)/2, niezależnie od danych. Zamian jest za to najwyżej n-1, co bywa zaletą, gdy przestawianie elementów jest kosztowne. Złożoność czasowa to O(n²).

def sortuj(dane):
    porownania = 0
    zamiany = 0
    n = len(dane)
    for i in range(n - 1):
        min_i = i
        for j in range(i + 1, n):
            porownania += 1
            if dane[j] < dane[min_i]:
                min_i = j
        if min_i != i:
            dane[i], dane[min_i] = dane[min_i], dane[i]
            zamiany += 1
    return porownania, zamiany


print(sortuj([5, 4, 3, 2, 1]))
print(sortuj([1, 2, 3, 4, 5]))

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