Algoritmo di ordinamento: bubble sort

Carlo Carrà - 1921 - "Pino sul mare"

E' il caso più semplice di ordinamento che si conosca. E' il metodo meno efficiente in termini di tempi di risoluzione ma è il più intuitivo. Tradotto significa bolle ossia si comporta come le bollicine di una bottiglia di acqua minerale che dal basso risalgono verso l'alto. L'algoritmo è il seguente:

Il primo elemento del vettore si confronta con l'elemento successivo se è maggiore si scambia do posto.

Se arrivato al secondo posto è ancora maggiore del terzo si scambia e così via fino ad arrivare all'ultimo posto.

Si riprende dall'inizio confrontando nuovamente il primo posto con il secondo fino ad arrivare al penultimo in quanto l'ultimo è già ordinato.

Ecco un esempio di un semplice vettore formato da cinque elementi non ordinati:

5 4 3 2 1

PRIMA FASE

5>4 scambio  --> 4 5 3 2 1

5>3 scambio  --> 4 3 5 2 1

5 >2 scambio --> 4 3 2 5 1

5>1 scambio  --> 4 3 2 1 5

SECONDA FASE (si ferma ad un punto inferiore rispetto al precedente)

4>3 scambio --> 3 4 2 1 5

4>2 scambio --> 3 2 4 1 5

4>1 scambio --> 3 2 1 4 5

TERZA FASE

3 > 2 scambio --> 2 3 1 4 5

3> 1 scambio --> 2 1 3 4 5

QUARTA FASE

2 > 1 scambio 1 2 3 4 5

STOP

Il numero delle fasi è sempre uguale al numero di elementi meno.

Come esercizio è utile provare ad implementarlo (suggerimento sono due cicli uno all'interno dell'altro).

 

 

 

Informazioni su Francesco Bragadin

Insegno informatica e telecomunicazioni al liceo scienze applicate ed all'indirizzo informatica e telecomunicazioni. Ho terminato gli studi in ingegneria elettronica e telecomunicazioni lavorando per molti anni come libero professionista nell'ambito della gestione storage e disaster recovery su mainframe.
Questa voce è stata pubblicata in Uncategorized. Contrassegna il permalink.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *