Il Bubble Sort è un algoritmo, una serie di istruzioni, che ci permetto di ordinare gli elementi numerici di un array dal più piccolo al più grande. Viene studiato nelle scuole superiori per aiutare gli studenti a capire la logica della programmazione. Consiste nel confrontare due elementi adiacenti alla volta e spostare il numero più grande in avanti fino alla fine della lista. Una volta trovato il numero più grande, si cerca il penultimo e così via fino a quando la lista non è ordinata.
In questo articolo vediamo meglio la logica del Bubble Sort per capire cosa quali istruzioni dobbiamo dare al programma per ordinare la lista numerica. Successivamente, vedremo come si scrive l’algoritmo in alcuni dei principali linguaggi di programmazione partendo dal più semplice: Python, Java e C++.
Per capire questo argomento è importante avere un’idea di cosa sono le variabili, gli array, i cicli for e le condizioni if. Non è necessario conoscere per forza i linguaggi mostrati sotto, perché i vari passaggi verranno spiegati durante la lettura. Nella programmazione le variabili sono come dei contenitori a cui vengono dato delle etichette dove vengono inseriti dati da lavorare o gestire. Ad esempio posso creare una variabile per l’anno corrente così:
int anno = 2023L’array è come una scatola che può contenere più variabili, come i modelli delle auto oppure una lista di numeri casuali. Per quanto riguarda i modi per gestire i dati verranno fatti degli esempi più avanti mentre viene spiegato l’algoritmo. Gli esempi dell’articolo sono stati preparati tramite Visual Studio Code.
Come funziona il Bubble Sort
Il Bubble Sort non è il metodo più efficiente per ordinare una lista, soprattutto se contiene molti valori, perché richiede molti passaggi e scambi ma è tuttora utile per capire la logica degli algoritmi di ordinamento a motivo della sua semplicità.
Immaginiamo di avere i numeri 5, 3, 1, 2, 4. Al programma faremo fare quanto segue:
- Inizia a leggere i primi due numeri: se il primo è maggiore del secondo scambiali di posto;
- Fai la stessa cosa con il secondo numero e il terzo; ripeti i passaggi fino a quando non sei arrivato alla fine;
- Non considerare l’ultima posizione già sistemata e ricomincia confrontando i numeri da capo;
- Quando non ci sono più numeri da scambiare, fermati
- Mostrami la lista dei numeri in modo da verificare che tutto è a posto.
Ecco come avviene in pratica:
5, 3, 1, 2, 4
3, 5, 1, 2, 4
3, 1, 5, 2, 4
3, 1, 2, 5, 4
3, 1, 2, 4, 5
Questo è il primo ciclo: l’ultima posizione non viene più considerata e si ricomincia da capo:
3, 1, 2, 4, 5
1, 3, 2, 4, 5
1, 2, 3, 4, 5
A questo punto il programma continuerà a confrontare i numeri all’interno dell’array ma non farà nessuno scambio perché la lista è già ordinata. Appena finito tutti i confronti, il programma stamperà la lista nel terminale.
Bubble Sort in Python
A questo punto possiamo vedere come si scrive l’algoritmo del Bubble Sort su Python. Iniziamo a creare l’array con i numeri da ordinare:
array_numeri = [5,3,1,2,4]Ora l’istruzione per confrontare due numeri di una lista è la seguente:
if array_numeri[j] > array_numeri[j+1]:
temp = array_numeri[j]
array_numeri[j] = array_numeri[j+1]
array_numeri[j+1] = templa prima riga di codice verifica se la condizione è vera, cioè se il primo numero di uno stesso array, indicato con j è maggiore del secondo. Dato che la lettera j non indica un numero ma la posizione all’interno dell’array, j + 1 significa il numero che segue quello stiamo considerando.
Se la condizione è falsa, il programma non farà nulla ma leggerà il resto del codice per fare altro oppure si fermerà se non ci sono altre istruzioni. Se la condizione è vera il programma farà ciò che segue:
- Creerà un variabile temp e ricopierà il primo numero che abbiamo confrontato per non perderlo;
- Alla posizione del primo numero verrà inserito il secondo numero e il primo verrà cancellato;
- Nella posizione del secondo numero verrà inserito il valore del primo ricopiandolo dalla variabile temporanea.
Il risultato al momento sarà:
5, 3, 1, 2, 4
3, 5, 1, 2, 4
Ma in questo caso, se il programma funzionasse confronterebbe soltanto i primi due numeri continuamente (in realtà, non farebbe nulla perché non sa che cosa sia ancora j). Come facciamo a fargli fare tutti i passaggi della lista?
Usando un ciclo for, possiamo dire al programma di passare al secondo numero e confrontarlo con il terzo, poi passare al terzo e confrontarlo con il quarto fino a quando non arriva alla fine. Il codice adesso sarà:
array_numeri = [5,3,1,2,4]
n_elementi_array = len(array_numeri)
for j in range(n_elementi_array - 1):
if array_numeri[j] > array_numeri[j+1]:
temp = array_numeri[j]
array_numeri[j] = array_numeri[j+1]
array_numeri[j+1] = temp
print("Array ordinato: ", array_numeri)Adesso abbiamo aggiunto una nuova variabile che conta la lunghezza dell’array, cioè il numero di elementi al suo interno. Abbiamo poi avviato un ciclo, indicando con j la posizione del primo elemento, che aumenta fino a raggiungere la penultima posizione della lista.
L’istruzione for j in range() significa che j aumenta ogni volta che tutte le condizioni al suo interno, in questo caso if, vengano completate. Il valore di j, ma potrebbe essere qualsiasi lettera o nome, inizia sempre da 0 e non supera mai il valore di range. Il range, in questo caso, è n_elementi_array – 1, perché l’ultimo numero non ha un successivo con cui confrontarsi.
Il risultato fino a questo momento sarà:
5, 3, 1, 2, 4
3, 5, 1, 2, 4
3, 1, 5, 2, 4
3, 1, 2, 5, 4
3, 1, 2, 4, 5
Cioè la prima serie di passaggi. Tuttavia, adesso il programma dovrebbe ricominciare da capo e trovare il numero maggiore per le restanti posizioni. Basterà inserire tutto all’interno di un altro ciclo:
array_numeri = [5,3,1,2,4]
n_elementi_array = len(array_numeri)
for i in range(n_elementi_array - 1):
for j in range(n_elementi_array - i - 1):
if array_numeri[j] > array_numeri[j+1]:
temp = array_numeri[j]
array_numeri[j] = array_numeri[j+1]
array_numeri[j+1] = temp
print("Array ordinato: ", array_numeri)Abbiamo inserito un ciclo con la variabile i che arriverà fino alla penultima posizione della lista. Il ciclo for per j farà lo stesso procedimento mostrato sopra, soltanto che questa volta, il range non conterà più le posizioni dell’array che abbiamo già occupato con il numero più grande.
Nel primo passaggio, i = 0 e perciò il range sarà sempre n_elementi_array – 1; Quando i sarà uguale a 1, il range sarà n_elementi_array – i – 1, cioè 5 -1 – 1, quindi 3 non guardando più gli ultimi due numeri della lista. Il programma continuerà così fino a quando non ci saranno più scambi.
L’algoritmo Bubble Sort in Java e in C++
L’algoritmo Bubble Sort può essere scritto anche negli altri linguaggi di programmazione, seguendo le loro sintassi.
Ecco l’esempio in Java:
/**
* bubble-sort
*/
public class bubbleSort {
public static void main(String[] args) {
int[] array_numeri = {5,1,4,2,3};
BubbleSort(array_numeri);
System.out.println("Array ordinato: ");
for (int num : array_numeri) {
System.out.print(num + " ");
}
}
public static void BubbleSort(int[] nome_array) {
int n_elementi_array = nome_array.length;
for(int i = 0; i < n_elementi_array - 1; i++) {
System.out.println(nome_array[i]);
for(int j = 0; j < n_elementi_array - i - 1; j++) {
if (nome_array[j] > nome_array[j+1]) {
int temp = nome_array[j];
nome_array[j] = nome_array[j+1];
nome_array[j+1] = temp;
}
}
}
}
}In Java si inizia sempre creando la classe, che rappresenta il programma che stiamo creando. Questo perché Java è un linguaggio di programmazione orientato agli oggetti e promuove l’organizzazione del codice all’interno di classi.
All’interno della classe si crea una funzione principale, chiamata main, che viene richiamata automaticamente quando si testa o si apre il programma. Questa volta l’algoritmo principale è stato inserito in una funzione a parte, chiamata BubbleSort, e richiamato nel main quando necessaro.
In C++, ci sono due modi. Il primo è inserire tutto in un file:
#include <iostream>
using namespace std;
/// @brief Stampa gli elementi di un array in colonna
/// @param nome_array
/// @param n_elementi_array
void Stampa_array(int nome_array[], int n_elementi_array);
/// @brief Ordina gli elementi di un array dal più piccolo al più grande
/// @param nome_array
/// @param n_elementi_array
/// @return
int BubbleSort(int nome_array[], int n_elementi_array);
int main(int argc, char const *argv[])
{
int array_numeri[5] = {5, 1, 4, 2, 3};
int n_elementi_array = 5;
cout << "Array originale: " << endl;
Stampa_array(array_numeri, n_elementi_array);
BubbleSort(array_numeri,n_elementi_array);
cout << "Array ordinato: " << endl;
Stampa_array(array_numeri, n_elementi_array);
return 0;
}
void Stampa_array(int nome_array[], int n_elementi_array)
{
for (int i = 0; i < n_elementi_array; i++)
{
cout << nome_array[i] << endl;
}
}
int BubbleSort(int nome_array[],int n_elementi_array) {
for (int i = 0; i < n_elementi_array - 1; i++)
{
for (int j = 0; j < n_elementi_array - i - 1; j++)
{
if (nome_array[j] > nome_array[j + 1])
{
int temp = nome_array[j];
nome_array[j] = nome_array[j + 1];
nome_array[j + 1] = temp;
}
}
}
return 0;
}
Nel caso di C++ bisogna aggiungere le librerie anche per stampare informazioni sul terminale manualmente: <iostream> serve proprio per questo mentre il namespace std è per la gestione delle stringhe di testo.
Anche C++, come Java, ha una funzione principale chiamata main, ed è questa funzione che fa partire e funzionare il programma.
Questa volta sono state create due funzioni: una per l’ordinamento delle stringhe e un’altra per la stampa della lista, una volta senza essere ordinata e infine per verificare che tutto è a posto. Le funzioni devono essere dichiarate prima del main ma possono essere completate dopo.
Un’altra pratica molto comune è quella di creare un file di intestazione con lo stesso nome del file cpp, contenente soltanto le dichiarazioni.
Abbiamo così il file BubbleSort.h:
#ifndef BUBBLE_SORT_H
#define BUBBLE_SORT_H
/// @brief Stampa gli elementi di un array in colonna
/// @param nome_array
/// @param n_elementi_array
void Stampa_array(int nome_array[], int n_elementi_array);
/// @brief Ordina gli elementi di un array dal più piccolo al più grande
/// @param nome_array
/// @param n_elementi_array
/// @return
int BubbleSort(int nome_array[], int n_elementi_array);
#endifE il file BubbleSort.cpp:
#include "bubbleSort.h"
#include <iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int array_numeri[5] = {5, 1, 4, 2, 3};
int n_elementi_array = 5;
cout << "Array originale: " << endl;
Stampa_array(array_numeri, n_elementi_array);
BubbleSort(array_numeri, n_elementi_array);
cout << "Array ordinato: " << endl;
Stampa_array(array_numeri, n_elementi_array);
return 0;
}
void Stampa_array(int nome_array[], int n_elementi_array)
{
for (int i = 0; i < n_elementi_array; i++)
{
cout << nome_array[i] << endl;
}
}
int BubbleSort(int nome_array[],int n_elementi_array) {
for (int i = 0; i < n_elementi_array - 1; i++)
{
for (int j = 0; j < n_elementi_array - i - 1; j++)
{
if (nome_array[j] > nome_array[j + 1])
{
int temp = nome_array[j];
nome_array[j] = nome_array[j + 1];
nome_array[j + 1] = temp;
}
}
}
return 0;
}
Esercizi
Ecco alcuni esercizi per capire meglio l’algoritmo del Bubble Sort:
- Riscrivere il codice Python in inglese. Provare anche a creare una classe con le sue funzioni per rendere il codice più leggibile e modulare.
- Provare a creare il Bubble Sort in C# creando un progetto in Visual Studio.
- Creare un progetto Java o C++ inserendo il codice in inglese.