Algoritmi di ordinamento in C
Pagina 1 di 5
Un algortimo di ordinamento è una sequenza di operazioni che assegna un ordine di precedenza agli elementi di un insieme secondo una relazione d'ordine. In queste righe saranno esposti i più comuni (con un'approccio fortemente orientato agli esempi) e di ciascuno verranno commentati i pregi ed i difetti.
Per semplicità negli esempi sarà sempre impiegato come insieme quello dei numeri naturali e come relazione d'ordine quella di maggioranza; gli algoritmi esposti sono comunque universalmente validi, al netto di un breve lavoro di adattamento del codice.
Selection sort
Per ordinare un insieme numerico una prima e semplice intuizione può essere scandire il vettore tante volte quanti sono i suoi elementi, ad ogni passo ricercare il valore minimo ed aggiungerlo alla sequenza ordinata, che inizialmente identifichiamo con un secondo vettore;
Esempio: {5,1,3,8,2}
passo #1 -> {1,X,X,X,X}
passo #2 -> {1,2,X,X,X}
passo #3 -> {1,2,3,X,X}
passo #4 -> {1,2,3,5,X}
passo #5 -> {1,2,3,5,8}
(con X è contrassegnata una posizione del nuovo vettore non ancora scritta)
Dal punto di vista dello spazio occupato in memoria, applicare in tale modo questo algoritmo è fortemente svantaggioso in quanto l'insieme iniziale viene copiato in un altro. Un semplice artificio correttivo consiste nel sostituire l'operazione di copia con lo scambio del valore minimo appena trovato con il primo elemento che non fa parte del sottoinsieme dei numeri gia ordinati.
Esempio: {5,1,3,8,2}
passo #1 -> {1,5,3,8,2}
passo #2 -> {1,2,3,8,5}
passo #2 -> {1,2,3,8,5}
passo #3 -> {1,2,3,5,8}
L'algortimo così modificato è il Selection Sort, del quale segue una possibile implementazione:
sel_sort(int *v,int dim)
{
int i=0, temp=0, y=0, j=0;
for(i=0;i=i;j--)
{
if(temp>v[j])
{
temp=v[j];
y=j;
}
scambia(v,i,y); //Scambia le posizioni i e y nel vettore v
}
}
Il doppio ciclo for annidiato fa intuire che il numero dei confronti effettuati da questo algoritmo è di ordine quadratico rispetto al numero di elementi.Cio significa che sono effettuati un numero di confronti di ordine di grandezza pari al quadrato del numero degli elementi dell'insieme.
Si noti che in casi normali è proprio il numero di confronti a pesare sull'efficienza; le restanti operazioni, per lo più assegnazioni, hanno un costo trascurabile rispetto al confronto.
Quando si hanno record da ordinare di dimensioni ragguardevoli, il numero di scambi influisce in modo determinante sulle prestazioni. In questo secondo caso il Selection Sort si rivela una soluzione eccellente ed ottimale perché ogni elemento viene spostato al più una sola volta.
Il Selection Sort è inoltre un algoritmo stabile.
Un algoritmo stabile preserva l'effetto degli ordinamenti precedenti nel caso vengano trattate strutture dati a chiavi multiple, ad esempio Cognome e Nome:
1. Verdi Carlo 2. Rossi Andrea 3. Rossi Mario 4. Bianchi LucianoOrdiniamo prima i campi per nome:
1. Rossi Andrea 2. Verdi Carlo 3. Rossi Mario 4. Bianchi LucianoOra ordiniamo per cognome, un algoritmo stabile preserverà sempre le precedenze dell'insieme iniziale, ovvero, in caso di parità tra le chiavi su cui si sta ordinando, sarà la posizione dell'elemento prima dell'ordinamento a stabilire la collocazione finale.
1. Bianchi Luciano 2. Rossi Andrea 3. Rossi Mario 4. Verdi CarloUn algoritmo stabile farà in modo che in questo caso Andrea Rossi preceda sempre Mario Rossi. Uno non stabile ha un comportamento non prevedibile, tale per cui potrebbero risultare invertite le posizioni 2 e 3.
Il selection sort è anche in loco.
Un algoritmo si dice in loco (o anche in place) se non occupa uno spazio di memoria extra rispetto alla base dati iniziale, oppure ne occupa una piccola quantità costante.
