Informatica 2 Liceo Scientifico Scienze Applicate/BubbleSort

Ordinare un vettore: l'algoritmo del BubbleSort

Per ordinare gli elementi di un vettore dal piu' piccolo al piu' grande si possono usare diversi algoritmi, quello piu' semplice da spiegare e' il BubbleSort e quello piu' veloce e' il QuickSort. Un algoritmo e' un particolare programma che risolve una classe di problemi (nel nostro caso l'ordinamento degli elementi di un vettore) con una certa efficienza ( generalmente espressa in termini di velocita' di calcolo).

Bubblesort

Per ordinare un vettore di n elementi bisogna fare n-1 passate, ad ogni passata l'elemento piu' piccolo rimasto nella parte di vettore ancora da ordinare viene spostato nella posizione corretta, per ordinare il vettore bastano n-1 passate perché sistemati i primi n-1 elementi anche l'ultimo numero e' per forza di cose al posto giusto. In una singola passata , pensiamo sia la passata i-esima si prendono in considerazione tutti gli elementi partendo dall'ultimo (indice n-1) fino a quello con l'indice con lo stesso numero della passata, ogni elemento considerato ad esempio quello k-esimo viene confrontato con quello che lo precede k-1-esimo e se vett[k] < vett[k-1] i due elementi del vettore si scambiano fra loro , altrimenti si passa a considerare l'elemento successivo. Facciamo un esempio , vettore di 6 elementi , passate da fare 5, nella prima passata si ha

come si vede, alla fine della prima passata il vettore e' composto da due parti una ordinata (colore verde) che contiene il numero piu' piccolo (2) e una che deve essere ancora ordinata, la seconda passata si occupa di ordinare soltanto di quest'ultima, si vede che per fare la prima passata bisogna considerare via via gli elementi in giallo con il corrispondente elemento che lo precede, sono queste coppie di valori che vengono confrontate ed eventualmente scambiate fra loro. Nella seconda passata si ha:

il vettore ordinato e' composto ora da due numeri e il vettore da ordinare e' diventato piu' piccolo, si nota che il numero di confronti che si devono fare si riduce di conseguenza di una unità ad ogni passata.Vediamo la passata 3

Vediamo la passata 4

vediamo la passata 5

si nota che durante la passata 4 non ci sono stati scambi , quando non ci sono scambi durante tutta una passata il vettore risulta ordinato e ele passate successive non sono piu' necessarie, in questa spiegazione e nel programma seguente non utilizzeremo questa particolarita' che consente di velocizzare la fine dell'algoritmo.

Il programma e' caratterizzato da un primo ciclo for che conta le passate ( conta da 1 ) e all'interno della singola passata c'e un secondo for che prende in analisi i diversi elementi J (partendo dal fondo n-1 fino a quello di indice pari al numero della passata) che devono essere confrontati con l'elemento del vettore che lo precede J-1 , si nota poi la necessita' dell'uso della variabile temp per poter scambiare due celle di un vettore senza perdersi uno dei valori delle celle.
In questo programma l'ordinamento e' fatto su un vettore di stringhe (parole), in questo caso l'ordinamento e' quello alfabetico (antonella minore di zorro)

BubbleSort

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

/* dato un vettore disordinato  ordinarlo con il bubblesort
   e poi stamparlo
*/    

int main(int argc, char *argv[])
{
  int n=5;
  string vett[5];
  int i,j;
  string temp;
  
  for (i=0;i<n;i++)
     { cout<<"inserisci il "<<i<<" elemento ";
       cin>>vett[i];
     }
     
  cout<<"stampa vettore disordinato"<<endl;
  for (i=0;i<n;i++)
     { cout<<vett[i]<<" , ";
     }
  cout<<endl;
 
//Bubblesort
 
  for (i=1;i<n;i++)
     for ( j= n-1;j>=i;j--)
        if(vett[j]<vett[j-1])
          { temp= vett[j];
            vett[j]=vett[j-1];
            vett[j-1]=temp;
          } 
     
  cout<<"stampa vettore ordinato"<<endl;
  for (i=0;i<n;i++)
     { cout<<vett[i]<<" , ";
     }
  cout<<endl;     
  
  system("PAUSE");            
  return 0;
}

L'efficienza di un algortimo viene espressa con l'ordine di complessita', generalmente esso dipende dal numero n di elementi del vettore, se le operazioni da fare per completare l'algoritmo fossero proporzionali al numero di elementi del vettore l'ordine di complessità sarebbe indicato come $O(n)$ e si legge O grande di n. Nel caso del bubblesort le cose vanno peggio di O(n) e i calcoli da farsi sono proporzionalia a $n^{2}$ secondo un fattore di proporzionalita' di 0.5 si ha allora $O({\frac {n^{2}}{2}})$. Per il quicksort l'ordine di complessita' e' del $O(n\log _{2}n)$ , meglio del bubblesort ma peggio di un andamento solamente proporzionale ad n . Vediamo in un grafico l'andamento delle istruzioni da effettuare in 3 casi diversi di complessita'