Il metodo di ordinamento a bolle è il più conosciuto e semplice algoritmo di ordinamento da realizzare. Esso si basa su due indici che saranno utilizzati per confrontare due elementi della lista di dati da ordinare. Se il primo elemento in analisi è maggiore del secondo elemento i due dati analizzati saranno invertiti.

Più che nozioni teoriche vedremo proprio un esempio pratico di applicazione di questo principio, applicato ad un vettore di 10 numeri interi.

Immaginiamo pertanto questo vettore disordinato di numeri:

Per effettuare l'inversione dovremo confrontare due elementi per volta ed effettuare lo scambio di due elementi nel caso che il primo sia maggiore del secondo. Vediamo passo passo la procedura da seguire:
inizialmente imposteremo il primo indice al primo elemento ed il secondo indice al secondo elemento. Se il numero indicato dal primo indice (10) è maggiore di quello indicato dal secondo indice (4), scambieremo i due valori (4 e 10).

In seguito a questo, manenendo fisso il primo indice, incrementiamo il secondo indice di una posizone; pertanto il primo indice punterà al valore 4 (infatti il 10 è stato invertito con il 4) ed il secondo indice punterà al valore 7. Poiché il numero puntato dal primo indice non è maggiore di quello puntato dal secondo indice, lasceremo intatti i due valori.
Incrementiamo di 1 il secondo indice ed otteniamo i due numeri (4 e 5); anche in questo caso non sarà necessario alcun cambiamento in quanto il primo numero non è maggiore del secondo.

Tutto procede regolarmente fino a che il secondo indice non raggiunge la fine del vettore, scambiando i valori quando il primo è maggiore del secondo.
Otteniamo pertanto questo vettore:

Completato il primo giro, abbiamo nella prima posizione del vettore il numero 1.
Può adesso cominciare il secondo giro: impostiamo il primo indice al secondo elemento del vettore ed il secondo indice all'elemento successivo al primo indice, ovvero al terzo elemento. Effettuiamo i normali confronti tra i due valori, incrementando ogni volta il secondo ed invertendo i valori quando il primo è maggiore del secondo. Otterremo quindi il seguente vettore:

E procediamo così via, fino a quando il primo indice non raggiunge il penultimo elemento ed il secondo indice non raggiunge l'ultimo.
Alla fine di quest'operazione il vettore di numeri sarà ordinato:

I numeri in rosso sono gli indici già controllati e che utilizzeremo per confrontare con gli altri elementi.

Fibia FBI
1 Febbraio 2001

Scarica il progetto

Scarica il testo dell'articolo

Stampa l'articolo