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.
Parlo del bubble sort anche nel libro:
Implementazione bubble sort in C++
Innanzitutto inseriamo gli elementi nell’array e dopo procediamo all’ordinamento.
Banner Pubblicitario
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.
Banner pubblicitario
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!