L'ordinamento in informatica è sicuramente una delle funzionalità più necessarie ed importanti, uno tra gli algoritmi maggiormente noti ed utilizzati per la sua semplicità è l'algoritmo del Bubble Sort.
Il BubbleSort è un'algoritmo iterativo di ordinamento degli elementi di un array molto usato soprattutto in ambito didattico, per far apprendere le logiche e le basi della programmazione. Il suo nome deriva dal fatto che gli elementi vengono ordinati secondo una logica che li estrae dall'insieme mettendoli in cima al vettore con un'alogia grafica a quella delle bollicine che salgono in un bicchiere di spumante.
Dato un numero n di elementi di qualsiasi tipo, ma tali che esista una relazione di ordinamento tra di loro, l'algoritmo del bubblesort consente di ordinarli in modo crescente o decrescente. Del bubblesort solitamente vi sono svariati esempi in Linguaggio C, in questo articolo vogliamo invece fornirne una versione in Linguaggio C#, mostrando come implementare l'algoritmo del bubble sort in C# in modo efficiente.
Concentreremo l'attenzione solo sul cuore del bubblesort e passo passo vedremo come apportare le varie migliorie per diminuire il numero d'iterazioni ed ottimizzare al massimo l'algoritmo del bubble sort sviluppato in C#.
Supponiamo di voler ordinare un array di 100 elementi numerici in ordine crescente, la prima parte del codice C# sarà così composta:
/// <summary>
/// Funzione per implementare l'algoritmo del Bubble Sort in C#
/// </summary>
public static void BubbleSortCSharp()
{
int[] vett = new int[100]; //array di 100 interi contenente gli elementi da ordinare
int temp = 0; //variabile temporanea per lo scambio degli elementi
//ciclo di ordinamento
for(int j=0; j < (vett.Length - 1); j++)
for(int i=0; i < (vett.Length - 1); i++)
if(vett[i] > vett[i+1])
{
temp = vett[i];
vett[i] = vett[i+1];
vett[i+1] = temp;
}
...
Come si vede dal codice nel ciclo più interno gli elementi vengono confrontati e se quello antecedente (vett[i]) risultasse più grande di quello successivo (vett[i+1]) i valori vengono scambiati tramite l'ausilio della variabile d'appoggio (temp). Questo confronto viene ripetuto cento meno una volta (1 < vett[].Lenght -1, dove lenght è la lunghezza dell'array che è appunto 100), questo non basta però ad assicurarci l'ordinamento degli elementi poichè abbiamo solamente spostato l'elemento più pesante (o più grande) in fondo al vettore, quindi dobbiamo ripetere questo ciclo altre n - 1 volte, ed ecco giustificato il for più esterno che si ripeterà nel nostro caso 99 volte, ovvero Lenght - 1, con lenght uguale a 100.
In questo modo abbiamo già un primo algoritmo che ci permette un'ordinamento completo, questo codice però è poco efficiente, in quanto ripete per n-1 volte il ciclo esterno anche nel caso in cui l'array risultasse già ordinato. Supponiamo di avere la sequenza di numeri: 9, 24, 67, 52, 75, 88. In questo caso l'unico scambio da fare è quello tra il 67 ed il 52 ed il vettore risulterà di per sè ordinato, è inutile iterare il ciclo ulteriormente, quindi possiamo ottimizzare il codice precedente inserendo un controllo che interrompi il ciclo esterno nel caso in cui in quello interno non sia avvenuto nessuno scambio, vediamo il codice modificato:
/// <summary>
/// Funzione per implementare l'algoritmo del Bubble Sort in C#
/// </summary>
public static void BubbleSortCSharp()
{
int[] vett = new int[100]; //array di 100 interi contenente gli elementi da ordinare
int temp = 0; //variabile temporanea per lo scambio degli elementi
int flag = 0; //variabile di controllo sul ciclo esterno
do
{
flag = 0; //reiniziallizzo a zero il flag
for (int i = 0; i < (vett.Length - 1); i++)
if (vett[i] > vett[i + 1])
{
temp = vett[i];
vett[i] = vett[i + 1];
vett[i + 1] = temp;
flag = 1; //se avviene lo scambio modifico il valore del flag
}
}
while (flag == 1);
...
Dichiariamo esternamente al ciclo una variabile intera (flag) per effettuare un controllo sul ciclo più esterno, per ogni iterazione del ciclo più interno se vi è un valore da scambiare e quindi vett[i] > vett[i+1] si entrerà nel blocco dell'if assegnando a flag il valore 1 e l'iterazione esterna si ripeterà (while flag == 1). Se invece non avviene alcuno scambio, flag resterà a zero e la condizione "while flag == 1" non sarà più verificata facendo terminare immediatamente l'algoritmo del bubble sort, risparmiando così tutti gli ulteriori n-x cicli rimanenti rispetto al codice precedente, poichè se il flag resta a zero (ad ogni nuova iterazione esterna viene reinizializzato a zero) siamo certi che non vi è più alcun elemento da ordinare.
Riflettendo bene però su quanto detto prima, possiamo apportare un'ulteriore miglioria al nostro algoritmo bubblesort, infatti abbiamo detto che il ciclo più interno ripetuto n-1 volte sposta ogni volta l'elemento più pesante in fondo all'array, quindi siamo certi che ad ogni ciclo l'elemento più grande sarà in fondo al vettore, allora perchè esaminarlo nuovamente? Possiamo così diminuire il numero d'iterazioni del ciclo interno di uno ad ogni nuova iterazione, vediamo come cambia nuovamente il codice:
/// <summary>
/// Funzione per implementare l'algoritmo del Bubble Sort in C#
/// </summary>
public static void BubbleSortCSharp()
{
int[] vett = new int[100]; //array di 100 interi contenente gli elementi da ordinare
int temp = 0; //variabile temporanea per lo scambio degli elementi
int flag = 0; //variabile di controllo sul ciclo esterno
int k = 1; //variabile per la diminuzione delle iterazioni sul ciclo interno
do
{
for (int j = 0; j < (vett.Length - 1); j++)
{
flag = 0; //reiniziallizzo a zero il flag
for (int i = 0; i < (vett.Length - k); i++)
if (vett[i] > vett[i + 1])
{
temp = vett[i];
vett[i] = vett[i + 1];
vett[i + 1] = temp;
flag = 1; //se avviene lo scambio modifico il valore del flag
}
k++; //incremento k per diminuire n (ovvero Lenght)
}
}
while (flag == 1);
...
Come vedete ho inserito un'ulteriore variabile contatore (k) inizializzondola ad 1, dopodichè ad ogni fie iterazione la incremento di un'unità (k++), questo mi serve per decrementare i numeri d'iterazioni del ciclo interno ( vett.Lenght - k ) poichè certi che per i cicli già compiuti l'elemento più grande si trova in fondo all'array.
Infine è possibile effettuare un'ulteriore miglioria, togliamo la variabile k, anzichè decrementare di uno per volta il numero d'iterazioni interne, cerchiamo di fare in modo che queste terminino nel punto in cui al ciclo precedente si è avuto lo scambio, possiamo farlo poichè siamo certi che da lì in poi gli elementi dell'array saranno già ordinati, il codice allora si trasforma in questo modo:
/// <summary>
/// Funzione per implementare l'algoritmo del Bubble Sort in C#
/// </summary>
public static void BubbleSortCSharp()
{
int[] vett = new int[100]; //array di 100 interi contenente gli elementi da ordinare
int temp = 0; //variabile temporanea per lo scambio degli elementi
int flag = 0; //variabile di controllo sul ciclo esterno
int n = vett.Length; //variabile inizializzata alla dimensione dell'array
int p = vett.Length; //variabile per fermarsi al punto del ciclo precedente
do
{
flag = 0; //reiniziallizzo a zero il flag
for (int i = 0; i < (n - 1); i++)
if (vett[i] > vett[i + 1])
{
temp = vett[i];
vett[i] = vett[i + 1];
vett[i + 1] = temp;
flag = 1; //se avviene lo scambio modifico il valore del flag
p = i + 1; //assegno a p il valore del punto in cui avviene lo scambio
}
n = p; //assegno ad n (lunghezza array) il valore di p per interrompere in questo punto
}
while (flag == 1);
...
Ho dovuto dichiarare due variabili ed inizializzarle entrambe alla lunghezza dell'array, poichè una (p) ci serve per la nostra ottimizzazione, interrompere il bubblesort al punto precedente dello scambio, e l'altra (n) ci è servita poichè fino adesso come lunghezza avevamo usato la proprietà "Lenght" del nostro array ed in questo caso l'abbiamo dovuto sostituire con n per fare le nostre opportune assegnazioni (n = p) e controlli (i < n -1).
Conclusioni
Bene, questo è l'algoritmo del bubble sort in C# ottimizzato al meglio, ciò nonostante il bubblesort non è tra gli algoritmi di ordinamento più efficienti poichè anche nella sua versione ottimizzata possiede una complessità computazionale pari ad "O di n al quadrato", ad ogni modo è molto semplice d'applicare e garantisce comunque buoni risultati, e poi dal punto di vista didattico è sempre un'ottimo esercizio.
Chiunque voglia aggiungere qualcosa in merito all'argomento, porre una domanda o dare un suggerimento, ogni commento è ben accetto.