In questo articolo sarà esaminato l'algoritmo del Bubble sort.
Strategia utilizzata:
Ogni elemento, a partire dal primo, viene confrontato con l'elemento successivo e se non sono ordinati vengono scambiati di posizione.
Risorse collegate
Se vuoi approfondire la spiegazione dell'algoritmo guarda il video 
Se vuoi scaricare il codice in linguaggio C clicca qui 
Se vuoi scaricare il codice in linguaggio Php clicca qui 
Clicca sull'icona per il PDF di questo argomento 
Supponendo di ordinare in maniera crescente, questo metodo produce in generale uno spostamento dei valori più alti verso destra. Viene usato un solo indice K che scorre fino al penultimo elemento del vettore (posizione N-2) cosicché esso possa essere confrontato con l'elemento successivo che è l'ultimo. Quando la prima scansione sarà terminata, avremo portato il massimo del vettore in ultima posizione, cioè nella posizione N-1. Questo algoritmo risulta generalmente più efficiente del selection sort se i dati sono parzialmente ordinati.
Per rendere l'algoritmo più efficiente utilizzeremo una variabile, chiamata scambioeffettuato, che fungerà da flag. Essa sarà impostata a 0 inizialmente
e poi impostata al valore 1 se durante la scansione del vettore sarà stato effettuato almeno uno scambio.
Alla fine di ciascuna scansione, se non è avvenuto alcuno scambio (cioè se la variabile scambioeffettuato sarà rimasta con il valore 0) vorrà dire che gli elementi sono tutti ordinati e l'algoritmo potrà terminare senza ulteriori confronti.
Riporto qui di seguito il tracciamento di tutti gli scambi effettuati durante la prima scansione.
Notare che, dopo il primo scambio, la variabile scambioeffettuato rimane costantemente uguale a 1. Questo costringerà l'algoritmo a ripetere la scansione del vettore, dopo aver escluso l'ultimo elemento del vettore che essendo il massimo non sarà più necessario confrontare con gli altri. Per ridurre gli elementi in gioco, utilizzerò una variabile ultimo, che inizialmente sarà impostata a N-2 e che sarà decrementata alla fine di ogni scansione, permettendomi così di ridurre (virtualmente) il vettore.
Di seguito riporto una possibile pseudo-codifica dell'algoritmo in questione.
Passiamo ora ad un veloce commento della codifica in linguaggio C, che potete scaricare
Definiamo le costanti e le variabili a livello di modulo:La variabile nconfronti servirà per contare il numero di confronti effettuati, al fine di valutare l'algoritmo. La #define definisce MAX che sarà utilizzata per dichiarare la dimensione del vettore.
Esaminiamo ora la funzione main(). Carichiamo un vettore statico di 15 elementi solo per la fase di test del programma; nel caso reale sostituiremo le linee evidenziate con il tratteggio con le due linee di codice che lo precedono che ci consentiranno di caricare un vettore con n elementi essendo n un numero deciso dall'utente comunque minore o uguale a 100 (vincolo imposto dalla define MAX). Richiamiamo la funzione stampa_vettore per mostrare il vettore prima dell'ordinamento; poi richiamiamo la funzione BubbleSort per ordinare il vettore ed infine richiameremo la funzione stampa_vettore per mostrare il vettore ordinato.
Esaminiamo la funzione stampa_vettore.
Essa ha in ingresso tre parametri: il vettore da stampare e poi due indici che puntano al primo elemento e all'ultimo elemento da stampare. Essa è implementato con un ciclo iterativo controllato dalla variabile i il cui valore iniziale è uguale al parametro p e che dovrà arrivare al valore del parametro u; all'interno del ciclo sarà visualizzato l'elemento a[i] sempre sulla stessa riga; quando avremo mostrato tutto il vettore invieremo anche un "\n" per andare a capo.
Analizziamo la funzione BubbleSort()
Essa non restituisce alcun valore (infatti c'è un Void prima del nome della funzione). Prende In input due parametri il vettore a e n che indica quanti elementi del vettore a devono essere presi in considerazione (questo ci consente di utilizzare una parte più piccola del vettore invece che tutti i 100 elementi dichiarati nella define Max, di cui abbiamo parlato all'inizio). Dichiariamo poi le variabili che ci servono: in particolare la variabile k che sarà l'indice che utilizzeremo, il flag scambioeffettuato e la variabile ultimo. Il flag scambioeffettuato sarà impostato a 1 per forzare l'ingresso nel nel ciclo while immediatamente successivo. La variabile ultimo sarà impostata a N-2 e sarà decrementata ad ogni ciclo. All'interno del ciclo while rimettiamo a 0 il flag scambioeffettuato eh incominciamo a scandire il vettore con un ulteriore ciclo interattivo. Questa volta utilizziamo l'istruzione for la cui variabile di controllo k parte da zero e arriva a ultimo incluso. All'interno del ciclo iterativo andremo a fare il confronto di ogni elemento con il suo successivo, (a[k]>a[k+1]), e se necessario effettueremo lo scambio.
Passiamo alla funzione scambia.
No comment!