Bubble sort

Il Bubble Sort, in italiano ordinamento a bolle, è l'algoritmo più semplice per ordinare gli elementi di un array.

Come funziona? Esso prevede l'uso di due indici: il primo, inizialmente, punta al primo elemento dell'array, il secondo indice punta al secondo elemento. Partendo da queste posizioni, il primo elemento viene confrontato con tutti gli elementi successivi. Ogni volta che il primo elemento risulta maggiore dell'elemento con cui viene confrontato, i due valori vengono scambiati. E' chiaro che alla fine di questa serie di confronti il primo elemento risulterà il minore di tutto l'array. Poi il primo indice viene spostato alla seconda posizione e il secondo indice riparte dalla terza; di nuovo si effettuano tutti i confronti. E così via, finchè il primo indice arriva al penultimo elemento dell'array.

Questo algoritmo viene qui esposto per scopi didattici ma, siccome richiede una quantità di confronti troppo alta, risulta molto poco efficente.

Segue la sua implementazione in linguaggio C:

void bubble_sort(TYPE *array, int count) {
  
  register int a, b;
  int tmp;
  
  for (a=0; a<count; a++) {
    for (b=count-1; b>=a; --b) {
      if (array[b-1] > array[b]) {
        tmp = array[b-1];
        array[b-1] = array[b];
        array[b] = tmp;
      }
    }
  }
  
}

Due note di carattere tecnico: a e b sono dichiarati come register, il chè significa che, se possibile, il compilatore farà in modo che vengano collocate nei registri della CPU; questo renderà più rapido l'accesso a dette varibaili. tmp è dichiarata di tipo int, quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficente modificare la sua dichiarazione.