Porządek i szukanie
Wstęp do działu
Połowa pracy wszystkich komputerów świata sprowadza się do dwóch czynności: znaleźć coś i uporządkować coś. Wyszukiwarka znajduje strony, bank znajduje Twoje konto, gra znajduje przeciwnika w rankingu — a wszystko to działa błyskawicznie tylko dlatego, że dane są wcześniej posortowane. Sortowanie i wyszukiwanie to siostrzane rzemiosła: porządek kosztuje, ale zwraca się przy każdym kolejnym szukaniu.
Ten dział to także pierwsze prawdziwe derby algorytmów: dla jednego problemu poznasz kilka konkurencyjnych rozwiązań i nauczysz się je zestawiać jak zawodnik ów — kto ile porównań, kto ile pamięci, kto pada na jakich danych. Tu właśnie zamieni się w narzędzie to, co w 1.5 było intuicją: policzysz koszty bąbelkowego i scalania, zobaczysz przepaść między $n^2$ a $n \log n$, a w rozszerzeniu dostaniesz zawodowy język do mówienia o tych przepaściach — notację, którą informatycy całego świata opisują tempo wzrostu. Zgadywanka z działu 1 wróci jako pełnoprawny algorytm, a Gauss z 1.5 będzie miał godnego następcę.
Mapa pojęć działu
PORZĄDEK I SZUKANIE
|
┌─────────────────────┴──────────────────────┐
SZUKANIE SORTOWANIE
liniowe (n) bąbelkowe (n²)
[R] + wartownik przez wstawianie (n²,
binarne (log n) ─── wymaga porządku! ───► szybkie na prawie-
posortowanych)
| [R] scalanie (n log n)
KTÓRY LEPSZY? → licz koszty [R] szybkie (n log n śr.)
[R] notacja O [R] lider, idol, min-max
Jednostki w tym dziale
- 6.1 Wyszukiwanie liniowe (w rozszerzeniu: wartownik)
- 6.2 Wyszukiwanie binarne — połowienie na tablicy
- 6.3 Sortowanie bąbelkowe
- 6.4 Sortowanie przez wstawianie
- 6.5 Który szybszy? — porównywanie algorytmów (w rozszerzeniu: notacja O)
- 6.6 Sortowanie przez scalanie (rozszerzenie)
- 6.7 Sortowanie szybkie (rozszerzenie)
- 6.8 Lider, idol i min-max za jednym przejściem (rozszerzenie)