Bubble sort in C++, algoritmo di ordinamento a bolla

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(n²), 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.