Tra i piú semplici algoritmi di ordinamento di Java abbiamo il Bubble Sort, che in italiano significa naturalmente ordinamento a bolle.
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 dettaglio 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 Bubble Sort:
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 situazione migliore.
