Sprawdzanie jeden po drugim
Wyszukiwanie liniowe: sprawdź każdy element
Wyobraź sobie, że masz 10 kart odwróconych, ponumerowanych od 1 do 10, potasowanych w losowej kolejności.
Chcesz znaleźć kartę z numerem 7.
Odwracasz karty jeden po drugim, od lewej do prawej, aż go znajdziesz.
| Scenariusz | Potrzebnych odwróceń |
|---|---|
| Najlepszy przypadek | 1 odwrócenie (szczęśliwy pierwszy raz!) |
| Najgorszy przypadek | 10 odwróceń (to była ostatnia karta) |
| Średnio | około 5 odwróceń |
Teraz wyobraź sobie 100 kart. Średnio: około 50 odwróceń.
1000 kart? Średnio: około 500 odwróceń.
Widzisz wzór? Podwójne karty, podwójna praca. Praca rośnie w linii prostej.
Informatycy nazywają to wyszukiwaniem liniowym — liniowe oznacza, że praca rośnie jak linia: stała & przewidywalna.
Wyszukiwanie liniowe działa na KAŻDEJ liście, posortowanej lub nie. To czyni ją prostą. Ale może być powolna.
Ile nazwisk?
Masz listę klasy z 20 nazwiskami napisaną w losowej kolejności.
Musisz znaleźć nazwisko Zoe.
Sprawdzasz nazwiska jeden po drugim, od góry listy w dół.
Podziel listę na połowę
Wyszukiwanie binarne: przeskocz do środka
Wyszukiwanie binarne ma jedną regułę: lista musi być najpierw posortowana.
Jeśli twoja lista 20 nazwisk idzie od A do Z, możesz użyć wyszukiwania binarnego.
Jak to działa: otwórz nazwisko w środku (nazwisko #10). Zapytaj: czy Zoe jest przed czy po tym nazwiskiem?
Z pojawia się blisko końca alfabetu, więc Zoe pojawia się PO środku. Odrzuć pierwszą połowę. Teraz masz tylko nazwiska 11-20.
Sprawdź środek tych 10 nazwisk (nazwisko #15). Z pojawia się po M, więc Zoe pojawia się po nazwiskiem #15. Odrzuć nazwiska 11-14. Teraz masz nazwiska 16-20.
Ciągle dziel na połowę. Każde sprawdzenie usuwa połowę pozostałych nazwisk.
| Rozmiar listy | Maks. sprawdzenia z wyszukiwaniem binarnym |
|---|---|
| 20 nazwisk | co najwyżej 5 sprawdzeń |
| 1000 nazwisk | co najwyżej 10 sprawdzeń |
| 1000000 nazwisk | co najwyżej 20 sprawdzeń |
Porównaj to z wyszukiwaniem liniowym na 1000000 nazwisk: średnio 500000 sprawdzeń.
Wyszukiwanie binarne dzieli listę na połowę każdym razem. Wielokrotne dzielenie na połowę osiąga 1 bardzo szybko — dlatego pozostaje tak szybko.
Znajdź 'fig' na posortowanej liście
Oto posortowana lista 8 słów:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Chcesz znaleźć fig używając wyszukiwania binarnego.
Pamiętaj: sprawdź środek, zapytaj, czy twój cel pojawia się przed czy po, a następnie podziel listę na połowę.
Zamienianie sąsiadów w porządek
Sortowanie bąbelkowe: porównaj sąsiadów i zamień
Sortowanie bąbelkowe porządkuje listę, porównując dwa sąsiadujące elementy na raz.
Jeśli dwaj sąsiedzi są poza porządkiem — zamień ich.
Ciągle przechodzisz przez listę, aż nic nie będzie wymagało zamiany.
Przykład: posortuj [5, 3, 8, 1]
Przejście 1:
- Porównaj 5 i 3. 5 > 3, więc zamień → [3, 5, 8, 1]
- Porównaj 5 i 8. 5 < 8, bez zamiany → [3, 5, 8, 1]
- Porównaj 8 i 1. 8 > 1, więc zamień → [3, 5, 1, 8]
Przejście 2:
- Porównaj 3 i 5. OK → [3, 5, 1, 8]
- Porównaj 5 i 1. 5 > 1, zamień → [3, 1, 5, 8]
- Porównaj 5 i 8. OK → [3, 1, 5, 8]
Przejście 3:
- Porównaj 3 i 1. 3 > 1, zamień → [1, 3, 5, 8]
- Porównaj 3 i 5. OK. Porównaj 5 i 8. OK.
Gotowe! [1, 3, 5, 8] ✓
Zauważ: największa liczba wynurza się na koniec listy z każdym przejściem. Tak sortowanie bąbelkowe otrzymuje swoją nazwę.
Sortowanie bąbelkowe działa. Nie jest najszybsze dla dużych list, ale jest łatwe do zrozumienia — idealne do nauki.
Posortuj [4, 2, 7, 1] sortowaniem bąbelkowym
Posortuj tę listę używając sortowania bąbelkowego: [4, 2, 7, 1]
Pokaż listę po każdym przejściu. Policz ile przejść zajmuje ukończenie.