Implementazioni di algoritmi/Bubble sort

Il bubble sort o bubblesort (letteralmente: ordinamento a bollicine) è un semplice algoritmo di ordinamento particolarmente indicato per l'ordinamento di array. Non si tratta di un algoritmo particolarmente efficiente; ha una complessità computazionale (misurata in termini di numero di confronti e assegnamenti) O(n²), molto superiore per esempio a quella del quicksort. Tuttavia è piuttosto noto e utilizzato (sia in ambito didattico che da parte di programmatori professionisti) in virtù della sua semplicità. Dell'algoritmo esistono numerose varianti, in alcuni casi sufficientemente note da aver meritato un nome distinto (per esempio, lo shakersort). Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una relazione d'ordine; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di numeri interi. Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine in un bicchiere di champagne. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente (a differenza di quanto avviene nel caso del bicchiere di champagne, tuttavia, alcuni elementi salgono ma altri scendono).

Spiegazione astratta

Il bubblesort è un algoritmo iterativo, ovvero basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito (se si scandisca l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; nel seguito ipotizzeremo che lo si scandisca partendo dall'inizio). Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto, e così via fino al confronto fra penultimo e ultimo elemento. Per ogni confronto, se i due elementi confrontati non sono ordinati, essi vengono scambiati. Durante ogni iterazione, almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array. Il motivo è semplice, e si può illustrare con un esempio. Supponiamo che l'array sia inizialmente disposto come segue:

15 6 4 10 11 2

Inizialmente 15 viene confrontato con 6, ed essendo 15>6, i due numeri vengono scambiati:

6 15 4 10 11 2

A questo punto il 15 viene confrontato col 4, e nuovamente scambiato:

6 4 15 10 11 2

Non è difficile osservare che, essendo 15 il numero massimo, ogni successivo confronto porterà a uno scambio e a un nuovo spostamento di 15, che terminerà nell'ultima cella dell'array. Per motivi analoghi, alla seconda iterazione è garantito che il secondo numero più grande raggiungerà la sua collocazione definitiva nella penultima cella dell'array, e via dicendo. Ne conseguono due considerazioni:

1. se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;
2. alla iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto dei valori alle posizioni N-1-i e N-i.

Ovviamente, a ogni iterazione può accadere che più numeri vengano spostati; per cui, oltre a portare il numero più grande in fondo all'array, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (normalmente accade) che l'array risulti ordinato prima che si sia raggiunta la N-1esima iterazione. Su questa osservazione sono basate alcune ottimizzazioni dell'algoritmo.

Analisi dell'algoritmo

Il bubble sort effettua all'incirca ${\frac {N^{2}}{2}}$ confronti ed ${\frac {N^{2}}{2}}$ scambi sia in media che nel caso peggiore.

Varianti e ottimizzazioni

Esistono numerose varianti del bubblesort, molte delle quali possono essere definite ottimizzazioni nel senso che mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni.

Un insieme di ottimizzazioni sono basate sull'osservazione che se, in una data iterazione, non avviene alcuno scambio, allora l'array è necessariamente ordinato e l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1esima iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile booleana (o equivalente) usata come "flag" che indica se l'iterazione corrente ha prodotto uno scambio. La variabile viene reimpostata a false all'inizio di ogni iterazione, e impostata a true solo nel caso in cui si proceda a uno scambio. Se al termine di una iterazione completa il valore della variabile flag è false, l'intero algoritmo viene terminato. Questa tecnica produce una riduzione del tempo medio di esecuzione dell'algoritmo, pur con un certo overhead costante (assegnamento e confronto della variabile flag).

Una seconda linea di ottimizzazione (che può essere combinata con la prima) è basata sull'osservazione che (sempre assumendo una scansione dell'array, per esempio, in avanti, e ordinamento crescente) se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore i, allora si può facilmente dimostrare che nessuna iterazione successiva eseguirà alcuno scambio in posizioni successive a tale valore i. L'algoritmo può dunque essere ottimizzato memorizzando l'indice a cui avviene l'ultimo scambio durante una iterazione, e limitando le iterazioni successive alla scansione dell'array solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo overhead (gestione della variabile aggiuntiva che indica la posizione di ultima modifica).

Un'altra variante già menzionata (lo shakersort) consente di ridurre la probabilità che si verifichi la situazione di caso peggiore (in cui tutte le ottimizzazioni precedentemente citate falliscono e quindi contribuiscono solo negativamente con i relativi overhead); vedi la voce relativa.

Implementazioni

Seguono alcune implementazioni in vari linguaggi. Le implementazioni nei diversi linguaggi non si riferiscono necessariamente alla stessa variante dell'algoritmo.

Altre implementazioni si trovano qui su wikisource

C

void BubbleSort(int* array, int elemN)
{
  register int i,tmp, ultimo;
  register int alto=elemN-1; /* indica la parte di array ancora da ordinare */
  
  while (alto >= 0){ 
    ultimo = -1; 
    for (i=0; i<alto; i++) 
      if (array[i]>array[i+1]) { /* scambiate il '>' con '<' se volete un ordinamento decrescente */
        tmp = array[i]; 
        array[i] = array[i+1]; 
        array[i+1] = tmp;
        ultimo = i; 
      } 
     alto = ultimo; 
    }
}

Due note di carattere tecnico: alcune variabili sono dichiarate come register, il ché significa che, se possibile, il compilatore C farà in modo che vengano collocate nei registri della CPU; questo renderà più rapido l'accesso a dette variabili.

tmp è dichiarata di tipo int, quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare la sua dichiarazione.

C++

#include <algorithm>
template <typename container> void bubbleSort(container &array)
{
  container::reverse_iterator  i;
  container::iterator j;
  for(i = array.rbegin(); i != array.rend(); ++i)
    for(j = array.begin(); j != i ; ++j)
      if((*j) > *(j+1) /* compara gli elementi vicini */
          std::swap(*j, *(j+1));
}

template<typename T> void bubble_sort(T *base, size_t n) {
   T *p, *q, t;    
   while (n--) { 
      for (q = (p = base) + 1; p < base + n; ++q, ++p) {
         (*p > *q) && (t = *p, *p = *q, *q = t);
      }
   }
}

Nota di carattere tecnico: in virtù dell'uso dei template (lo strumento C++ per la programmazione generica), questo estratto di codice può ordinare liste di dati di qualsiasi tipo su cui sia definito una relazione d'ordine ("<").

Java

 public void bubbleSort(int[] x) {
   int temp = 0;
   for(int j=0;j<x.length;j++) {
        for(int i=j;i<x.length;i++) {
            if(x[j]>x[i]) {
               temp=x[j]; 
               x[j]=x[i];
               x[i]=temp;
            }//fine if
        }//fine for
   }//fine for
 }//fine bubbleSort

Algoritmo implementato sui vector, in questo esempio, di oggetti di tipo String:

  public void bubbleSort(Vector v) {
     int i=0;
     //boolean ordinato = false;
     //while (i<v.size() && !ordinato) {
     while (i<v.size()) {
        //ordinato = true;
	 for(int j=i+1;j<v.size();j++) {
	    String first = (String) v.elementAt(i);
	    String next = (String) v.elementAt(j);
	    if(first.compareTo(next)>0) {
	       exchange(v,i,j);
	       //ordinato = false;
	    }
        }
	 i++;
     }
  }
	
  public static void exchange(Vector v, int i, int j) {
     Object obk = v.elementAt(i);
     v.setElementAt(v.elementAt(j),i);
     v.setElementAt(obk,j);
  }

BASIC

Sub BubbleSort(lista() As Integer, elementi As Integer)

Dim I, J, Temp As Integer
For I = elementi - 1 To 1 Step -1
  For J = 1 To I
  If lista(J) > lista(J + 1) Then
     Temp = lista(J)
     lista(J) = lista(J + 1)
     lista(J + 1) = Temp
  End If
  Next J
Next I
End Sub

Perl

sub bubble_sort(@) {
  my @a = @_;
  foreach $i (reverse 0..$#a) {
    foreach $j (0..$i-1) {
        ($a[$j],$a[$j+1]) = ($a[$j+1],$a[$j]) if ($a[$j] > $a[$j+1]);
    }
  }
  return @a;
}

Python

def bubblesort(iterable):
    seq = list(iterable)
    for passesLeft in xrange(len(seq)-1, 0, -1):
        for index in xrange(passesLeft):
            if seq[index] > seq[index + 1]:
                seq[index], seq[index + 1] = seq[index + 1], seq[index]
    return seq

Fortran

      SUBROUTINE Bubble (X,N)
      ! X e' l'array da ordinare, di dimensione N
      IMPLICIT NONE
      INTEGER :: N, J, I, JMAX, TEMP
      INTEGER :: X(N) 
      JMAX=N-1
      spike1: DO I=1,N-1
         spike2: DO J=1,JMAX
             IF(X(J).GT.X(J+1)) GO TO 100
             TEMP=X(J)
             X(J)=X(J+1)
             X(J+1)=TEMP
 100     END DO spike2
        JMAX=JMAX-1
     END DO spike1
     RETURN
     END

Lisp

(DEFUN bubble-sort (X)
  (LET ((Bubble (bubble X)))
    (IF (EQUAL X Bubble) X (bubble-sort Bubble))))

(DEFUN bubble (X)
  (COND ((NULL X) X)
        ((= (LENGTH X) 1) X)
        ((LISTP X) 
         (IF (> (CADR X) (CAR X)) 
             (CONS (CADR X) 
                   (bubble (CONS (CAR X) (CDDR X)))) 
             (CONS (CAR X) (bubble (CDR X)))))
        (T (ERROR "bubble expects a list"))))

AppleScript

-- Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1
--
on bubblesort( array )
    repeat with i from length of array to 2 by -1 --> va indietro
        repeat with j from 1 to i - 1 --> va avanti
            tell array 
                if item j > item ( j + 1 ) then
                    set { item j, item ( j + 1 ) } to { item ( j + 1 ), item j } -- swap
                end if
            end tell
        end repeat
    end repeat
end bubblesort