Esistono diverse categorie di algoritmi di ordinamento. Essi possono essere distinti in due classi:

·   &nb 424d39e sp;    Algoritmi di Ordinamento Interno. Fanno uso di strutture dati allocate in memoria centrale dell'elaboratore. Per tale motivo hanno il principale limite di non permettere l'ordinamento di grosse sequenze di informazioni.

·   &nb 424d39e sp;    Algoritmi di Ordinamento Esterno. Tipicamente fanno uso di strutture file per la memorizzazione e le operazioni di ordinamento della sequenza di informazioni da ordinare.

1.Algoritmi di Ordinamento Interni

Come detto tali algoritmi sono caratterizzati dall'uso di strutture dati allocate in memoria RAM per la memorizzazione e l'ordinamento di sequenze di informazioni. Ad esempio essi fanno uso di vettori.

Esistono due categorie di algoritmi di ordinamento interni. La classificazione è fatta in base alla complessità di calcolo. La complessità di calcolo si riferisce soprattutto al numero di operazioni necessarie all'ordinamento, ossia la tempo di esecuzione dell'algoritmo.

1.   &nb 424d39e sp;  Algoritmi Semplici di Ordinamento. Algoritmi che presentano una complessità proporzionale a n², dove n è il numero di informazioni da ordinare. Essi sono caratterizzati da poche e semplici istruzioni, dunque presentano un codice molto ristretto.

2.   &nb 424d39e sp;  Algoritmi Evoluti di Ordinamento. Algoritmi che offrono una complessità computazionale proporzionale a n logn (che è sempre inferiore a n²) . Tali algoritmi sono molto più complessi, fanno molto spesso uso di ricorsione. La convenienza del loro utilizzo si ha unicamente quando il numero n di informazioni da ordinare è molto elevato.

Nel seguito verrà presentato un esempio di algoritmo di tipo evoluto: il Quick Sort. Si supporrà, per semplicità di adottare la seguente struttura dati.

tipobase vettore[n];

dove tipobase potrebbe essere: int, float, char.

La sequenza di elementi da ordinare viene memorizzata in un vettore di dimensione n. Si è supposto che tipobase sia il tipo degli elementi da ordinare.

Nella realtà le informazioni da ordinare sono molto più complesse, ad esempio costituite da struct. In tal caso l'ordinamento verrà effettuato considerando uno o più attributi (campi) di ciascun elemento (chiavi). La scelta di tali attributi deve essere realizzata sulla base di differenti criteri. Uno tra essi è rappresentato dalle operazioni di ricerca che dovranno essere fatte sull'insieme delle informazioni. Generalmente le chiavi di ordinamento vengono scelte uguali alle chiavi di ricerca. Un altro fattore da considerare nella scelta delle chiavi di ordinamento è la garanzia che le possibili omonimie vengano ridotte al minimo. Le chiavi di ordinamento dovranno essere scelte in modo ed in numero da evitare che vi possano essere più elementi con stesse chiavi di ordinamento (o di ricerca), e che dunque non potrebbero essere distinti.

1.2.Algoritmi di Ordinamento Evoluti: Algoritmo di Ordinamento QuickSort

L'algoritmo di ordinamento QuickSort si basa su un concetto molto semplice. Si consideri un vettore di n elementi e si supponga di ordinarlo secondo algoritmi non evoluti, ossia quelli che presentano un tempo di calcolo proporzionale a n², come detto prima. Si supponga, adesso di dividere il vettore da ordinare in due pezzi di n/2 elementi ciascuno e di ordinare le due metà separatamente. Applicando sempre gli algoritmi non evoluti, si avrebbe un tempo di calcolo pari a (n/2)² + (n/2)²=n²/2. Si supponga adesso di riunire i due vettori ordinati e di poter riottenere il vettore originario ordinato. E' chiaro che se questo ragionamento si potesse applicare anche immaginando una decomposizione del vettore originario in quattro, si avrebbe un tempo di calcolo totale pari a: (n/4)² + (n/4)² + (n/4)² + (n/4)²=n²/4. Se si potesse dividere in 8, si avrebbe un tempo ancora più basso, e così via dicendo.

L'unico problema è che in linea di massima il ragionamento descritto prima non funziona sempre. Si consideri ad esempio il vettore:

Si supponga di divederlo a metà e di ordinare separatamente i due pezzi, ottenendo i due vettori:

Se i due vettori ordinati vengono riuniti assieme, otteniamo il vettore:

che ovviamente non è ordinato.

Un modo per superare il problema è quello di operare nel modo seguente:

1.   &nb 424d39e sp;  prima di dividere il vettore, gli elementi del vettore vengono spostati in modo che la prima metà (quella a sinistra) contiene elementi tutti più piccoli della seconda metà (quella a destra).

2.   &nb 424d39e sp;  il vettore viene decomposto nelle due metà

3.   &nb 424d39e sp;  le due metà vengono ordinate separatamente

4.   &nb 424d39e sp;  il vettore originario è ordinato mettendo insieme le due metà ordinate separatamente

Il QuickSort segue questa "strategia". In particolareL'algoritmo QuickSort si compone dei seguenti passi:

1.   &nb 424d39e sp;  il vettore da ordinare viene delimitato dall'indice del primo elemento (inf) e dall'indice dell'ultimo elemento (sup).

2.   &nb 424d39e sp;  viene scelto un elemento del vettore di indice compreso tra inf e sup, chiamato pivot. Il pivot viene scelto del tutto casualmente. Una scelta potrebbe essere l'elemento che ha come indice (inf+sup)/2.

3.   &nb 424d39e sp;  vengono utilizzati due indici i,j, che vengono inizializzati a i=inf e j=sup.

4.   &nb 424d39e sp;  l'indice i viene incrementato di 1 fino a quando l'elemento di indice i non è maggiore o uguale al pivot.

5.   &nb 424d39e sp;  l'indice j viene decrementato di 1 fino a quando l'elemento di indice j non è minore o uguale al pivot.

6.   &nb 424d39e sp;  nel caso in cui i<j, gli elementi di indici i e j vengono scambiati, e poi i viene incrementato e j decremenato (in modo unitario)

7.   &nb 424d39e sp;  nel caso in cui i=j, non si effettua lo scambio, ma i viene incremenato di 1 e j viene decrementato di 1.

8.   &nb 424d39e sp;  se i>j allora l'algortimo termina. In questo modo risulta che:

tutti gli elementi di indice appartenente a inf,..,j sono minori o uguali del pivot

tutti gli elementi di indice appartenente a i,..,sup sono maggiori o uguali del pivot 

tutti gli elementi di indice appartenente a j+1,..,i-1 sono uguali del pivot

9.   &nb 424d39e sp;  L'algortimo QuickSort viene applicato ricorsivamente al sottovettore individuato dagli indici (inf,j), se tale sottovettore contiene almeno un elemento, ossia se inf<j

l'algortimo QuickSort viene applicato ricorsivamente al sottovettore individuato dagli indici (i, sup), se tale sottovettore contiene almeno un elemento, ossia se i<sup

1.2.1. Esempi del QuickSort

Nel seguito verranno mostrati tre esempi del QuickSort, che si riferiscono a situazioni reali. Nel primo esempio verrà considerato il caso in cui il vettore originario viene decomposto nella prima passata in due sottovettori di dimensione uguale (pari alla metà della dimensione del vettore originario). Nel secondo esempio, il vettore originario viene decomposto in due sottovettori, di cui il primo ha dimensione uguale alla dimensione originaria meno 1, e l'altro ha una dimensione unitaria. I due primi esempi rappresentano il caso migliore e il caso peggiore del comportamento del QuickSort. I due casi sono legati alla scelta del pivot. Come si vedrà negli esempi, nel primo esempio il pivot viene scelto pari al mediano[1] degli elementi contenuti nel vettore, e ciò rappresenta il caso migliore. Nel secondo esempio, invece, il pivot coincide con l'elemento massimo del vettore. Ciò rappresenta il caso peggiore del comportamento del QuickSort.

Il terzo esempio si riferisce ad un comportamento generico (ossia compreso tra il peggiore e il migliore) del QuickSort.

Esempio 1: il Pivot coincide con l'elemento mediano del vettore.

Si consideri il seguente vettore di n=10 elementi:

In tal caso, risulta pivot=vett[m]=15, ossia casualmente il pivot coincide con l'elemento mediano del vettore. Infatti il numero di elementi più piccoli di 15 è 4, mentre il numero di elementi più grandi di lui è 4. L'indice i viene incrementato fino a quando non viene trovato un elemento più grande o uguale al pivot. Nel nostro esempio l'indice i si arresta in corrispondenza dell'elemento 45. Per quanto riguarda l'indice j esso viene spostato fino a quando non si perviene all'elemento 15, uguale al pivot.

Gli elementi di indice i e j vengono scambiati, e l'indice i viene incrementato, mentre j viene decrementato, ottenendo:

L'indice i viene arrestato in quanto esso corrisponde al pivot. L'indice j viene fatto decrementare fino a quando esso perviene all'elemento 12, che è inferiore al pivot. Gli indici sono dunque come mostrato dalla seguente figura:

Gli elementi i e j vengono scambiati e successivamente i viene incrementato e j viene decrementato, ottenendo:

La prima passata dell'algoritmo QuickSort si conclude, perché i due indici i e j si sono invertiti. Come si vede alla fine della prima passata di ordinamento risulta:

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a inf,..,j sono minori o uguali del pivot

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a i,..,sup sono maggiori o uguali del pivot

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a j+1,..,i-1 sono uguali del pivot (nel nostro esempio non ci sono elementi tra j+1 e i-1).

Come si vede l'esempio considerato rappresenta il caso migliore perché il vettore originario è stato decomposto in due vettori che hanno entrambi dimensione uguale e pari a metà della dimensione iniziale.

L'algoritmo procede ricorsivamente operando sui vettori delimitati dagli indici (inf,..,j) e (i,..,sup).

Esempio 2: il Pivot coincide con l'elemento più grande del vettore.

Si consideri il seguente vettore di n=10 elementi:

In tal caso, risulta pivot=vett[m]=34, ossia casualmente il pivot coincide con l'elemento massimo del vettore. L'indice i viene incrementato fino a quando non viene trovato un elemento più grande o uguale al pivot. Nel nostro esempio l'indice i si arresta in corrispondenza del pivot. L'esempio mette in evidenza il motivo di incrementare l'indice i fino a quando si trova un elemento più grande o uguale al pivot. Se non ci fosse la condizione uguale, nel nostro esempio l'indice i verrebbe continuamente incrementato oltre la dimensione del vettore. Per quanto riguarda l'indice j esso non viene spostato in quanto l'elemento j-esimo è inferiore al pivot.

Gli elementi di indice i e j vengono scambiati, e l'indice i viene incrementato, mentre j viene decrementato, ottenendo:

L'indice i viene fatto incrementare fino a quando arriva all'elemento 34, che è pari al pivot. Infatti secondo la regola di incremento dell'indice i, esso viene fatto arrestare perché è stato trovato un elemento uguale al pivot. L'indice j non viene fatto decrementare perché si riferisce ad un elemento già inferiore al pivot. Gli indici sono dunque come mostrato dalla seguente figura:

Come si vede alla fine della prima passata di ordinamento risulta:

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a inf,..,j sono minori o uguali del pivot

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a i,..,sup sono maggiori o uguali del pivot

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a j+1,..,i-1 sono uguali del pivot (nel nostro esempio non ci sono elementi tra j+1 e i-1).

L'algoritmo procede ricorsivamente operando sui vettori delimitati dagli indici (inf,..,j) e (i,..,sup). Come si vede l'esempio considerato rappresenta un caso peggiore, perché il vettore originario è stato decomposto in due vettori di cui il primo (quello compreso tra inf e j) ha dimensione quasi uguale a quella originaria. E' chiaro che la complessità di riordino del primo sottovettore è praticamente la stessa di quella relativa al riordino del vettore originario. Dunque non si è avuto alcun vantaggio nel suddividere il vettore.

Esempio 3: il Pivot non coincide né con il massimo/minimo né con il mediano del vettore.

Si consideri il seguente vettore di n=10 elementi:

In tal caso, risulta pivot=vett[m]=15. Esso non è né il massimo (o il minimo ) del vettore, né il mediano, visto che il numero di elementi più piccoli di 15 è 3, mentre il numero di elementi più grandi di lui è 5. L'indice i viene incrementato fino a quando non viene trovato un elemento più grande o uguale al pivot. Nel nostro esempio l'indice i si arresta in corrispondenza dell'elemento 45. Per quanto riguarda l'indice j esso viene spostato fino a quando non si perviene all'elemento 15, uguale al pivot.

Gli elementi di indice i e j vengono scambiati, e l'indice i viene incrementato, mentre j viene decrementato, ottenendo:

L'indice i viene arrestato in quanto esso corrisponde al pivot. L'indice j viene fatto decrementare fino a quando esso perviene all'elemento 15, che è uguale al pivot. Gli indici sono dunque come mostrato dalla seguente figura:

Gli elementi i e j non vengono scambiati, perché non avrebbe senso visto che i e j coincidono, e successivamente i viene incrementato e j viene decrementato, ottenendo:

La prima passata dell'algoritmo QuickSort si conclude, perché i due indici i e j si sono invertiti. Come si vede alla fine della prima passata di ordinamento risulta:

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a inf,..,j sono minori o uguali del pivot

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a i,..,sup sono maggiori o uguali del pivot

·   &nb 424d39e sp;    tutti gli elementi di indice appartenente a j+1,..,i-1 sono uguali del pivot (nel nostro esempio c'è un solo elemento tra j+1 e i-1).

L'algoritmo procede ricorsivamente operando sui vettori delimitati dagli indici (inf,..,j) e (i,..,sup).

1.2.2.Codifica in C dell'Algoritmo QuickSort

La sequente procedura realizza l'algortimo QuickSort.

void scambia (tipobase v[], int i, int j)

void QSort (tipobase v[], int inf, int sup)

} while (i<=j);

if (inf<j) QSort(v,inf,j);

if (i<sup) QSort(v,i,sup);

Come si vede essa si compone di un ciclo do-while che termina quando i>j. Dentro questo ciclo due cicli while incrementano i e decrementano j. Si noti che i due cicli terminano sicuramente quando v[i] coincide con il pivot e v[j] coincide con il pivot. Nel caso in cui i<j viene effettuato lo scambio, che non viene realizzato se i=j. Se i j, la variabile i viene incrementata e j decrementata.

1.2.3.Applicazione in C dell'Algoritmo QuickSort

Il seguente programma mostra un'applicazione dell'algortimo QuickSort in Linguaggio C. L'applicazione si riferisce all'ordinamento di un vettore di struct. Ciascun elemento del vettore contiene diversi campi: cognome, nome e telefono. L'ordinamento è realizzato utilizzando come chiavi di ordinamento i campi cognome e nome. Come visibile, il vettore è dinamico ed è previdta una procedura per la sua allocazione.

#include<stdio.h>

#include<alloc.h>

#include<string.h>

typedef struct persona;

persona *vettore;

int n;

persona * alloca(int dim)

void riempi(persona v[], int dim)

void visualizza(persona v[], int dim)

void scambia (persona v[], int i, int j)

void QSort (persona v[], int inf, int sup)

} while (i<=j);

if (inf<j) QSort(v,inf,j);

if (i<sup) QSort(v,i,sup);

main() while (n<1);

vettore=alloca(n);

riempi(vettore,n);

printf("Il vettore non ordinato e' \n");

visualizza(vettore,n);

QSort(vettore,0,n-1);

printf("\nIl vettore ordinato e' \n");

visualizza(vettore,n);

getchar();

---