L’ordinamento di una lista di oggetti è uno dei problemi fondamentali del calcolo automatico. Esistono diverse soluzioni per effettuare questa operazione ed esse rientrano nell’area dei cosiddetti algoritmi di ordinamento. Alcuni di questi algoritmi sono semplici e intuitivi, mentre altri sono più complessi e permettono di ottenere prestazioni migliori.
Tra i più conosciuti e diffusi algoritmi di ordinamento vi sono:
- Bubble Sort
- Heap Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Selection Sort
- Shell Sort
BUBBLE SORT
Il Bubble Sort opera comparando ogni elemento di una lista con l’elemento successivo, scambiandoli di posto se necessario. L’algoritmo ripete questo processo finchè non scorre l’intera lista senza effettuare scambi tra gli elementi. Il nome bubble (bolla) deriva dal modo in cui gli elementi vengono ordinati: quelli più piccoli risalgono verso le proprie posizioni corrette all’interno della lista, proprio come bollicine di una bibita gassata. A causa di questo modo di operare questo algoritmo è considerato il più inefficiente tra quelli elencati.
Di seguito il codice di una implementazione di tale algoritmo:
//Array di interi
private int[] a = new int[100];
//Numero di elementi dell'array
private int x;
public void BubbleSort()
{
int i;
int j;
int temp;
for (i = (x - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (a[j - 1] > a[j])
{
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}HEAP SORT
L’Heap Sort è un’ottima scelta per insiemi di dati ampi, costituiti anche da milioni di elementi. Il termine heap in inglese vuol dire ‘mucchio’ e l’algoritmo infatti opera utilizzando proprio una struttura denominata heap, ovvero un albero binario in cui tutti i nodi seguono una determinata proprietà.
Il primo passo è quello di creare un primo heap dell’insieme di dati e poi rimuovere gli elementi più grandi per piazzarli alla fine dell’array ordinato. Dopo aver rimosso gli elementi più grandi l’algoritmo ricostruisce l’heap e di nuovo rimuove gli elementi più grandi, ponendoli nella corretta posizione dell’array ordinato. Questa operazione viene ripetuta finchè non sono più presenti elementi nell’heap e l’array ordinato è completo.
L’implementazione di base dell’algoritmo prevede due array, uno per gestire l’heap e uno per gestire gli elementi ordinati:
//Array di interi
private int[] a = new int[100];
//Numero di elementi dell'array
private int x;
public void HeapSort()
{
int i;
int temp;
for (i = (x / 2) - 1; i >= 0; i--)
{
ScorriNodi(i, x);
}
for (i = x - 1; i >= 1; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
ScorriNodi(0, i - 1);
}
}
public void ScorriNodi(int radice, int valoreMinore)
{
bool completato = false;
int figlioMaggiore;
int temp;
while ((radice * 2 <= valoreMinore) && (!completato))
{
if (radice * 2 == valoreMinore)
figlioMaggiore = radice * 2;
else if (a[radice * 2] > a[radice * 2 + 1])
figlioMaggiore = radice * 2;
else
figlioMaggiore = radice * 2 + 1;
if (a[radice] < a[figlioMaggiore])
{
temp = a[radice];
a[radice] = a[figlioMaggiore];
a[figlioMaggiore] = temp;
radice = figlioMaggiore;
}
else {completato = true;}
}
}INSERTION SORT
L’Insertion Sort funziona proprio come il suo nome suggerisce: esso inserisce ogni elemento nella corretta posizione della lista finale. La più semplice implementazione di questo algoritmo richiede due liste: la lista sorgente e la lista in cui devono essere inseriti gli elementi ordinati. Questo algoritmo è indicato per liste di poche migliaia di elementi ed è significativamente più semplice dello Shell Sort, anche se è un pò meno efficiente. Allo stesso tempo è due volte più efficiente del Bubble Sort ed almeno il 40% più veloce del Selection Sort, con la limitazione delle dimensioni della lista suddette.
Di seguito il codice di una implementazione di tale algoritmo:
//Array di interi
private int[] a = new int[100];
//Numero di elementi dell'array
private int x;
public void InsertionSort()
{
int i;
int j;
int indice;
for (i = 1; i < x; i++)
{
indice = a[i];
j = i;
while ((j > 0) && (a[j - 1] > indice))
{
a[j] = a[j - 1];
j = j - 1;
}
a[j] = indice;
}
}MERGE SORT
Il Merge Sort suddivide la lista da ordinare in due metà uguali e pone questi dati in due array separati. Ogni array viene poi ordinato ricorsivamente ed infine i due vengono uniti (da qui deriva il termine merge, unione) per creare la lista finale ordinata. Alcune implementazioni di questo algoritmo prevedono l’utilizzo di tre array, uno per ogni metà dei dati e uno per la lista finale ordinata, ma noi vedremo un algoritmo che utilizza solo due array.
Il Merge Sort in pratica opera suddividendo il problema in sottoproblemi sempre più piccoli: si parte suddividendo i dati in due metà e procedendo all’ordinamento delle due ricorsivamente; quando si sono suddivise tutte le metà si procede alla loro fusione ottenendo un insieme ordinato.
Questo algoritmo è leggermente più veloce dell’ Heap Sort per insiemi di grandi dimensioni, ma richiede il doppio di memoria a causa della presenza del secondo array.
Di seguito il codice di una implementazione di tale algoritmo:
//Array di interi contenenti i valori da ordinare
private int[] a = new int[100];
private int[] b = new int[100];
//Numero di elementi
private int x;
public void MergeSort(int sinistra, int destra)
{
sinistra = 0;
destra = x - 1;
int mezzo;
if (destra > sinistra)
{
mezzo = (destra + sinistra) / 2;
MergeSort(sinistra, mezzo);
MergeSort(mezzo + 1, destra);
Merge(sinistra, mezzo + 1, destra);
}
}
public void Merge(int sinistra, int mezzo, int destra)
{
int i, sinistra_fine, num_elementi, tmp_pos;
sinistra_fine = mezzo - 1;
tmp_pos = sinistra;
num_elementi = destra - sinistra + 1;
while ((sinistra <= sinistra_fine) && (mezzo <= destra))
{
if (a[sinistra] <= a[mezzo])
{
b[tmp_pos] = a[sinistra];
tmp_pos = tmp_pos + 1;
sinistra = sinistra + 1;
}
else
{
b[tmp_pos] = a[mezzo];
tmp_pos = tmp_pos + 1;
mezzo = mezzo + 1;
}
}
while (sinistra <= sinistra_fine)
{
b[tmp_pos] = a[sinistra];
sinistra = sinistra + 1;
tmp_pos = tmp_pos + 1;
}
while (mezzo <= destra)
{
b[tmp_pos] = a[mezzo];
mezzo = mezzo + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i < num_elementi; i++)
{
a[destra] = b[destra];
destra = destra - 1;
}
}QUICK SORT
Il Quick Sort è anch’esso un algoritmo che usa massicciamente la ricorsione, semplice in teoria ma difficile da tradurre in codice. L’algoritmo ricorsivo è costituito da quattro fasi:
- Se c’è nell’array da ordinare un numero di elementi minore o uguale a uno termina
- Prendi un elemento dell’array per utilizzarlo come pivot (in inglese perno, fulcro). Solitamente si prende l’elemento all’estrema sinistra dell’array
- Suddividi l’array in due parti, una con gli elementi più grandi del pivot e l’altra con gli elementi più piccoli del pivot
- Ripeti ricorsivamente l’algoritmo per entrambe le parti dell’array originale
Questo algoritmo è di gran lunga il più veloce tra gli algoritmi di ordinamento, anche se il fatto che esso sia ricorsivo potrebbe farne una scelta non molto corretta su macchine dotate di una quantità di memoria limitata (come per gli altri algoritmi ricorsivi del resto).
Di seguito il codice di una implementazione di tale algoritmo:
//Array di interi contenente i valori da ordinare
private int[] a = new int[100];
//Numero di elementi
private int x;
public void QuickSort(int sinistra, int destra)
{
sinistra = 0;
destra = x - 1;
int pivot, sx_mem, dx_mem;
sx_mem = sinistra;
dx_mem = destra;
pivot = a[sinistra];
while (sinistra < destra)
{
while ((a[destra] >= pivot) && (sinistra < destra))
{
destra--;
}
if (sinistra != destra)
{
a[sinistra] = a[destra];
sinistra++;
}
while ((a[sinistra] <= pivot) && (sinistra < destra))
{
sinistra++;
}
if (sinistra != destra)
{
a[destra] = a[sinistra];
destra--;
}
}
a[sinistra] = pivot;
pivot = sinistra;
sinistra = sx_mem;
destra = dx_mem;
if (sinistra < pivot)
{
QuickSort(sinistra, pivot - 1);
}
if (destra > pivot)
{
QuickSort(pivot + 1, destra);
}
}SELECTION SORT
Il Selection Sort opera selezionando il più piccolo elemento non ordinato in una lista e spostandolo nella sequenza ordinata, scambiandolo con il prossimo elemento da ordinare. La sequenza viene suddivisa in due parti: la sottosequenza ordinata (che occupa le prime posizioni dell’array) e la sottosequenza da ordinare.
Questo algoritmo offre prestazioni migliori rispetto al Bubble Sort ma risulta più difficile da implementare dell’Insertion Sort (che è comunque due volte più veloce del Bubble Sort). Quindi non è consigliabile l’uso del Selection Sort e se proprio si desidera utilizzarlo è consigliabile farlo su liste limitate a un migliaio di elementi.
Di seguito il codice di una implementazione di tale algoritmo:
//Array di interi contenente i valori da ordinare
private int[] a = new int[100];
//Numero di elementi
private int x;
public void SelectionSort()
{
int i, j;
int min, temp;
for (i = 0; i < x - 1; i++)
{
min = i;
for (j = i + 1; j < x; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}SHELL SORT
Lo Shell Sort è uno degli algoritmi di ordinamento più antichi. Esso effettua operazioni multiple sulla lista di elementi da ordinare e ogni volta ordina un numero di insiemi di elementi di uguale dimensione utilizzando l’Insertion Sort. La dimensione degli insiemi utilizzati ad ogni iterazione ha chiaramente un forte impatto sull’efficienza della procedura.
Questo algoritmo è cinque volte più veloce del Bubble Sort e circa due volte più veloce dell’ Insertion Sort. E’ invece più lento del Merge Sort, dell’Heap Sort e del Quick Sort, ma la sua semplicità lo rende un’ottima scelta per l’ordinamento di liste con meno di 5000 elementi. Inoltre esso è indicato per l’ordinamento ripetitivo di piccole liste.
Di seguito il codice di una implementazione di tale algoritmo:
//Array di interi contenente i valori da ordinare
private int[] a = new int[100];
//Numero di elementi
private int x;
public void ShellSort()
{
int i, j, incremento, temp;
incremento = 3;
while (incremento > 0)
{
for (i = 0; i < x; i++)
{
j = i;
temp = a[i];
while ((j >= incremento) && (a[j - incremento] > temp))
{
a[j] = a[j - incremento];
j = j - incremento;
}
a[j] = temp;
}
if (incremento / 2 != 0)
{
incremento = incremento / 2;
}
else if (incremento == 1)
{
incremento = 0;
}
else
{
incremento = 1;
}
}
}Conclusioni
Possiamo dunque concludere che la scelta dell’algoritmo di ordinamento da utilizzare dipende sia dalle dimensioni dell’insieme di elementi da ordinare, sia dalle caratteristiche delle macchine sulle quali vengono eseguiti tali algoritmi. La scelta di quello più idoneo alle nostre esigenze deve quindi scaturire da un’attenta analisi di questi due parametri.
