Kontrollera en åt gången
Linjär sökning: Kontrollera varje en
Föreställ dig att du har 10 kort vänd nedåt, numrerade 1 till 10, blandade i slumpmässig ordning.
Du vill hitta kortet med numret 7.
Du vänder kort ett efter ett, från vänster till höger, tills du hittar det.
| Scenario | Vändningar behövs |
|---|---|
| Bästa fall | 1 vändning (lyckad första försöket!) |
| Värsta fall | 10 vändningar (det var det sista kortet) |
| Genomsnitt | ungefär 5 vändningar |
Föreställ dig nu 100 kort. Genomsnitt: ungefär 50 vändningar.
1 000 kort? Genomsnitt: ungefär 500 vändningar.
Se mönstret? Dubbla korten, dubbla arbetet. Arbetet växer i en rät linje.
Dataloger kallar detta linjär sökning — linjär betyder att arbetet växer som en linje: stadigt & förutsägbar.
Linjär sökning fungerar på VILKEN lista som helst, sorterad eller inte. Det gör det enkelt. Men det kan bli långsamt.
Hur många namn?
Du har en klasslista med 20 namn skrivna i slumpmässig ordning.
Du behöver hitta namnet Zoe.
Du kontrollerar namn ett efter ett, från början av listan nedåt.
Halvera listan
Binär sökning: Hoppa till mitten
Binär sökning har en regel: listan måste redan vara sorterad.
Om din lista med 20 namn går från A till Z, kan du använda binär sökning.
Så fungerar det: öppna i mitten av namn (namn #10). Fråga: kommer Zoe före eller efter detta namn?
Z kommer nära slutet av alfabetet, så Zoe kommer EFTER mitten. Kasta bort första hälften. Nu har du bara namn 11-20 kvar.
Kontrollera mitten av dessa 10 namn (namn #15). Z kommer efter M, så Zoe kommer efter namn #15. Kasta bort namn 11-14. Nu har du namn 16-20.
Fortsätt halvera. Varje kontroll tar bort hälften av de återstående namnen.
| Liststorlek | Maximalt kontroller med binär sökning |
|---|---|
| 20 namn | högst 5 kontroller |
| 1 000 namn | högst 10 kontroller |
| 1 000 000 namn | högst 20 kontroller |
Jämför det med linjär sökning på 1 000 000 namn: ett genomsnitt på 500 000 kontroller.
Binär sökning halverar listan varje gång. Att halvera upprepade gånger når 1 mycket snabbt — det är därför det förblir så snabbt.
Hitta 'fig' i en sorterad lista
Här är en sorterad lista med 8 ord:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Du vill hitta fig med binär sökning.
Kom ihåg: kontrollera mitten, fråga om ditt mål kommer före eller efter, halvera sedan listan.
Byta grannar i ordning
Bubbelsortering: Jämför grannar & byt
Bubbelsortering ordnar en lista genom att jämföra två närliggande objekt åt gången.
Om två grannar är felordnade — byt dem.
Fortsätt göra pass genom listan tills ingenting behöver bytas.
Exempel: sortera [5, 3, 8, 1]
Pass 1:
- Jämför 5 & 3. 5 > 3, så byt → [3, 5, 8, 1]
- Jämför 5 & 8. 5 < 8, ingen byte → [3, 5, 8, 1]
- Jämför 8 & 1. 8 > 1, så byt → [3, 5, 1, 8]
Pass 2:
- Jämför 3 & 5. OK → [3, 5, 1, 8]
- Jämför 5 & 1. 5 > 1, byt → [3, 1, 5, 8]
- Jämför 5 & 8. OK → [3, 1, 5, 8]
Pass 3:
- Jämför 3 & 1. 3 > 1, byt → [1, 3, 5, 8]
- Jämför 3 & 5. OK. Jämför 5 & 8. OK.
Klar! [1, 3, 5, 8] ✓
Observera: det största numret bubblar till slutet av listan på varje pass. Det är hur bubbelsortering får sitt namn.
Bubbelsortering fungerar. Det är inte det snabbaste för stora listor, men det är lätt att förstå — perfekt för lärande.
Sortera [4, 2, 7, 1] med bubbelsortering
Sortera denna lista med bubbelsortering: [4, 2, 7, 1]
Visa listan efter varje pass. Räkna hur många pass det tar att avsluta.