Algoritmi di ordinamento in C

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 Luciano

Ordiniamo prima i campi per nome:

1. Rossi Andrea
2. Verdi Carlo
3. Rossi Mario
4. Bianchi Luciano

Ora 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 Carlo

Un 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.

Insertion sort

Immaginiamo di giocare a carte e supponiamo di voler ordinare le 5 carte che teniamo in mano. Prendiamo la seconda carta a partire da sinistra ed ordiniamola rispetto alla prima, poi prendiamo la terza carta e mettiamola nella giusta posizione rispetto alle prime due, e così via estraiamo in ordine le carte ed inseriamole, ad ogni passo, nella posizione corretta. Ad esempio consideriamo di vaere le seguenti carte {8,6,4,7,5}.

Passo 1:
{8,6,4,7,5} -> {8,P,4,7,5} -> {6,8,4,7,5}
(la carta contrassegnata dalla P è quella appena pescata)

Avendo in mano le carte non ci avremmo sicuramente fatto caso, ma guardando le cose con un occhio "più informatico" si può dedurre che l’operazione di inserimento della carta è simulabile con uno scalamento a destra (in questo caso solo dell’8) e con un assegnazione finale. Tutte operazioni, come visto prima, di costo trascurabile.

Andiamo avanti con l’applicazione dell’algoritmo, pescando questa volta la terza carta:

Passo 2:
{6,8,4,7,5} -> {6,8,P,7,5} -> {4,6,8,7,5}

Passo 3:
{4,6,8,7,5} -> {4,6,8,P,5} -> {4,6,7,8,5}

Passo 4:
{4,6,7,8,5} -> {4,6,7,8,P} -> {4,5,6,7,8}
(insieme ordinato)

Ecco una possibile implementazione:

void ins_sort(int *a, int n) 
{
   int i, j, temp; 
   for (j = 1; j < n; j++)
   {
      temp = a[j];
      i=j-1;       
      while( (i>=0) && (temp<a[i]) )
      {
         a[i+1] = a[i];
         i=i-1;
      }
      a[i + 1] = temp;
   }
}

Come nel caso del Selection Sort, il doppio ciclo rende l’algoritmo di ordine quadratico rispetto al numero di elementi; con analisi più approfondite si dimostra che l’insertion sort è efficientissimo nel caso di vettori di piccole dimensioni o parzialmente ordinati. E’stabile ed in loco.

Bubble sort

Il bubble sort è un algoritmo semplice e compatto. Confronta ogni coppia di elementi consecutiva a partire dall’elemento 1 e 2, effettuando lo scambio tra gli elementi se questi non sono in ordine. Si procede con l’elemento 2 e 3, con 3 e 4 fino all’esaurimento degli elementi. Al termine del primo passo l’elemento maggiore dell’insieme sarà collocato nella posizione corretta. Si ricomincia coi confronti ripartendo dalla coppia 1 e 2 e concludendo fino alla fine dell’insieme dei numeri non ordinati, il quale non comprende gli elementi in posizione finale che occupano gia la collocazione che gli compete. Quando l’insieme dei numeri ordinati ha la stessa cardinalità dell’insieme iniziale l’ordinamento è completo.

Applichiamo l’algoritmo all’insieme I = {10, 7, 2, 4}:

confronto 7 con 10: {7, 10, 2, 4}
confronto 10 con 2: {7, 2, 10, 4}
confronto 10 con 4: {7, 2, 4, 10}

primo passo completato: il 10 ha raggiunto la sua posizione corretta, lo contrassegno con le parentesi tonde;

confronto 7 con 2: {2, 7, 4, (10)}
confronto 7 con 4: {2, 4, 7, (10)}

secondo passo completato: il 7 ha raggiunto la sua posizione corretta;

confronto 2 con 4: {2, 4, (7), (10)}

terzo passo completato: il 4 ha raggiunto la sua posizione corretta, di conseguenza anche il 2;

L’algorimo ha un costo in termini di numero di confronti, pari alla sua cardinalità (numero di elementi) nel caso che l’insieme di partenza sia gia ordinato e pari al quadrato nel caso peggiore. Per migliorare l’efficienza è possibile inserire una variabile sentinella che interrompe l’algoritmo se nel passo in corso non vengono effettuati scambi, in quel caso il vettore risulta gia essere ordinato.

Il Bubble Sort è stabile ed in loco ma le sue prestazioni non sono ottimali. Ecco un implementazione in C dell’algoritmo base:

void bubblesort(int insieme[], int n_elementi_insieme)
{
  int i, j, temp;
  for (i = (n_elementi_insieme - 1); i > 0; i--)
  {
    for (j = 1; j <= i; j++)
    {
      if (insieme[j-1] > insieme[j])
      {
        // Effettua lo scambio
        temp = insieme[j-1];
        insieme[j-1] = insieme[j];
        insieme[j] = temp;
      }
    }
  }
}

Merge Sort

Il merge sort è un algoritmo di tipo divide et impera; esso, infatti, suddivide il problema principale in due sottoproblemi di analoga tipologia ma con minore complessità. Per facilitare e velocizzare la comprensione dell’algoritmo, affianchiamo passo passo la spiegazione ad un esempio, che consiste nell’applicare il merge sort all’insieme

{2,5,7,3,9,1,0,8}

Partendo dall’insieme dato, formiamo due sottoinsiemi con la stessa cardinalità.

{2,5,7,3} | {9,1,0,8}

Da ognuno dei sottoinsiemi ricaviamo a loro volta uilteriori sottoinsiemi, dimezzando ancora il numero di elementi per ciascun insieme. Procediamo in questo modo fino ad avere insiemi minimali di un solo elemento.

{2,5} | {7,3} || {9,1}|{0,8}
{2} | {5} || {7} | {3} ||| {9} | {1} || {0} | {8}

A questo punto si effettua l’operazione di fusione tra coppie di insiemi. La fusione è un operazione particolarmente efficiente che genera a partire da due insiemi gia ordinati un terzo insieme anch’esso ordinato, in un numero di passi pari alla somma delle cardinalità degli elementi degli insiemi interessati; ha quindi complessità lineare. L’operazione si implementa con un ciclo e tre contatori, tutti inizializzati a 0, ad ogni passo si confronta l’elemento j del primo vettore con l’elemento k del secondo e si copia il risultato nella posizione i del vettore risultato, infine si incrementa uno dei due contatori tra j e k, quello relativo al valore appena copiato. In ogni caso si incrementa i. Queste ultime righe si traducono in C nella seguente maniera:

fusione (insieme1[], insieme2[], destinazione[])
{
  int i, j=0, k=0;
  for (i=0; i < (len(insieme1) + len(insieme2); i++)
  {
    if (insieme1[j]<insieme2[k]) destinazione[i] = insieme1[j++];
    else destinazione[i] = insieme2[k++];
  }
}

Ripartendo dal nostro esempio applichiamo l’algoritmo di fusione agli insiemi elementari ricavati nell’ultimo passo:

{2} | {5} || {7} | {3} ||| {9} | {1} || {0} | {8}
{2,5} | {3,7} || {1,9} | {0,8}

Continuiamo con le fusioni fino a ricavare l’insieme iniziale ordinato.

{2,3,5,7} | {0,1,8,9}
{0,1,2,3,5,7,8,9}

Cio che garantisce a questo algoritmo prestazioni eccellenti è la tecnica della fusione: sfruttando il fatto che si sta operando su due sottoinsiemi gia ordinati il numero dei confronti che sono necessari per fonderli è pari alla somma degli elementi dei due sottoinsiemi. Il numero di fusioni è invece logaritmico; se il numero di elementi è n, al primo stadio vengono fuse n/2 coppie di insiemi, al secondo stadio n/4, poi n/8 e cosi via fino ad ottenere l’insieme ordinato. Sommariamente la complessità dell’algoritmo è n*log(n), perchè ogni fusione costa circa n confronti e viene effettuata circa log(n) volte. Il numero di operazioni compiute dal Merge Sort è identico in tutte le circostanze, dal caso migliore a quello medio a quello peggiore. Questo fatto può essere ritenuto un vantaggio rilevante in alcune applicazioni perchè permette di prevedere con ottima precisione il tempo di esecuzione dell’algoritmo. Stabile ed anche in loco, il MergeSort è spesso preferito a tutti gli altri algoritmi ottimali, in quanto riesce combinare ottime prestazioni, stabilità e bassa occupazione di memoria. Il Merge Sort si implementa classicamente e in modo compatto con la funzione ricorsiva esposta di seguito:

mergesort(int insieme[], int inizio, int fine)
{
  int elemento_centrale;
  if(inizio<fine)
  {
    elemento_centrale=(inizio+fine)/2;
    mergesort(a,inizio,elemento_centrale);
    mergesort(a,elemento_centrale+1,fine);
    merge(a,inizio,fine,elemento_centrale);
  }
  return(0);
}

Quick Sort

Il QuickSort è l’algoritmo conosciuto più efficiente nel caso medio e con grandi quantità di dati. Funziona con un meccanismo simile a quello del MergeSort: richiama se stesso ricorsivamente su due sottoinsiemi fino ad ottenere il risultato ordinato. La differenza è nella tecnica di partizionamento. Mentre nel MergeSort erano scelti come sottoinsiemi ordinatamente la prima metà e la seconda metà dell’insieme principale, nel QuickSort si applica un’algoritmo più elaborato.

Partizionamento nel QuickSort

Inizialmente si sceglie, tra gli elementi dell’insieme su cui si sta lavorando, un elemento detto pivot. Scelto il pivot si suddivide l’insieme iniziale in due sottoinsiemi, in cui il primo contiene gli elementi minori di esso ed il secondo quelli maggiori. L’algoritmo funziona sempre, qualsiasi sia la scelta del pivot, sebbene esistano scelte "ragionate" che producono effetti sul tempo di esecuzione in situazioni particolari. Una scelta comune e funzionale è prendere come pivot il primo elemento dell’insieme.

Il partizionamento ha due effetti: ricava i due sottoinsiemi e sposta gli elementi in modo tale che tutti quelli del primo siano minori di quelli del secondo (la sicurezza dipende dal fatto che quelli del primo sono tutti minori del pivot, quelli del secondo tutti maggiori). Per inciso, si noti come non esiste nessun vincolo sul numero di elementi per ciascun sottoinsieme, tutte le combinazioni sono ammesse, contrariamente al caso del MergeSort in cui i sottoinsiemi erano di pari dimensione. Ordinando il primo ed il secondo sottoinsieme e poi concatenandoli, otterremmo l’insieme di partenza ordinato. Naturalmente come algoritmo di ordinamento per i sottoinsiemi si può impiegare nuovamente il QuickSort ad oltranza, fino all’ottenimento del risultato finale.

A livello implementativo si utilizzano per il partizionamento due indici "i" e "j", uno che punta all’elemento iniziale, l’altro che punta all’elemento finale. Si fa scorrere "i" verso destra (lo si incrementa) fino a rilevare un valore maggiore del pivot. Ora si prende "j" e lo si fa scorrere verso sinistra (j–) fino a trovare un elemento minore del pivot. A questo punto si scambiano gli elementi puntati da "i" e "j" e si ripete la procedura fino a che "i" e "j" non convergono (ciò equivale a testare la condizione "i &lt j"). Si confrontino queste righe con l’implementazione C esposta sotto:

int partition( int a[], int l, int r)
{
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;

   while(1)
   {
     do ++i; while( a[i] <= pivot && i <= r );
     do --j; while( a[j] > pivot );
     if( i >= j ) break;
     t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}

Applicazione del QuickSort

Applichiamo subito l’algoritmo ad un esempio di prova:

I = {32, 23, 35, 8, 99, 34, 10, 33, 67}

In primo luogo osserviamo che il pivot per questo turno è 32. Lo contrassegnamo con delle parentesi quadre. Gli indici "i" e "j" puntano inizialmente al primo e all’ultimo elemento della lista (racchiudo gli elementi puntati tra le parentesi tonde).

I = {[(32)], 23, 35, 8, 99, 34, 10, 33, (67)}

Partendo dall’indice "i", che inizialmente punta a 32 e scorre da sinistra verso destra, ci fermiamo appena troviamo un elemento maggiore del pivot, Tale elemento in questo caso è il pivot stesso.

I = {([32]), 23, 35, 8, 99, 34, 10, 33, (67)}

Ora, scorriamo l’indice "j" (inizialmente 67) fino a trovare un elemento minore del pivot.

I = {([32]), 23, 35, 8, 99, 34, 10, (33), 67}
I = {([32]), 23, 35, 8, 99, 34, (10), 33, 67}

A questo punto scambiamo gli elementi puntati da "i" e da "j".

I = {(10), 23, 35, 8, 99, 34, ([32]), 33, 67}

Il primo indice, "i", punta ancora al primo elemento, che è 10. Il primo elemento maggiore del pivot che si trova lungo il percorso verso destra di "i" è 35. Proseguiamo con "j": il secondo indice punta a 32 e scorre verso sinistra, il primo elemento minore del pivot lungo il suo percorso è 8:

I = {10, 23, (35), (8), 99, 34, [32], 33, 67}

Scambiamo gli elementi di posizione "i" e "j":

I = {10, 23, (8), (35), 99, 34, [32], 33, 67}

Ora che "i" e "j" sono consecutivi, il partizionamento è finito; non ci saranno più scambi. Annotiamo i due sottoinsiemi ricavati:

A={inizio, i}; B={i+1, fine}.

Si noti come gli elementi di A siano quelli minori del pivot e gli elementi di B siano quelli maggiori.

A = {10, 23, 8}
B = {35, 99, 34, 32, 33, 67}

L’algoritmo prevede di richiamare se stesso su A e B. Risolviamo velocemente il caso A:

A = {[10], 23, 8}
A = {(8), 23, ([10])}
A1 = {8} (minimale)
A2 = {23, 10} (una chiamata ulteriore di sort produrrà gli insiemi minimali {10} e {23})

Un insieme minimale soddisfa la condizione di terminazione dell’algoritmo ricorsivo del quicksort, che decreta la fine dei conti sul sottoinsieme. Al termine di tutte le chiamate ricorsive si osserverà che il vettore è stato ordinato.

Una bella implementazione del QuickSort, formulata dal prof. R.Lawlor (Dublin Institute of Technology) è la seguente:

void quicksort( int a[], int inizio, int fine)
{
   int limite;
   if( inizio < fine ) 
   {
      limite = partition( a, inizio, fine);
      quicksort( a, inizio, limite-1);
      quicksort( a, limite+1, fine);
   }
}

int partition( int a[], int l, int r)
{
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;

   while(1)
   {
     do ++i; while( a[i] <= pivot && i <= r );
     do --j; while( a[j] > pivot );
     if( i >= j ) break;
     t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}

Il QuickSort ha complessità n*log(n) nel caso medio, nel quale, come gia annunciato, risulta essere di gran lunga l’algoritmo migliore. L’unico punto debole, da evitare assolutamente perché demolisce le prestazioni dell’algoritmo fino a farle degenerare in quadratiche, è il caso peggiore, che si verifica applicando l’algoritmo su un vettore gia ordinato con la scelta del pivot al primo elemento. Si provi ad applicare l’algoritmo in questo caso. Questa problematica sperimentalmente non si verifica se non in casi particolarissimi, e la sua probabilità diminuisce con l’aumentare della quantità di dati da ordinare. Per limitare ulteriormente lo spettro del caso peggiore si può procedere ad una differente tecnica per la scelta del pivot, si può pensare ad esempio, a prendere un elemento casuale, oppure quello medio, od altre scelte, che comunque hanno un prezzo in termini di operazioni. Vista la probabilità veramente scarsa che si verifichi il caso peggiore, la soluzione generalmente migliore continua sempre ad essere quella di scegliere come pivot il primo elemento. Il limite principale del Quick Sort è il fatto di non essere né stabile né in loco.