Kontrollera En Vid En Gång
Linjär Sökning: Kontrollera Varje En
Föreställ dig att du har 10 kort liggande vända ner, numrerade 1 till 10, rufflade i slumpordning.
Du vill hitta kortet med numret 7.
Du vänder upp korten en och en, från vänster till höger, tills du hittar det.
| Scenario | Vänd Och Klicka Behövs |
|----------|----------------------|
| Bästa Fall | 1 vänd och klicka (lyckad första försöket!) |
| Värsta Fall | 10 vänd och klicka (det var det sista kortet) |
| Genomsnitt | cirka 5 vänd och klicka |
Nu föreställ dig 100 kort. Genomsnitt: cirka 50 vänd och klicka.
1,000 kort? Genomsnitt: cirka 500 vänd och klicka.
Ser du mönstret? Dubblera antalet kort, dubblera arbetet. Arbetet ökar i en rak linje.
Datavetare kallar det här för linjär sökning - linjär innebär att arbetet ökar som en linje: stadig och förutsägbar.
Linjär sökning fungerar på NÅGON lista, ordnad eller inte. Det gör att det är 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 en och en, från toppen av listan ner.
Klipp listan på mitten
Binärsök: Hoppa till mitten
Binärsök har en regel: listan måste vara sorterad först.
Om ditt lista med 20 namn går från A till Z kan du använda binärsök.
Hur det fungerar: öppna på mitten namnet (namn #10). Fråga: är Zoe före eller efter detta namn?
Z kommer nära slutet av alfabetet, så Zoe kommer EFTER mitten. Kasta bort den första halvan. 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.
Fort-sätta klippa i halvorna. Varje kontroll tar bort hälften av de kvarvarande namnen.
| Liststorlek | Max kontroller med binärsök |
|-----------|-------------------------------|
| 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ärt sök på 1,000,000 namn: genomsnittligt 500,000 kontroller.
Binärsök klipper listan i halvor varje gång. Att klippa i halvor upprepade gånger når 1 mycket snabbt - det är varför det fortsätter vara så snabbt.
Hitta 'fig' i ett Sorterat Lista
Här är ett sorterat lista med 8 ord:
1. äpple 2. banan 3. hallon 4. dat 5. ädelgran 6. fig 7. grape 8. honungsmel
Du vill hitta fig med hjälp av binärsök.
Kom ihåg: kontrollera mitten, fråga om din målkomponent kommer före eller efter, och klipp sedan listan i halvor.
Byt Plats med Grannar för att Ordna
Bubblsortera: Jämför Grannar & Byt Plats
Bubblsort ordnar en lista genom att jämföra två grannposter åt gången.
Om två grannposter är ur ordning — byt plats.
Fortfarande göra genomgångar genom listan tills ingenting behöver bytas plats.
Exempel: sortera [5, 3, 8, 1]
Gång 1:
- Jämför 5 & 3. 5 > 3, så byt → [3, 5, 8, 1]
- Jämför 5 & 8. 5 < 8, ingen byt → [3, 5, 8, 1]
- Jämför 8 & 1. 8 > 1, så byt → [3, 5, 1, 8]
Gång 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]
Gång 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.
Färdigt! [1, 3, 5, 8] ✓
Observera: det största talet bubblar till slutet av listan på varje gång. Det är så bubblsort får sitt namn.
Bubblsort fungerar. Det är inte snabbast för stora listor, men det är lätt att förstå — perfekt för att lära sig.
Sortera [4, 2, 7, 1] med Bubblsort
Sortera denna lista med bubblsort: [4, 2, 7, 1]
Visa listan efter varje pass. Räkna hur många genomgångar det tar att slutföra.