Nel mondo dell’informatica le strutture dati ricoprono un ruolo di primissimo piano.

I dati, infatti, sono la linfa vitale di qualsiasi sistema informativo e la loro organizzazione logica e fisica è determinante per il corretto ed efficiente funzionamento di tutto il sistema.

Una struttura dati è semplicemente un insieme di dati logicamente correlati fra loro, come una lista o un database.



Una delle operazioni più frequenti su una struttura dati è senz’altro la ricerca di un elemento al suo interno, ad esempio per verificarne l’esistenza, per modificarlo o per cancellarlo.

È del tutto evidente che ricercare un elemento all’interno di una struttura logica, richiede sicuramente meno tempo se i dati di questa struttura logica rispettano un criterio di ordinamento. Ad esempio, immaginiamo di voler cercare il numero di telefono di una persona, partendo dal suo nome e cognome e immaginiamo anche che abbiamo a disposizione un (ormai obsoleto) elenco telefonico. Siccome le utenze nell’elenco telefonico sono ordinate alfabeticamente per cognome, non mi occorre molto tempo per centrare il mio obiettivo. Che succederebbe invece se l’elenco non fosse ordinato, ma le utenze fossero state inserite totalmente a caso? Dovrei scorrere pazientemente tutti gli elementi uno alla volta, in quanto quello che io cerco potrebbe stare ovunque. Concordi con me che così sarebbe una follia?

Allo stesso modo in ambito informatico, se una struttura dati è pesantemente oggetto di ricerche, potrebbe avere senso ordinarla preventivamente. Perderei del tempo all’inizio per ordinare tutti i suoi elementi, ma poi le ricerche in seguito sarebbe molto veloci.

Inutile dire che ci sono innumerevoli algoritmi di ordinamento, tuttavia non è questa la sede per approfondirli. Vediamo qui, invece, un particolare algoritmo, ormai sorpassato da altri più efficienti, ma che ha ancora una validità didattica, per la sua semplicità ed eleganza: il bubble sort.


Prendiamo per semplicità un vettore di caratteri. Un vettore è una semplice struttura dati unidimensionale, in cui tutte le celle contengono lo stesso tipo di dato, in questo caso un carattere.


Applicando il bubble sort al nostro vettore, i suoi elementi più grandi, verranno via via spostati verso il fondo (a destra), lasciando gli elementi più piccoli all’inizio. Infatti il nome bubble sort è stato dato perché ricorda un po’ le bollicine che salgono in un bicchiere di spumante.

È un algoritmo iterativo, ossia vengono ripetuti (iterati) sempre gli stessi passi finché non viene rispettata una condizione, quindi si ha la soluzione finale e ci si ferma.

I passi sono i seguenti:

Partendo dall’inizio (da sinistra), si confronta il primo valore e il secondo. Se il maggiore dei due si trova nella prima posizione, allora i due valori vengono scambiati, altrimenti non viene fatto nulla. Dopodiché si confrontano il secondo valore del vettore e il terzo e anche qui, se il secondo valore è maggiore del terzo, questi vengono scambiati, altrimenti no, e così via. Dopo una prima passata, cioè quando tutto il vettore è stato oggetto dei confronti due a due, il valore massimo avrà raggiunto la posizione finale (a destra). A questo punto si ripete il processo altre n-1 volte, dove n è la lunghezza del vettore che vogliamo ordinare.

Facciamo un esempio pratico, vogliamo ordinare il seguente insieme di caratteri in ordine sequenziale:


Eseguiamo la prima passata:

Confrontiamo il primo e il secondo elemento: B>G ?

No, pertanto non effettuiamo lo scambio.

Confrontiamo ora il secondo con il terzo elemento: G>A?

Sì, quindi scambiamo i due elementi e otteniamo questo:


Proseguiamo, confrontiamo il terzo elemento con il quarto: G>C?



La risposta è ancora positiva, pertanto scambio gli elementi;


È chiaro come il valore G ad ogni iterazione tenderà a salire (come una bollicina in un liquido) fino ad occupare la posizione più a destra.

Finita la prima passata, si procede con la seconda. Ma per lo stesso identico principio, a salire questa volta sarà l’elemento F che arriverà fino alla penultima posizione e lì si fermerà, poiché il confronto con G (F>G) risulterà negativo.

Dopo un numero di passate sufficienti pari a 6 (ossia n-1, dove n=7 nel nostro caso),

avremo il vettore perfettamente ordinato:

Questa appena esposta è la versione base dell’algoritmo, ma ne esistono innumerevoli varianti, in grado di ottimizzare l’intero processo, ad esempio uscendo prima dal ciclo quando ci si accorge che il vettore è già ordinato, risparmiando tempo.