Bubble sort

Il Bubble Sort, in italiano ordinamento a bolla, è un semplice algoritmo per ordinare gli elementi di un array.

L'algoritmo comincia con un ciclo in cui ogni elemento, a partire dall'ultimo, è confrontato con l'elemento che lo precede; se i due elementi non si trovano nell'ordine esatto vengono scambiati. Alla fine del primo ciclo inevitabilmente l'elemento 'più leggero' come una bolla sarà risalito in prima posizione. Il secondo ciclo esegue le stesse operazioni escudendo il primo elemento e così facendo risalire il secondo elemento 'più leggero' e così si prosegue fino all'orinamento completo. Se N è la lunghezza del array, occorreranno N-1 di questi cicli. E' anche possibile invertire l'ordine delle operazioni iniziando ad ordinare l'array a partire dall'ultimo elemento per poi risalire.

Questo algoritmo è usato solo per scopi didattici o quando gli elementi da ordinare sono pochi poiché, siccome richiede una quantità di confronti troppo alta, risulta molto poco efficente (dell'ordine di n²).

Implementazioni

Seguono alcune implementazioni in vari linguaggi.

Altre implementazioni si trovano qui su wikisource

C

void BubbleSort(int* array, int elemN)
{
  register int a, b,tmp=0, scambio;
  for (a=0; a<elemN-1; ++a)
  {
    scambio=0;
    for (b=a+1; b<elemN; ++b)
    {
      if (array[b] > array[b+1]) // scambiate il '>' con '<' se volete un ordinamento decrescente
      {
        tmp = array[b+1];
        array[b+1] = array[b];
        array[b] = tmp;
        scambio=1;
      }
    }
    if (!scambio) return; //esco se non ci sono stati scambi, inutile proseguire l'array è già ordinato
  }
}

Due note di carattere tecnico: a,b,tmp sono variabili 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);
      }
   }
}

Java

public void bubbleSort(int[] array)
{
  int temp = 0;
  for(int i = array.length - 1; i > 0; i--)
    for(int j = 0; j < i; j++)
      if(array[j] > array[j+1]) // compara gli elementi vicini
      {                         // scambio
         temp = array[j+1];     
         array[j+1] = array[j];
         array[j] = temp;
      }
}

BASIC

Sub Bubblesort(Array() as Integer, Length as Integer)
Dim I as Integer
Dim J as Integer
Dim Temp as Integer

   For I = Length -1 To 1 Step -1
      For J = 0 to I - 1
         IF Array(J)>Array(J+1) THEN  ' compara gli elementi vicini
            Temp = Array(j) 
            Array(J) = Array(J+1)
            Array(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 range(len(seq)-1, 0, -1):
        for index in range(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) (CDR 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 --> go backwards
        repeat with j from 1 to i - 1 --> go forwards
            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