Sprawdzanie jednego po drugim
Szybka poszukiwanie: Sprawdź każdego
Wyobraź sobie, że masz 10 kart odkrytych, z numerami od 1 do 10, wymieszanych w losowej kolejności.
Chcesz znaleźć kartę z numerem 7.
Odkrywasz karty jeden po drugim, od lewej do prawej, aż znajdziesz ją.
| Scenariusz | Potrzebne obroty |
|----------|-------------|
| Najlepszy przypadek | 1 obrót (szczęśliwy pierwszy raz!) |
| Najgorszy przypadek | 10 obrotów (była to ostatnia karta) |
| Średni | około 5 obrotów |
Teraz wyobraź sobie 100 kart. Średnio: około 50 obrotów.
1000 kart? Średnio: około 500 obrotów.
Zobacz wzorzec? Podwajając karty, podwajamy pracę. Praca rośnie w prostoliniowej.
Inżynierowie komputerowi nazywają to szybkie poszukiwanie - liniowe oznacza, że praca rośnie jak linia: stała & przewidywalna.
Szybka poszukiwanie działa na dowolnej liście, posortowanej lub nie. To sprawia, że jest proste. Ale może być powolne.
Ile nazwisk?
Masz listę klasową 20 nazwisk napisanych w losowej kolejności.
Potrzebujesz znaleźć nazwisko Zoe.
Sprawdzasz nazwiska jeden po drugim, od góry listy w dół.
Podziel listę na połowę
Szukanie binarne: skocz do środka
Szukanie binarne ma jedno przepisane: **lista musi być posortowana najpierw.
Jeśli lista 20 nazw idzie od A do Z, możesz użyć szukania binarnego.
Jak to działa: otwórz na środkowej nazwie (nazwie #10). Zapytaj: czy Zoe jest przed lub po tej nazwie?
Z pochodzi na końcu alfabetu, więc Zoe jest PO środku. Wyrzuć pierwszą połowę. Teraz masz tylko nazwy od 11 do 20.
Sprawdź środek tych 10 nazw (nazwa #15). Z pochodzi po M, więc Zoe pochodzi po nazwie #15. Wyrzuć nazwy od 11 do 14. Teraz masz nazwy od 16 do 20.
Krok po kroku dziel na połowy. Każde sprawdzenie usuwa połowę pozostałych nazw.
Rozmiar listy | Maksymalna liczba sprawdzeń za pomocą szukania binarnego |
|-----------|-------------------------------|
| 20 nazw | nie więcej niż 5 sprawdzeń |
| 1,000 nazw | nie więcej niż 10 sprawdzeń |
| 1,000,000 nazw | nie więcej niż 20 sprawdzeń |
Porównaj to z liniowym szukaniem w 1,000,000 nazw: średnio 500,000 sprawdzeń.
Szukanie binarne dzieli listę na połowę każdorazowo. Dzielenie na pół wielokrotnie prowadzi do 1 bardzo szybko - to jest dlaczego pozostaje tak szybkie.
Znajdź 'fig' w posortowanej liście
Oto posortowana lista 8 słów:
1. jabłko 2. banan 3. malina 4. datek 5. jeżyna 6. fig 7. wino 8. ananas
Chcesz znaleźć fig przy użyciu szukania binarnego.
Pamiętaj: sprawdź środek, zapytaj, czy Twoja cel pochodzi przed lub po, a następnie podziel listę na połowę.
Zamiana sąsiadów w porządku
Sortowanie pętli bąbelkowej: porównaj sąsiadów i zamień
Bubble sort umieszcza listę w porządku, porównując dwie sąsiednie elementy jednocześnie.
Jeśli dwóch sąsiadów jest nieuporządkowanych — zamień je.
Zróńczaj kolejne przejścia przez listę, aż niczego nie będzie trzeba wymieniać.
Przykład: posortuj [5, 3, 8, 1]
Przejście 1:
- Porównaj 5 & 3. 5 > 3, więc zamień → [3, 5, 8, 1]
- Porównaj 5 & 8. 5 < 8, nie zamień → [3, 5, 8, 1]
- Porównaj 8 & 1. 8 > 1, więc zamień → [3, 5, 1, 8]
Przejście 2:
- Porównaj 3 & 5. OK → [3, 5, 1, 8]
- Porównaj 5 & 1. 5 > 1, zamień → [3, 1, 5, 8]
- Porównaj 5 & 8. OK → [3, 1, 5, 8]
Przejście 3:
- Porównaj 3 & 1. 3 > 1, zamień → [1, 3, 5, 8]
- Porównaj 3 & 5. OK. Porównaj 5 & 8. OK.
Zrobione! [1, 3, 5, 8] ✓
Uwaga: największa liczba wypływa na koniec listy w każdym przejściu. To dlatego bubble sort nazywa się tak.
Bubble sort działa. Nie jest najbardziej szybkim dla dużych list, ale jest łatwy do zrozumienia — idealny do nauki.
Posortuj [4, 2, 7, 1] za pomocą Bubble Sort
Posortuj tę listę za pomocą bubble sort: [4, 2, 7, 1]
Pokaż listę po każdym przejściu. Licz, ile przejść zajęło to zrobienie.