Algoritmo di ordinamento "bubble sort" [SPIEGAZIONE]

  1. #1
    Nuovo utente L'avatar di Red John ©
    Data Registrazione
    Jan 2014
    Località
    Bologna
    Messaggi
    11
    Salve a tutta la community
    Apro questo tread per presentare ai neofiti di questo linguaggio e a chi si addentra per la prima volta nel mondo della programmazione questo semplicissimo algoritmo di ordinamento, denominato "Bubble sort ".
    Per prima cosa partiamo dalla teoria:
    A cosa serve davvero un algoritmo di ordinamento?
    In programmazione ci capiterà spesso di ritrovarci un vettore (insieme di elementi) che contiene al suo interno dei dati in disordine; a volte può risultare utile, o addirittura indispensabile, ordinare questi dati in base ad una qualsiasi relazione d'ordine (per esempio la grandezza, in modo crescente o decrescente)
    Molto importante:
    L'algoritmo di ordinamento bubble sort è un algoritmo di ordinamento tanto semplice quanto inefficace; esistono altri algoritmi di ordinamento molto più efficaci, questo di solito viene usato solo a scopo didattico ed accademico a causa della sua estrema facilità.
    Esecuzione del Bubble sort su una lista di numeri:

    Algoritmo di ordinamento "bubble sort" [SPIEGAZIONE]

    Adesso passiamo ad una spiegazione più dettagliata di questo algoritmo:
    Come funziona?
    Questo algoritmo fa parte della famiglia degli algoritmi detti "iterativi" basati quindi sulla ripetizione di una certa istruzione; non a caso in programmazione ciclo è sinonimo di iterazione.
    Dato un vettore ordinato di numeri casuali parte l'algoritmo; esso è formato da due cicli: il primo (quello più esterno) attraverso una variabile logica di tipo booleana si occupa di controllare l'uscita dal ciclo interno che riordina i dati.
    Ma come funziona l'ordinamento vero e proprio dei dati?
    Calma calma, ci stavo arrivando!
    Il ciclo interno si occupa, come detto poco fa, dell'ordinamento dei dati.
    Pensiamola in termini numerici:
    Sostanzialmente viene controllato mano a mano ogni numero con il suo successivo, se questo numero è minore del suo successivo non succede niente e si passa al numero successivo; se invece questo numero è maggiore del suo successivo vengono scambiati.
    Si ripete questa operazione ciclicamente finchè tutti i numeri non sono ordinati.
    Quando tutti i numeri sono al loro posto non avviene più nessuno scambio quindi si esce dal ciclo.
    In sostanza quindi l'algoritmo a bolla controlla ciclicamente ogni numero con il suo successivo scambiandolo finchè tutti i numeri sono in ordine.
    Chiaro?
    In ogni caso adesso vediamo come implementare questa idea, questo algoritmo in codice Java.
    Implementazione dell'algoritmo in Java:

    Codice:
    //Algoritmo di ordinamento a bolla implementato in Java
    
    public class bubblesort {
        
        public static void main (String args[]) {
            
            int[] v = new int [20];
            boolean flag=true;
            //Riempo il vettore
            System.out.println("Vettore non ordinato");
            for (int i = 0; i <v.length ; i++)  
            {
                
                v[i]=(int)(Math.random()*10);
                
                System.out.println(v[i]);
            
            }    
            System.out.println("------------------");
            
            int C; //Inizia l'algoritmo
             
             while(flag==true){             
                flag=false;
                for(int i=0;i<v.length-1;i++){ 
                     if (v[i]>v[i+1]){ //se un numero è > del suo successivo
                         flag=true; //avviene lo scambio
                         C=v[i]; //quindi si scambiano e C diventa il n precedente
                         v[i]=v[i+1]; //inoltre il numero diventa uguale al suo successivo
                         v[i+1]=C;
                     }
                 }
                }
                    
            // Stampo il vettore ordinato
            System.out.println("Vettore ordinato");
            for(int i=0;i<v.length;i++)
                         System.out.println(v[i]);
            }
        }

    Ma vediamo più in dettaglio ogni parte di questo programma:

    Codice:
    public class bubblesort {    
        public static void main (String args[]) {
            
            int[] v = new int [20];
            boolean flag=true;
    Fin qui direi tutto bene, ho solamente dichiarato un vettore intero di 20 elementi interi e una variabile di tipo booleana.

    Codice:
    //Riempo il vettore        System.out.println("Vettore non ordinato");
            for (int i = 0; i <v.length ; i++)  
            {
                
                v[i]=(int)(Math.random()*10);
                
                System.out.println(v[i]);
            
            }
    Anche qui molto semplicemente riempo il vettore con numeri casuali interi per comodità. In realtà si possono anche dichiarare gli elementi del nostro vettore disordinato "a mano", non cambia assolutamente nulla al fine ultimo dell'algoritmo.

    Codice:
    int C;
     //Inizia l'algoritmo         
             while(flag==true){             
                flag=false;
                for (int i=0;i<v.length-1;i++){ 
                     if (v[i]>v[i+1]){ //se un numero è > del suo successivo
                         flag=true; //avviene lo scambio
                         C=v[i]; //quindi si scambiano e sposto il valore di v[i] (ora numero precedente) nella variabile temporanea C
                         v[i]=v[i+1]; //sposto il valore di v[i] nella casella successiva
                         v[i+1]=C;//nella casella successiva ci metto il valore di C (che conteneva il numero precedente)
                     }
                 }
                }
    Eccoci arrivati al "cuore" del programma ovvero all'algoritmo.
    Vediamo quindi il ciclo più esterno (il while) che incorpora il ciclo più interno (il for) il quale si occupa del confronto e dello scambio dei valori.
    Come condizione di uscita dal while metto che la variabile booleana (in questo caso flag) debba essere vera, subito dopo mi occupo di settare quest'ultima falsa in modo che non mi esca subito dal primo ciclo.
    Codice:
     while(flag==true){             
                flag=false;
    Fatto questo si entra nel for che controlla il vettore antecedentemente caricato lasciando però una cella vuota in modo così da evitare la perdita dei valori.
    Codice:
    for (int i=0;i<v.length-1;i++)
    Entrati nel ciclo ci troviamo di fronte ad una condizione imposta da un if :
    [CODE
    if (v[i]>v[i+1]) //se un numero è > del suo successivo
    [/CODE]
    Questa condizione in realtà è la condizione che regola l'operazione del confronto di un numero col suo successivo, fondamentale quindi per l'algoritmo.
    Nel caso questa condizione sia vera avviene lo scambio e settiamo la variabile booleana flag come vera.
    Molto bene, adesso avviene la fase di scambio dei numeri:
    Codice:
    C=v[i]; //quindi si scambiano e sposto il valore di v[i] (ora numero precedente) nella variabile temporanea C                     v[i]=v[i+1]; //sposto il valore di v[i] nella casella successiva
                         v[i+1]=C; //nella casella successiva ci metto il valore di C (che conteneva il numero precedente)
    In realtà il ragionamento qui è molto semplice ed immediato, ci occorre solo una variabile temporanea (in questo caso C) che ci serve per effettuare lo scambio dei valori.
    Quando non viene fatto alcuno scambio e l'ultimo ciclo gira a vuoto la variabile flag non viene più settata vera quindi si esce dal ciclo.

    Passiamo ora alla fase finale del programma.

    Adesso che abbiamo in nostro bel vettore ordinato salvato nella RAM non ci rimane che stamparlo per vedere il risultato:
    Codice:
    // Stampo il vettore ordinato        System.out.println("Vettore ordinato");
            for(int i=0;i<v.length;i++)
                         System.out.println(v[i]);
    Et voilà!
    Ecco spiegato il funzionamento di questo semplice algoritmo di ordinamento.
    Ho cercato di essere il più chiaro e dettagliato possibile, in ogni caso se avete dubbi o critiche vi esorto a scrivere qui sotto o per PM.
    Saluti.



    Ultima modifica di Red John ©; 14-01-2014 alle 00:35
    Tecnogers staff.
    Interventi di moderazione in questo colore : #00cc00

Termini piu ricercati:

flag bubble sort java algoritmo

bubble sort java spiegazione

spiegazione bubble sort

algoritmo ordinamento bubble sort

bubble sort c spiegazione

algoritmo bubble sort java con while

spiegazione bubble sort javaordinamento bubble sort javabubble sort spiegazionespiegazione variabile flagalgoritmo java spiegazione semplicespiegazione bubble sort c bubble sort in breve