Nauka / Sortowanie i wyszukiwanie

Sortowanie i wyszukiwanie

Sortowanie bąbelkowe, przez wstawianie, przez scalanie, szybkie; wyszukiwanie binarne; złożoności.

Rozszerzony

Teoria, wzory i przykłady

Sortowanie

algorytmideazłożoność
bąbelkowezamiana sąsiednich niepasującychO(n2)O(n^2)
przez wybieraniewybór minimum z resztyO(n2)O(n^2)
przez wstawianiewstawianie do posortowanej częściO(n2)O(n^2), ale O(n)O(n) dla prawie posortowanych
przez scalaniedziel i łącz (stabilne)O(nlog⁡n)O(n\log n)
szybkie (quicksort)podział względem pivotaśrednio O(nlog⁡n)O(n\log n)

Wyszukiwanie binarne

W posortowanej tablicy porównaj szukany element ze środkiem i odrzuć połowę. Złożoność O(log⁡n)O(\log n).

l, p = 0, len(t) - 1
while l <= p:
    s = (l + p) // 2
    if t[s] == x: return s
    elif t[s] < x: l = s + 1
    else: p = s - 1
return -1

Wskazówki

Przed zastosowaniem wyszukiwania binarnego upewnij się, że dane są posortowane. Do sortowania w Pythonie używaj sorted() lub .sort() — złożoność O(nlog⁡n)O(n\log n).

Gotowy na sprawdzian z działu?
Wygeneruj krótki test z tego działu w generatorze.
Test działowy