In questa lezione svilupperemo l’algoritmo bubble sort in C++. Il bubble sort è l’algoritmo di ordinamento più semplice da implementare, ma è anche poco efficiente.
Il bubble sort è utilizzato in ambito didattico per far apprendere le logiche e le basi della programmazione.
Il metodo che utilizza consiste nel confrontare elementi vicini tra loro portando l’elemento maggiore in ultima posizione durante la prima “passata” (eseguendo n-1 confronti), poi il secondo massimo in penultima posizione e così via finché l’array non è ordinato.
La complessità è O(n2), sia nel caso peggiore che nel caso migliore.

Implementazione bubble sort in C++
Innanzitutto inseriamo gli elementi nell’array e dopo procediamo all’ordinamento.
Per fare l’ordinamento, confronto se l’elemento in posizione i è maggiore dell’elemento in posizione i +1. Se è vero effettuo lo scambio. Per scambiare gli elementi utilizzo una variabile di appoggio temp.
Il ciclo interno non è sufficiente per effettuare l’ordinamento. Dunque per ottenere l’ordinamento completo bisogna ripetere n-1 volte il procedimento e questo lo otteniamo con un ciclo for più esterno controllato dall’indice j che va da 0 a n-1.
Dunque segue il listato del bubble sort in C++.
#include<iostream>
#define N 10
using namespace std;
int main()
{
int a[N],i,j,temp;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
for(j=0;j<N-1;j++)
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
cout<<"Array ordinato con bubble sort:";
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Come potete notare l’algoritmo è molto semplice, ma purtroppo poco efficiente perché anche nel caso in cui l’array fosse ordinato ripeterebbe in ogni caso n-1 volte il ciclo esterno.

Ottimizzazione bubble sort – ordinamento per scambio con sentinella
Pensiamo a delle ottimizzazioni dell’algoritmo. Ad esempio interrompendo il ciclo esterno se al termine del ciclo interno non si è fatto nessuno scambio.
Quindi utilizziamo una variabile flag che inizializzo a zero. Dopo, nel ciclo interno se effettuo almeno uno scambio la variabile flag la imposto uguale a 1. Potevo anche utilizzare una variabile booleana.
Se rimane a zero, vuol dire che non c’è nulla da ordinare e quindi interrompo il ciclo esterno.
Con valori iniziali poco disordinati questa prima ottimizzazione porta ad un certo guadagno di tempo.
Ecco dunque il listato completo del bubble sort in C++ ottimizzato.

#include<iostream>
using namespace std;
#define N 10
int main()
{
int a[N],i,j,temp,k;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
do {
k=0;
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
k=1;
}
} while (k==1);
cout<<"Array ordinato con bubble sort:";
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}

Seconda ottimizzazione dell’algoritmo bubble sort in C++
Un’altra possibile ottimizzazione si può ottenere considerando che ad ogni incremento di j almeno gli ultimi j+1 elementi sono già ordinati. Questa considerazione è possibile perché di volta in volta, per ogni iterazione, l’elemento più grande è spostato verso destra.
Quindi ad ogni iterazione accorciamo il ciclo dei confronti. Infatti all’n-esima iterazione si può fare a meno di toccare gli ultimi n-1 elementi che ormai sono nella loro posizione definitiva. Dunque decrementiamo n di uno ad ogni iterazione (- -n), in modo da diminuire di 1, di volta in volta, il numero dei confronti effettuati.
Ecco dunque il listato modificato del bubble sort in C++.
#include<iostream>
using namespace std;
int main()
{
int N=6;
int a[N],i,j,temp,k;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
do {
k=0;
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
k=1;
}
--N;
} while (k==1);
cout<<"Array ordinato con bubble sort ottimizzato:";
N=6;
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Terza ottimizzazione

Facciamo un’ulteriore ottimizzazione all’algoritmo bubble sort. Infatti consideriamo che ogni ciclo interno si interrompe proprio dove, la volta prima, è avvenuto lo scambio. Pertanto alla fine di ogni iterazione più elementi si trovano nella posizione definitiva e si può evitare di trattarli.
Quindi memorizziamo in una variabile x la posizione i+1 dell’ultimo scambio e ad n assegniamo il valore di x.
#include<iostream>
using namespace std;
int main()
{
int N=6;
int a[N],i,j,temp,k,x;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
do {
k=0;
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
k=1;
x=i+1;
}
N=x;
} while (k==1);
cout<<"Array ordinato con bubble sort ottimizzato:";
N=6;
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Questi esempi di implementazione del bubble sort in C++ sono utili a scopo didattico.

Alcuni link utili
Indice tutorial linguaggio C++
Esercitazione sugli array in C++
Passaggio di parametri per valore o per riferimento
Equazioni di secondo grado in C++
Le variabili globali e locali in C++
Definizione di funzioni in C++
Esercizi con switch case in C++
Successione di Fibonacci in C++

no
Grazie!