Bubble Sort

Tra i piú semplici algoritmi di ordinamento abbiamo il Bubble Sort, che in italiano significa naturalmente ordinamento a bolle, e gią il nome dovrebbe dirci tutto, almeno.
Il meccanismo si basa infatti sull 'idea di far emergere man mano (come bollicine) gli elementi minori all' inizio del vettore mentre contemporaneamente quelli maggiori si posizionano in fondo al vettore.

Vediamo nel dettagli l' algoritmo : dato un vettore con n elementi, per ogni iterazione il primo elemento viene confrontato con il secondo, e se risulta maggiore, viene scambiato. La stessa cosa avviene tra il secondo ed il terzo elemento e cosi via fino alla fine del vettore. Dopo n-1 iterazione il nostro vettore risulterá ordinato.

Ecco l' implementazione in java dell' algoritmo :
    public void bubbleSort(int [] array) {
for(int i = 0; i < array.length; i++) { boolean flag = false; for(int j = 0; j < array.length-1; j++) {
//Se l' elemento j e maggiore del successivo allora //scambiamo i valori if(array[j]>array[j+1]) { int k = array[j]; array[j] = array[j+1]; array[j+1] = k; flag=true; //Lo setto a true per indicare che é avvenuto uno scambio }
}
if(!flag) break; //Se flag=false allora vuol dire che nell' ultima iterazione //non ci sono stati scambi, quindi il metodo può terminare //poiché l' array risulta ordinato } }
La complessitá dell' algoritmo in numero di confronti é quadratica nel caso peggiore e medio O(n^2), mentre risulta lineare O(n) nel caso migliore (quando il vettore risulta parzialmente ordinato). Mentre per gli scambi é quadratica nel caso peggiore e medio O(n^2), mentre risulta costante O(1) nel cosa migliore.

Questa é l' applet che ci mostra l' esecuzione del Bubble Sort :

Per potere utilizzare questo tool č necessaria l' installazione della Java Virtual Machine.
Scarica la Java Virtual Machine

Inserite manualmente i numeri nelle caselle, oppure usate la generazione automatica, con gli opportuni pulsanti : Random (casuale), Crescente e Descrescente. Per far partire l' ordinamente usate il pulsante Ordina e regolate la velocita con l' apposita slider.

Indice » 1 2 3 4 5 6