Controllare Uno per Uno
Ricerca Lineare: Controlla Uno per Uno
Immagina di avere 10 carte coperte, numerate da 1 a 10, mescolate in ordine casuale.
Vuoi trovare la carta con il numero 7.
Scopri le carte una per una, da sinistra a destra, finché non la trovi.
| Scenario | Scoperte necessarie |
|---|---|
| Caso migliore | 1 scoperta (fortuna, al primo tentativo!) |
| Caso peggiore | 10 scoperte (era l'ultima carta) |
| Media | circa 5 scoperte |
Ora immagina 100 carte. Media: circa 50 scoperte.
1.000 carte? Media: circa 500 scoperte.
Vedi il modello? Raddoppia le carte, raddoppia il lavoro. Il lavoro cresce in linea retta.
I ricercatori di informatica chiamano questo ricerca lineare — lineare significa che il lavoro cresce come una linea: costante e prevedibile.
La ricerca lineare funziona su QUALUNQUE lista, ordinata o no. Questo la rende semplice. Ma può diventare lenta.
Quanti Nomi?
Hai una lista di classe di 20 nomi scritti in ordine casuale.
Devi trovare il nome Zoe.
Controlli i nomi uno per uno, dall'inizio della lista verso il basso.
Dividi la Lista a Metà
Ricerca Binaria: Salta al Centro
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 usare la ricerca binaria.
Come funziona: apri al nome di mezzo (nome #10). Chiedi: Zoe viene prima o dopo questo nome?
Z è verso la fine dell'alfabeto, quindi Zoe viene DOPO il mezzo. Butta via la prima metà. Ora hai solo i nomi 11-20.
Controlla il mezzo di quei 10 nomi (nome #15). Z viene dopo M, quindi Zoe viene dopo il nome #15. Butta via i nomi 11-14. Ora hai i nomi 16-20.
Continua a dividere a metà. Ogni controllo rimuove metà dei nomi rimasti.
| Dimensione della lista | Max controlli con ricerca binaria |
|---|---|
| 20 nomi | al massimo 5 controlli |
| 1.000 nomi | al massimo 10 controlli |
| 1.000.000 nomi | al massimo 20 controlli |
Confronta con la ricerca lineare su 1.000.000 nomi: una media di 500.000 controlli.
La ricerca binaria divida la lista a metà ogni volta. Dividere a metà ripetutamente raggiunge 1 molto velocemente — ecco perché rimane così veloce.
Trova 'fig' in una Lista Ordinata
Ecco una lista ordinata di 8 parole:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Vuoi trovare fig usando la ricerca binaria.
Ricorda: controlla il mezzo, chiedi se il tuo obiettivo viene prima o dopo, poi dividi la lista a metà.
Scambia i Vicini in Ordine
Ordinamento a Bolle: Confronta i Vicini e Scambia
L'ordinamento a bolle mette in ordine una lista confrontando due elementi vicini alla volta.
Se due vicini sono fuori ordine — scambiali.
Continua a fare passaggi attraverso la lista finché non c'è nulla da scambiare.
Esempio: ordina [5, 3, 8, 1]
Passaggio 1:
- Confronta 5 e 3. 5 > 3, quindi scambia → [3, 5, 8, 1]
- Confronta 5 e 8. 5 < 8, nessuno scambio → [3, 5, 8, 1]
- Confronta 8 e 1. 8 > 1, quindi scambia → [3, 5, 1, 8]
Passaggio 2:
- Confronta 3 e 5. OK → [3, 5, 1, 8]
- Confronta 5 e 1. 5 > 1, scambia → [3, 1, 5, 8]
- Confronta 5 e 8. OK → [3, 1, 5, 8]
Passaggio 3:
- Confronta 3 e 1. 3 > 1, scambia → [1, 3, 5, 8]
- Confronta 3 e 5. OK. Confronta 5 e 8. OK.
Fatto! [1, 3, 5, 8] ✓
Nota: il numero più grande risale alla fine della lista in ogni passaggio. Ecco come l'ordinamento a bolle prende il suo nome.
L'ordinamento a bolle funziona. Non è il più veloce per liste grandi, ma è facile da capire — perfetto per imparare.
Ordina [4, 2, 7, 1] con l'Ordinamento a Bolle
Ordina questa lista usando l'ordinamento a bolle: [4, 2, 7, 1]
Mostra la lista dopo ogni passaggio. Conta quanti passaggi occorrono per finire.