L’importanza dell’ordine
L’importanza dell’ordine
Nella maggior parte delle lingue l’oggetto che negli ultimi anni ha provocato i maggiori cambiamenti
della nostra vita ha un nome che descrive la sua funzione principale, quella di effettuare dei calcoli:
“computer” in inglese, “calcolatore” in italiano ...
Per ordinare un elenco telefonico contenuto in un file non basta confrontare ogni byte con gli altri,
ma si deve considerare il modo in cui i bytes sono disposti ...
Il primo algoritmo di ordinamento
Immaginiamo di dover ordinare una semplice sequenza di numeri (che possono essere visti come
record composti da un solo campo numerico). La sequenza è ...
Le cose cambiano se il numero degli elementi da ordinare aumenta. Immaginiamo di estendere a
dodici elementi la sequenza da ordinare ...
Il metodo che abbiamo visto per inserire un numero in un file già ordinato richiede un confronto
con ogni elemento che lo precede, fino all’identificazione della posizione corretta ...
Utilizzando l’inserzione binaria si può ridurre il numero di confronti necessari per ordinare un file,
ma non il numero di spostamenti. Per ridurre anche quest’ultimo si devono trovare altri accorgimenti ...
L’ultimo algoritmo di ordinamento che esaminiamo è il “quicksort” o “ordinamento rapido”,
che venne proposto nel 1962 da C.A. Hoare. Questo algoritmo richiede un numero limitato di scambi
ed è estremamente veloce ...
La ricerca all’interno di un file
Immaginiamo di dover cercare il nome di una persona di cui conosciamo il numero di telefono
utilizzando un normale elenco telefonico. Non ci sono particolari considerazioni da fare; l’unico
metodo è la ricerca sequenziale: si legge un numero alla volta, fino a trovare quello che cerchiamo ...