Implementazioni di algoritmi/Bubble sort

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Sviluppo · modifica il template

Copertina Implementazioni di algoritmi/Copertina

Il bubble sort o bubblesort (letteralmente: ordinamento a bolle) è un semplice algoritmo di ordinamento per ordinare array. Non è un algoritmo efficiente: ha una complessità computazionale (misurata in termini di numero di confronti) O(n²); si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità. Dell'algoritmo esistono numerose varianti, 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).

Indice

[modifica] 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. Il tempo di esecuzione dell'algoritmo è Θ(n2).

[modifica] Implementazioni

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

[modifica] C

void BubbleSort(int array[], int elemN)
 {
   int i, tmp;
   int alto=elemN; /* elemN è il numero degli elementi del vettore da ordinare */
 
   while (alto > 1) /* in questo modo si evita 1 passaggio*/
     { 
         for (i=0; i<alto-1; i++)
         {
           if (array[i]>array[i+1]) /* sostituire ">" con "<" per avere un ordinamento decrescente */
           { 
             tmp = array[i]; 
             array[i] = array[i+1]; 
             array[i+1] = tmp;
           } 
         }
     alto--; 
     }
 }

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

[modifica] Java

public void bubbleSort(int[] x) 
    {
    int temp = 0;
    int j = x.length-1;
    while(j>0) 
      {
      for(int i=0; i<j; i++) 
        {
        if(x[i]>x[i+1])   //scambiare il '>' con '<' per ottenere un ordinamento decrescente
          {
          temp=x[i]; 
          x[i]=x[i+1];
          x[i+1]=temp;
          }
        }
      j--; 
      }
    }

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

public void bubbleSort(Vector v) 
     {
     String first;
     String next;
     int i = v.size();
     while(i>0) 
       {
       for(int j=0; j < i; j++) 
         {
         first = (String) v.elementAt(j);
         next = (String) v.elementAt(j+1);
         if(first.compareTo(next)>0)   /*scambiare il '>' con '<' per ottenere un ordinamento decrescente*/
           exchange(v,j,j+1);
         }
       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);
     }

[modifica] BASIC

Sub BubbleSort(ByRef MioArray() As Integer)
 Dim I, J, Temp As Integer
 For I = UBound(MioArray, 1) To LBound(MioArray, 1) Step -1
   For J = LBound(MioArray, 1) To I - 1
     If MioArray(J) > MioArray(J + 1) Then   'scambiare il ">" con "<" per ottenere un ordinamento decrescente
       Temp = MioArray(J)
       MioArray(J) = MioArray(J + 1)
       MioArray(J + 1) = Temp
     End If
   Next J
 Next I
End Sub

MioArray e tmp sono dichiarati di tipo Integer, quindi dovranno contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare le dichiarazioni di entrambi.

[modifica] Ruby

def bubble(v)
     tmp=v.length
 
     while tmp > 0
         (tmp-1).times{|i|
             if v[i] > v[i+1]
                 v[i] , v[i+1] = v[i+1] , v[i] #scambia v[i] con v[i+1] alla maniera del Ruby!
             end
         }
         tmp-=1
     end
 end

[modifica] 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;
 }

[modifica] 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

[modifica] 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
          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
      END DO spike1
      RETURN
      END

[modifica] 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"))))

[modifica] AppleScript

on bubblesort( array )
     repeat with i from 1 to length of array
         repeat with j from 1 to length of array - 1
             tell array 
                 if item j > item ( j + 1 ) then
                     set { item j, item ( j + 1 ) } to { item ( j + 1 ), item j } 
                 end if
             end tell
         end repeat
     end repeat
 end bubblesort

Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1

[modifica] Altri progetti

Ricavato da "http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Bubble_sort"
Strumenti personali
Altre lingue