Implementazioni di algoritmi/Bubble sort

Indice del libro

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).

Analisi dell'algoritmo

modifica

Il bubble sort effettua all'incirca confronti ed scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è Θ(n2).

Implementazioni

modifica

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

#include <stdlib.h>
#include <stdio.h>

int main(){
    int array[100];  //Poniamo il caso "array" contenga 100 numeri in ordine sparso
    int n1=0;  //Contatore 1
    int n2=0;  //Contatore 2
    int temp=0;  //Variabile di supporto
    
    for(n1=0; n1<100; n1++){
        for(n2=0; n2<100-n1-1; n2++){
            if(array[n2]>array[n2+1]){  //Scambio valori
                temp=array[n2];
                array[n2]=array[n2+1];
                array[n2+1] = temp;
	    }
        }
    }
}
// elemN è il numero degli elementi del vettore da ordinare
void BubbleSort(int *array, int elemN){
    int alto;
    for (alto = elemN - 1; alto > 0; alto--) 
        for (int i=0; i<alto; i++)
            if (array[i] > array[i+1]){ /* sostituire ">" con "<" per avere un ordinamento decrescente */
                int tmp = array[i]; 
                array[i] = array[i+1]; 
                array[i+1] = tmp;
            } 
 }

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

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

Implementazione dell'algoritmo che presenta le ottimizzazioni enunciate alla voce Bubble sort:

void bubbleSort(int[] array) {
  boolean swapped = true;
  int upperBound = array.length - 1;
  int lastSwapIndex = 0;
  int temp;
  while (swapped && upperBound > 0) {
    swapped = false;
    for (int i = 0; i < upperBound; i++) {
      if (array[i] > array[i + 1]) { //scambiare il '>' con '<' per ottenere un ordinamento decrescente
        temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
        lastSwapIndex = i;
      }
    }
    upperBound = lastSwapIndex;
  }
}

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);
     }

Segue una documentata implementazione Java dell'algoritmo di sort a bolle,
pensata da uno studente del dipartimento di informatica (ITPS) di Bari:

   /**
    * Questo algoritmo di sort a bolle, si basa sul
    * confronto, passo dopo passo, dell'elemento corrente (dell' indice)
    * con quello precedente (confronto tra coppie adiacenti).
    * Se quello precedente e' maggiore di quello corrente
    * viene effettuato lo scambio.
    *
    * Descrizione dettagliata:
    * La variabile passo corrisponde al passo corrente, ovvero al numero
    * di elementi gia' ordinati.
    * Se nel passo sono stati effettuati scambi (lo sappiamo grazie alla
    * variabile booleana scambio) allora significa che l'array non e' ancora
    * ordinato e quindi bisogna continuare con il prossimo passo.
    * Se, invece, in un intero passo non sono stati effettuati scambi (nel
    * ciclo interno do-while) allora l'array e' ordinato e quindi si puo'
    * uscire dall' intero algoritmo.
    * Cosi' facendo si riesce a far risalire a galla ordinatamente le
    * stringhe più' piccole fra quelle in esame.
    * Ho pensato ad un ciclo do-while e non un while, perché
    * altrimenti l'ultimo elemento (quello la cui posizione e' maggiore
    * del passo) non verrebbe ordinato.
    * Nel caso peggiore si esce dall'algoritmo solo quando il passo supera
    * la posizione dell'ultimo elemento dell'array, e questo si verifica
    * ad esempio quando gli elementi da ordinare sono in un ordine inverso.
    * L'ordine di complessita' e' quadratico [MAX (n)*(n-1)/2 ],
    * ma l'algoritmo, grazie alla variabile sentinella scambio,
    * risulta ottimizzato.
    */
    public void sort() {
        String temp = "";
        String[] strings = {"ciao", "come", "stai"};
        int indice = 0;
        //variabile sentinella di scambio.
        boolean scambio = true;
        if (strings.length > 1) {
            //Il ciclo esterno si occupa di incrementare il passo se, e solo se,
            //il passo corrente e' minore del numero di stringhe presenti nell'
            //array e se sono stati effettuati scambi nel passo precedete.
            for (int passo = 0; passo <= (strings.length - 1)
                    && (scambio); passo++) {
                //impostiamo indice all'ultimo elemento presente nell'array.
                indice = strings.length - 1;
                scambio = false;
                do {
                    if (strings[indice].compareToIgnoreCase(
                          strings[indice - 1]) < 0) {
                            temp = strings[indice];
                            strings[indice] = this.strings[indice - 1];
                            strings[indice - 1] = temp;  
                            //Sono stati effettuati scambi,quindi scambio sara'true.
                            scambio = true;
                    }
                    indice--;
                } while (indice > passo);
            //Non e'difficile notare che mentre il passo aumenta da sinistra,
            //da destra vengono man mano ordinati sempre meno elementi.
            }
        }
    }
 Sub BubbleSort(ByRef MioArray() As Integer)
 
   For I = LBound(MioArray, 1) To UBound(MioArray, 1) -1 
      For J = I + 1  To UBound(MioArray, 1) 
         If MioArray(I) > MioArray(J) Then   'scambiare il ">" con "<" per ottenere un ordinamento saliente
            SWAP MioArray(I),MioArray(J)
         End If
      Next J
   Next I
 End Sub

''MioArray'' sono dichiarati di tipo ''Integer'', quindi dovranno contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare le dichiarazioni di entrambi.
 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
 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;
 }
 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
       SUBROUTINE Bubble (X,N)
       ! X e' l'array da ordinare in modo non decrescente, di estensione N
       IMPLICIT NONE
       INTEGER :: N, J, I, TEMP
       INTEGER :: X(N) 
       spike1: DO I=1,N
          spike2: DO J=1,N-1
              IF(X(J)<X(J+1)) CYCLE
              TEMP=X(J)
              X(J)=X(J+1)
              X(J+1)=TEMP
          END DO spike2
       END DO spike1
       RETURN
       END
       ! GO TO [label] è un'istruzione deprecata da FORTRAN77 e condannata dal Th. di Böhm-Jacopini.
 (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"))))
 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

function bubbleSort ($array)
{
	$alto= count ($array);
 
	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--; 
	}
}
function vettore = bubblesort(a)
for k=numel(a)-1:-1:1  
for i=1:k
        if(a(i+1)<a(i))
            tmp=a(i);
            a(i)=a(i+1);
            a(i+1)=tmp;
        end
            vettore=a
    end
end
end

Altri progetti

modifica