Controlla Uno alla Volta
Ricerca Lineare: Controlla Ogni Uno
Immagina di avere 10 carte con il dorso rivolto, numerate da 1 a 10, mescolate in un ordine casuale.
Vuoi trovare la carta con il numero 7.
Sollevi le carte uno alla volta, da sinistra a destra, fino a trovarla.
| Scenario | Flips needed |
|----------|-------------|
| Best case | 1 flip (lucky first try!) |
| Worst case | 10 flips (it was the last card) |
| Average | about 5 flips |
Ora immagina 100 carte. Media: circa 50 sollevamenti.
1000 carte? Media: circa 500 sollevamenti.
Vedi il pattern? Doppia il numero di carte, raddoppia il lavoro. Il lavoro cresce in linea retta.
I scienziati della computazione chiamano questo ricerca lineare - lineare significa che il lavoro cresce come una linea: costante e prevedibile.
La ricerca lineare funziona su QUALSIASI elenco, ordinato o meno. Questo lo rende semplice. Ma può diventare lento.
Quanti Nomidi?
Hai una lista di classe di 20 nomi scritti in ordine casuale.
Hai bisogno di trovare il nome Zoe.
Controlli i nomi uno alla volta, dalla parte superiore della lista verso il basso.
Taglia la lista a metà
Ricerca binaria: salta al mezzo
La ricerca binaria ha una regola: la lista deve essere ordinata per prima.
Se la tua lista di 20 nomi va da A a Z, puoi utilizzare la ricerca binaria.
Come funziona: apri alla posizione del nome centrale (nome #10). Domanda: Zoe è prima o dopo questo nome?
Z viene vicino alla fine dell'alfabeto, quindi Zoe viene DOPPIO del mezzo. Elimina la prima metà. Ora hai solo nomi da 11 a 20.
Controlla il mezzo di quei 10 nomi (nome #15). Z viene dopo M, quindi Zoe viene dopo il nome #15. Elimina i nomi da 11 a 14. Ora hai i nomi da 16 a 20.
Prosegui tagliando a metà. Ogni controllo elimina la metà dei nomi rimanenti.
Dimensione della lista | Massime verifiche con ricerca binaria |
|-----------|-------------------------------|
| 20 nomi | al massimo 5 verifiche |
| 1.000 nomi | al massimo 10 verifiche |
| 1.000.000 nomi | al massimo 20 verifiche |
Confrontalo con la ricerca lineare su 1.000.000 di nomi: in media, 500.000 verifiche.
La ricerca binaria riduce la lista a metà ogni volta. Tagliare a metà più volte raggiunge 1 molto rapidamente - questo è il motivo per cui rimane così veloce.
Trova 'fig' in una lista ordinata
Ecco una lista ordinata di 8 parole:
1. mela 2. banana 3. ciliegio 4. dattero 5. lamponi 6. fico 7. uva 8. melone
Vuoi trovare fig utilizzando la ricerca binaria.
Ricorda: controlla il mezzo, chiedi se il tuo obiettivo viene prima o dopo, poi taglia la lista a metà.
Scambia i vicini per l'ordine
Ordinamento a bolle: confronta i vicini e scambia
La bubble sort ordina una lista confrontando due elementi adiacenti alla volta.
Se due vicini sono fuori ordine - scambiarli.
Continua a fare passaggi attraverso la lista fino a quando non è necessario alcun ulteriore scambio.
Esempio: ordinare [5, 3, 8, 1]
Passaggio 1:
- Confronta 5 & 3. 5 > 3, quindi scambia → [3, 5, 8, 1]
- Confronta 5 & 8. 5 < 8, nessun scambio → [3, 5, 8, 1]
- Confronta 8 & 1. 8 > 1, quindi scambia → [3, 5, 1, 8]
Passaggio 2:
- Confronta 3 & 5. OK → [3, 5, 1, 8]
- Confronta 5 & 1. 5 > 1, scambia → [3, 1, 5, 8]
- Confronta 5 & 8. OK → [3, 1, 5, 8]
Passaggio 3:
- Confronta 3 & 1. 3 > 1, scambia → [1, 3, 5, 8]
- Confronta 3 & 5. OK. Confronta 5 & 8. OK.
Fatto! [1, 3, 5, 8] ✓
Nota: il numero più grande si gonfia (bubbles) alla fine della lista in ogni passaggio. Questo è il motivo per cui la bubble sort prende il suo nome.
La bubble sort funziona. Non è il più veloce per le grandi liste, ma è facile da comprendere - perfetto per l'apprendimento.
Ordina [4, 2, 7, 1] con Bubble Sort
Ordina questa lista utilizzando bubble sort: [4, 2, 7, 1]
Mostra la lista dopo ogni passo. Conta quante volte è necessario per finire.