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