Algoritmo bublesort

L’algoritmo bublesort consente di ordinare gli elementi in un array di N elementi.

Se quello in figura è un array di 10 caratteri, indicante un cognome, il vettore ordinato diventerà il seguente:

Per ottenere questo array controlliamo i primi due elementi e se il secondo è più piccolo del primo li invertiamo. Il C considera i caratteri ordinati perché ne valuta il loro ordine in base al corrispondente codice ASCII.

Facciamo una serie di N-1 confornti alla fine dei quali avremo un vettore con l’elemento più grande “salito” in ultima posizione (cioè nel posto n-esimo) proprio come succede ad una bolla che risale in superficie di un liquido.

Vediamo la sequenza di scambi:

La lettera o è risalita dalla terzultima posizione fino alla fine del vettore. Se ripetiamo un’altro ciclo di scambi vedremo che anche la lettera “n” risalirà in penultima posizione e così poi le altre.

L’algoritmo è del tipo:

1. for (i=0; i<N-1;i++) {
2.     for (j=0; j<N-1; j++) {
3.         if (V[j]>V[j+1])  {
4.                 temp = vet[j];
5.                 vet[j] = vet[j+1];
6.                 vet[j+1]  = temp;
7.         }
8.      }
9. }

Il ciclo interno (in colore marrone) effettua una scansione su tutti gli elementi del vettore (da 0 perché in C le celle dell’array sono numerate da 0 a N-1), man mano che il valore dell’indice “j” cresce vengono controllati gli elementi dell’array e se V[j]>V[j+1] cioè se il successivo è più piccolo deve essere fatto uno scambio. L’algoritmo di scambio è quello classico, questo:

• temp = vet[j];
• vet[j] = vet[j+1];
• vet[j+1] = temp;

si prende una variabile temporanea, temp, si “salva” in essa il valore di vet[j] con l’istruzione temp = vet[j] poi si cancella  vet[j]inserendovi il valore giusto, quello più piccolo che è dopo in  vet[j+1]. Infine in  vet[j+1]  si inserisce quello che c’era in vet[j]   e che è stato salvato in temp con l’istruzione vet[j+1] = temp.

Questa serie di (eventuali) scambi viene eseguite su tutto il vettore per una sola volta, alla fine, però, avremo un solo elemento risalito in ultima posizione (il più grande). Dobbiamo quindi ripetere l’operazione per far risalire anche il penultimo elemento, e poi il terzultimo e così via… Per questo motivo usiamo un altro ciclo di N ripetizioni esterne, così che ad ogni ciclo risale un’altro elemento.

Nota: in effetti il ciclo esterno è sempre di N ripetizioni e finisce per controllare anche gli elementi già ordinati. Questo controllo è superfluo ma ininfluente sull’esito finale.

Al secondo passaggio avremo:

Al termine del secondo ciclo esterno (primo ciclo j=0, secondo ciclo j=1) avrò due elementi in ultima posizione. Nel terzo ciclo si avrà:

quindi ottengo che le 3 lettere più in basso (le ultime 3 sono in ordine, sono le più grandi). Alla fine dei 10 scambi avrò il vettore ordinato.