Ordinamento (programmazione in C)

Per approfondire questo argomento, consulta la pagina Il problema dell'ordinamento.

lezione Ordinamento (programmazione in C)
	Tipo: lezione
	Materie: Algoritmi e strutture dati Fondamenti di programmazione in C
	Avanzamento: lezione completa al 75%

Questa pagina tratta l'ordinamento nel linguaggio C.

Considerazioni generali sugli algoritmi

Per risolvere un problema computabile esistono molti algoritmi risolutivi. Algoritmi che vengono valutati secondo diversi criteri, criteri che fanno di un certo algoritmo la soluzione migliore in alcuni casi ma non in altri, in base alle necessità del caso. I principali criteri di valutazione d'un algoritmo sono:

Tempo di calcolo occorrente (complessità temporale)
Occupazione di memoria (complessità spaziale)

E solitamente ottimizzare rispetto a un criterio significa spendere rispetto all'altro.

La rapidità di calcolo è sempre un fattore importantissimo nella determinazione della bontà di un algoritmo ma essa è ovviamente correlata con la quantità d'informazioni da elaborare, e quindi anche al numero di instruzioni da seguire in particolare operazioni di confronto e scambio.

Insertion sort

L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria.

L'algoritmo utilizza due indici: uno punta all'elemento da ordinare e l'altro all'elemento immediatamente precedente. Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito (da qui insertion).

Il primo indice punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

Analisi delle prestazioni

È un algoritmo che utilizza la minima quantità di memoria indispensabile, ma è lento, soprattutto con array di grosse dimensioni. Anche se per array piccoli è solitamente l'algoritmo di ordinamento più veloce.

Effettua in media $N^{2}/4$ confronti ed altrettanti spostamenti (mezzi scambi), che possono diventare il doppio nel caso peggiore. La complessità diventa lineare nel caso di vettore quasi ordinato. Se il vettore è già ordinato non vengono effettuati scambi e il numero di confronti è pari agli elementi del vettore stesso.

Codice in C

void InsertionSort(int x[], int n) 
{
   int i, j, app;
 
   for (i = 1; i < n; i++)
   {
      app = x[i];
       
      for (j = i - 1; (j >= 0) && (x[j] > app); j--){
               x[j+1] = x[j];
               j--;
             }
      x[j + 1] = app;
   }
}

La funzione qui riportata riceve due parametri: x è l'array da ordinare, n è il numero dei suoi elementi.

Selection sort

Anche l'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in place ed in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sottosequenza ordinata, che occupa le prime posizioni dell'array, e la sottosequenza da ordinare, che costituisce la parte restante dell'array. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.

I passi sono i seguenti:

Si inizializza un puntatore i che va da 0 a dim (dove dim è la lunghezza dell'array).
Si cerca il più piccolo elemento dell'array
Scambia l'elemento più piccolo con l'elemento alla posizione i
Incrementa l'indice i e si torna al passo uno fino alla fine dell'array.

Analisi delle prestazioni

L'ordinamento per selezione effettua $N(N-1)/2$ confronti. Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a $N-1$ (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo è determinato dal numero di confronti.

Codice in C

void SelectionSort(int a[], int dim){
	int i, j, min, tmp;
	for(i=0;i<dim-1;i++){
		min=i;
		for(j=i+1;j<dim; j++){
			if(a[j]<a[min])
                     min=j;
		}
	tmp=a[min];
        a[min]=a[i];
        a[i]=tmp;
	}
}

Bubblesort

Il bubblesort è un algoritmo iterativo, ovvero basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito (che si scandisca l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante).

Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto, e così via fino al confronto fra penultimo e ultimo elemento. Per ogni confronto, se i due elementi confrontati non sono ordinati, essi vengono scambiati. Durante ogni iterazione, almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array.

Ne conseguono due considerazioni:

Se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;
Alla iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto dei valori alle posizioni N-1-i e N-i.

Un insieme di ottimizzazioni sono basate sull'osservazione che se, in una data iterazione, non avviene alcuno scambio, allora l'array è necessariamente ordinato e l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1esima iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile booleana (o equivalente) usata come "flag" che indica se l'iterazione corrente ha prodotto uno scambio. La variabile viene reimpostata a false all'inizio di ogni iterazione, e impostata a true solo nel caso in cui si proceda a uno scambio. Se al termine di una iterazione completa il valore della variabile flag è false, l'intero algoritmo viene terminato. Questa tecnica produce una riduzione del tempo medio di esecuzione dell'algoritmo, pur con un certo overhead costante (assegnamento e confronto della variabile flag).

Analisi delle prestazioni

Il bubble sort effettua all'incirca $N^{2}/2$ confronti ed $N^{2}/2$ scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è $\Theta (n^{2})$ .

Codice in C

 void BubbleSort(int *array, int elemN)
 {
   int i, tmp, ultimo;
   int alto=elemN; /* elemN è il numero degli elementi del vettore da ordinare */
   ultimo=alto;
   
   while (alto >= 0) /* in questo modo si evita 1 passaggio*/
     { 
         ultimo = -1;
         for (i=0; i<alto; i++) 
         {
           if (array[i]>array[i+1]) 
           { /* ">" per ordinamento crescente, "<" per ordinamento decrescente*/
             tmp = array[i]; 
             array[i] = array[i+1]; 
             array[i+1] = tmp;
             ultimo = i;
           } 
         }
     alto = ultimo;
     }
 }

tmp è dichiarata di tipo int, quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare la sua dichiarazione.

Quicksort

Quicksort è un ottimo algoritmo di ordinamento ricorsivo in place che si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.

Il Quicksort è stato sottoposto a un'analisi matematica approfondita ed estremamente precisa, tanto che le sue prestazioni sono state comprese a fondo e il suo comportamento è stato descritto in modo molto accurato. I risultati ottenuti in fase di analisi sono stati verificati sperimentalmente in modo esteso e l'algoritmo di base è stato migliorato al punto da diventare il metodo ideale per un gran numero di applicazioni pratiche.

Analisi delle prestazioni

Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni temporali migliori tra quelli basati sul confronto; ma usa molta memoria; poiché, essendo ricorsivo, occorre creare molte istanze della funzione. Inoltre se le cose non sono fatte bene può arrivare ad una situazione critica e richiedere una profondità di ricorsione pari al numero di elementi del vettore.

Le prestazioni di questo algoritmo abbastanza complesse e sarebbero da considerare il caso peggiore, quello intermedio e quello migliore. A livello didattico ci basti sapere che esso effettua in media ${2N}\log {N}$ confronti ed ${2N}\log {N}$ scambi, ed esegue $N^{2}/2$ confronti nel caso peggiore, con sempre circa NlogN scambi.

Codice in C

 void sort(int array[], int begin, int end) {
    int pivot, l, r; 
    if (end > begin) {
       pivot = array[begin];
       l = begin + 1;
       r = end+1;
       while(l < r)
          if (array[l] < pivot) 
             l++;
          else {
             r--;
             swap(array[l], array[r]); 
          }
       l--;
       swap(array[begin], array[l]);
       sort(array, begin, l);
       sort(array, r, end);
    }
 }

Approfondimenti

Wikipedia

Wikibooks