Bubble Sort

"Ordinamento a bolle" con Java

L’algoritmo BUBBLE SORT si basa sull'idea di far emergere pian piano gli elementi più piccoli verso l’inizio dell’insieme da ordinare facendo sprofondare gli elementi maggiori verso il fondo, un po’ come le bollicine in un bicchiere di acqua gassata (da qui il nome di ordinamento a bolle). Immaginiamo di avere un vettore con n elementi, per ogni iterazione il primo elemento viene confrontato con il secondo, e se risulta maggiore, viene scambiato. Procedendo dall'inizio alla fine del vettore, al termine di ogni scansione si è ottenuto che l’elemento massimo è finito in fondo al vettore stesso, mentre gli elementi più piccoli hanno cominciato a spostarsi verso l’inizio del vettore. Dunque alla fine della prima scansione possiamo essere certi che l’elemento massimo ha raggiunto la sua posizione corretta nell'ultima posizione del vettore. Nella scansione successiva, il programma potrà fermarsi senza considerare l’ultimo elemento dell’insieme e riuscendo così a collocare nella posizione corretta (la penultima) il secondo elemento più grande dell’insieme;
Si ripete fino ad aver completato l’ordinamento dell’intera sequenza.

Prendendo in esame il caso dell'immagine, ordiniamo l'array partendo dal confrontare la prima casella (15) con la consecutiva (6); il numero della prima casella, essendo maggiore del numero della casella adiacente, prende il suo posto.
Ora confrontiamo la seconda casella (15) con la terza (4); anche in questo caso il numero 15 risulterà maggiore del numero presente nella terza casella e come nel passaggio precedente, anche qui prenderà il suo posto.
Nel nostro caso, vediamo il numero 15 risultare maggiore dei numeri nelle caselle successive ad esso, così da prenderne in ogni caso il posto. Arrivati all'ultima casella, il programma terminerà i confronti per il numero 15, essendo risultato il numero più grande nel vettore. Ora lo stesso procedimento verrà applicato alla nuova prima casella (6), effettuando i confronti e le modifiche come mostrato nel primo passaggio.
Il programma si arresterà quando dalla prima all'ultima casella del nostro vettore, i numeri risulteranno in ordine crescente.

Ecco un esempio di Bubble Sort svolto in Java:
public void main(String[] args){
 int prova[]={5,18,46,52,83,37,51,3};
int temp=0;
 int j=prova.lenght;
 System.out.println ("Array non ordinato:");
 for (i=0;i<prova.lenght;i++)
 System.out.println (" "+prova[i]);
 while (j> 0){
        for ( int i=0; i < j-1; i++){
                if (prova[i]> prova[i+1]){
                         temp = prova [i+1];
                         prova[i] = prova [i+1];
                         prova[i+1] = temp;
}}
} System.out.println ("Array ordinato:");
for (i=0; i<prova.lenght; i++)
System.out.println(" "+prova[i]);
}


Maria Giovanna Ambrosio - Alessia Ambrosio

Comment Stream