Ho intenzione di scrivere alcuni articoli che non riguardano un particolare linguaggio di programmazione, bensì i metodi dello sviluppo del software, lo studio degli algoritmi ed in particolare proporrò degli esempi in linguaggio C. Utilizzerò il compilatore GCC di Linux. In effetti non abbiamo bisogno di implementare questi algoritmi, difatti in tutti i linguaggi di programmazione moderni ce ne sono già di implementati ed anche molto ottimizzati, che è pressoché impossibile costruirli meglio; lo scopo di questa guida sarà però quello di capire come funzionano in modo poi da poterli utilizzare al meglio. Iniziamo questa serie di articoli parlando dell’algoritmo di ordinamento di una serie di dati, come per esempio i vettori o array.
Gli algoritmi di ordinamento sono una classe di algoritmi che data una sequenza di valori, dopo un certo numero di passi forniscono come risultato la stessa sequenza, ma ordinata in senso ascendente o discendente. Per arrivare allo stesso scopo possiamo percorrere strade diverse, quindi esisteranno vari algoritmi anche per risolvere il problema dell’ordinamento della nostra sequenza utilizzeranno procedimenti diversi.
Mettiamo di avere una serie di biglietti e sopra ognuno di essi un numero intero, se vogliamo eseguire l’ordinamento a mano dobbiamo procedere in questo modo:
- leggere uno ad uno il valore del foglietto alla ricerca del valore più piccolo in essi contenuto
- una volta individuato il valore più piccolo degli altri, lo scriviamo nella prima riga libera del secondo foglio
- cancelliamo dalla lista originaria il valore trovato
- ripartiamo dall’inizio ripetendo l’operazione fino alla fine dei valori sul tavolo di origine
Sicuramente questo metodo non è dei più efficienti, ma rappresenta comunque un modo per fare a mano il nostro lavoro. Dal punto di vista computazionale, si tratterebbe di scorrere la lista dell’array per tante volte quanti sono i valori e questo richiederebbe anche l’uso di una seconda variabile d’appoggio ed un altro array atto a contenere i valori trovati.
Esistono degli algoritmi di ordinamento di array molto semplici e che con un pò di modifiche si possono far diventare anche abbastanza performanti. Implementeremo un algoritmo che consente di ordinare i valori in senso ascendente ( crescente ) scambiando i valori all’interno dell’array stesso e quindi senza bisogno di quello d’appoggio. I passi da compiere sono:
- l’array viene scandito a partire dalla prima fino alla penultima posizione e viene eseguito un confronto di volta in volta fra due elementi adiacenti
- se l’elemento letto ha valore maggiore del successivo allora si esegue lo scambio fra i contenuti delle rispettive locazioni della struttura
- i passi vengono eseguiti fino a quando non si avrà bisogno di eseguire nessuno scambio
Per creare un algoritmo che ordini in senso discendente ( decrescente ) i valori occorre cambiare soltanto il confronto tra i numeri.
#include <stdio.h>
void swap(int* iArr, int iOld, int iNew)
{
int iTemp;
if (iArr == NULL)
return;
iTemp = iArr[iOld];
iArr[iOld] = iArr[iNew];
iArr[iNew ] = iTemp;
}
void main()
{
int iArrVal[] = {12, 65, 2, 5, 54, 98, 23, 123, 14, 76};
int i;
printf("Il vettore non ordinato:\n");
for (i = 0; i < sizeof(iArrVal) / sizeof(int); i++)
printf("%d\n", iArrVal[i]);
for (i = 0; i < (sizeof(iArrVal) / sizeof(int)) - 1; i++)
{
if (iArrVal[i] > iArrVal[i + 1])
{
swap(iArrVal, i + 1, i);
i = -1;
}
}
printf("Il vettore ordinato crescente:\n");
for (i = 0; i < sizeof(iArrVal) / sizeof(int); i++)
printf("%d\n", iArrVal[i]);
}
Secondo questo procedimento, ad ogni scansione dell’array, l’algoritmo tende a portare i valori più grandi verso l’alto ed i più piccoli verso indici inferiori. In particolare ho creato una funzione swap che consente di scambiare i valori di determinati indici.
Questo algoritmo riesce ad ordinare bene i valori di un vettore, ma dobbiamo chiederci di quanto aumenti il tempo computazionale rispetto alla quantità di valori nell’array o meglio quale sia l’efficienza dell’algoritmo. Per renderci conto di questo possiamo inserire un contatore all’interno del ciclo e vedere quante volte siamo costretti a ciclare per arrivare all’ordinamento del vettore. Il valore sul nostro array è di ben 83 cicli per arrivare all’ordinamento della serie di numeri, che sono 10, quindi per un array di 1000 elementi dobbiamo aspettarci indicativamente 8300 cicli, un bel numero di volte, per non parlare di vettori di migliaia di valori.
L’algoritmo che prendiamo in esame ora è il bubble sort ( ordinamento a bolle ) nel quale l’elemento più piccolo viene sistemato al posto giusto già nel primo ciclo sull’array e poi pian piano tutti gli altri riducendo sempre di più il campo di ricerca.
#include <stdio.h>
void swap(int* iArr, int iOld, int iNew)
{
int iTemp;
if (iArr == NULL)
return;
iTemp = iArr[iOld];
iArr[iOld] = iArr[iNew];
iArr[iNew ] = iTemp;
}
void main()
{
int iArrVal[] = {12, 65, 2, 5, 54, 98, 23, 123, 14, 76};
int i, k, iTot;
int bSwap;
printf("Il vettore non ordinato:\n");
for (i = 0; i < sizeof(iArrVal) / sizeof(int); i++)
printf("%d\n", iArrVal[i]);
iTot = 0;
k = 1;
bSwap = 0;
while (iTot >= 0)
{
for (i = 0; i < (sizeof(iArrVal) / sizeof(int)) - k; i++)
{
if (iArrVal[i] > iArrVal[i + 1])
{
swap(iArrVal, i + 1, i);
bSwap = 1;
}
}
iTot++;
}
if (bSwap > 0)
{
bSwap = 0;
k++;
if (k >= (sizeof(iArrVal) / sizeof(int)) - 1)
break;
}
else
break;
printf("Il vettore ordinato crescente:\n");
for (i = 0; i < sizeof(iArrVal) / sizeof(int); i++)
printf("%d\n", iArrVal[i]);
printf("\n\nSiamo stati costretti a %d cicli\n", iTot);
}
Con il metodo del bubble sort siamo stati costretti a 39 cicli, la metà di prima, che è sicuramente un ottimo risultato ed abbiamo quindi anche indicativamente dimezzato il tempo computazionale dell’algoritmo.
Nel corso degli anni si sono studiati algoritmi per l’ordinamento molto sofisticati, che troviamo in tutti i compilatori moderni: il quick sort ed il merge sort. L’idea alla base di questi due procedimenti è di dividere i dati. Nel primo caso si mettono a destra i numeri superiori ed a sinistra quelli minori, mentre nel secondo si suddividono i numeri in parti che si ordinano e poi si uniscono ( merge ) per dare il risultato finale. Data la difficoltà dei due algoritmi vi evito il sorgente, anche perché non utile in quanto come già detto tutti i linguaggi di programmazione moderni contengono questi algoritmi di ordinamento.
