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
| algorytm | idea | złożoność |
|---|---|---|
| bąbelkowe | zamiana sąsiednich niepasujących | |
| przez wybieranie | wybór minimum z reszty | |
| przez wstawianie | wstawianie do posortowanej części | , ale dla prawie posortowanych |
| przez scalanie | dziel i łącz (stabilne) | |
| szybkie (quicksort) | podział względem pivota | średnio |
Wyszukiwanie binarne
W posortowanej tablicy porównaj szukany element ze środkiem i odrzuć połowę. Złożoność .
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ść .
Gotowy na sprawdzian z działu?
Wygeneruj krótki test z tego działu w generatorze.