Algoritmi in pillole: bubble sort

Animazione dell'algoritmo di Bubble sort da wikipedia

Animazione dell'algoritmo di ordinamento bubble sort da wikipedia

L'algoritmo controlla ogni coppia di elementi adiacenti  e li scambia se non sono ordinati. L'algoritmo procede così fino a quando non ci sono più scambi da fare. 

pseudocodice:

"per i che varia da 0 a N-1
   per j che varia da N-1 a i+1
      se l'elemento j è minore dell'elemento j-1
        allora scambia l'elemento j con l'elemento j-1"

Codice:

void bubblesort(int v[], int n) {
  int i=0,j,temp;
  int scambio = FALSE;
  do {
    scambio=FALSE;
    for (j=n-1;j>i;j--)
      if (v[j]<v[j-1]) {
        temp=v[j];
        v[j]=v[j-1];
        v[j-1]=temp;
        scambio=TRUE;
      }
      i=i+1;
    } while(i<n-1 && scambio);
}

La complessità computazionale asintotica è O(n^2).
Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                     - T. esec. prop. a n