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.
| Scenari | Volte necessarie |
|----------|-----------------|
| Migliore ipotesi | 1 volta (fortuna, primo tentativo!) |
| Peggiore ipotesi | 10 volte (era l'ultima carta) |
| Media | circa 5 volte |
Ora immagina 100 carte. Media: circa 50 volte.
1000 carte? Media: circa 500 volte.
Vedi il pattern? Doppia il numero di carte, raddoppia il lavoro. Il lavoro cresce in modo rettilineo.
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 ELLEN LISTE, ordinate o meno. Questo rende più semplice. Ma può diventare lento.
Quanti Nomidi?
Hai una lista di classifica 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 mezzo nome (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-20.
Controlla il mezzo di quei 10 nomi (nome #15). Z viene dopo M, quindi Zoe viene dopo il nome #15. Elimina i nomi 11-14. Ora hai i nomi 16-20.
Continua a tagliare 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 |
Confronta questo con la ricerca lineare su 1.000.000 di nomi: una media di 500.000 verifiche.
La ricerca binaria riduce la lista a metà ogni volta. Tagliare a metà ripetutamente 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, quindi taglia la lista a metà.
Scambio dei vicini in ordine
Bubble Sort: Confronta vicini & Scambia
La bubble sort mette in ordine una lista confrontando due elementi vicini uno all'altro.
Se due vicini sono fuori ordine - scambiali.
Continua a fare passaggi attraverso la lista fino a quando non è necessario alcun scambio.
Esempio: ordinare [5, 3, 8, 1]
Passo 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]
Passo 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]
Passo 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 la bubble sort: [4, 2, 7, 1]
Mostra la lista dopo ogni passo. Conta quante volte è necessario per finire.