L’algoritmo appartiene alla categoria: Ordinamento per interscambio.

Effettua l’ordinamento di un array confrontando elementi adiacenti ed eventualmente scambiandoli. Poi effettua altre passate fin quando l’array è completamente ordinato.

L’algoritmo fondamentalmente parte da destra (il secondo ciclo è quello che fa gli scambi) confronta l’ultimo elemento, con il penultimo e se l’ultimo è < del penultimo li scambia. Poi passa a confrontare il penultimo con il terzultimo e così via.. fino a confrontare il secondo con il primo. A questo punto una prima passata dell'array è completa ed l'elemento più piccolo si troverà alla prima componente dell'array. Si procede quindi con altre passate fermandosi al confronto fra il terzo e il secondo elemento dell'array.. e così finchè non viene ordinato completamente l'array. Questo algoritmo si chiama Bubble sort perchè come le bolle d'aria tendono a salire su, se vediamo l'array in verticale, gli elementi più piccoli man mano saliranno verso l'alto. Analogamente a BubbleSort vi è LeadSort (un bubblesort invertito), Lead significa piombo. Infatti questo algoritmo è uguale a BubbleSort con l'unica differenza che ordina i numeri grandi. La sua complessità computazionale è: O(n^2). 

/*
BUBBLESORT - Ordinamento di un Array.
Complessità Computazionale: O(n^2)
*/
 
void bubblesort(int a[], int n){
int i, j;
// N.B. n-1 è l'ultima componente dell'array.
for(i = 0; i < n - 1; i++) //scansiona tutto l'array tranne l'ultima componente: n - 1 escluso. Quindi fino al penultimo elemento.
      for (j = n - 1; j > i; j--) //j settato all'ultima componente e decresce ad ogni iterazione. Esce dal ciclo solo se j <= i
                  if (a[j] < a[j-1])  //se la componente corrente è più piccola della precedente, li scambia.
                          scambia(&a[j],&a[j-1]);                   
}
 
//la funzione scambia è così composta:
void scambia(int *a, int *b){ //richiede due indirizzi di memoria in entrata che verranno memorizzati in 2 puntatori.
int temp; //la variabile d'appoggio che memorizza temporaneamente il valore di a.
temp = *a;
*a = *b;
*b = temp;
}
//NB. l'asterisco * dei puntatori fa riferimento sempre al valore a cui punta il puntatore.

Accompagniamo l’algoritmo con un simpatico video che ne mostra la strategia di funzionamento: