Da Wikiversità, l'università aperta.

Questa lezione è solo un abbozzo. Se puoi contribuisci adesso a migliorarla secondo le convenzioni di Wikiversità.
Per l'elenco completo degli stub, vedi la relativa categoria

Un classico problema algoritmico consiste nell'ordinare una sequenza di n elementi. Per poter ordinare tale sequenza è necessario che gli elementi appartengano tutti ad un insieme dove è definita una relazione d'ordine; ossia, presi due elementi a scelta, deve sempre essere possibile accertare quale venga prima e quale dopo. Dunque per poter ordinare è necessario che esista:

• una chiave per ogni elemento (ad esempio: la matricola di uno studente, il prezzo di un prodotto, la data di un acquisto ecc..)
• un metodo (che solitamente restituisce un intero) che definisca l'ordine tra due elementi (ad esempio: int strcmp(char *s1, char *s2) per le stringhe in C)

[modifica] Proprietà degli algoritmi di ordinamento

Esistono alcune proprietà che un algoritmo può presentare che sono molto utili e possono venire sfruttate persino per creare altri algoritmi di ordinamento.

[modifica] Stabilità

Un algoritmo di ordinamento si dice stabile se in presenza di due elementi con la medesima chiave (due acquisti nella stessa data ad esempio) non modifichi l'ordine con cui i due elementi si presentavano prima dell'ordinamento. Ad esempio se applicassimo ad una lista di persone ordinate per nome, un algoritmo di ordinamento stabile, in modo tale da ordinare le persone in base al cognome, otterremmo un elenco in cui tutte le persone con lo stesso cognome sono ordinate per nome (come nei normali elenchi telefonici). Se tale algoritmo non fosse stabile le persone con lo stesso cognome sarebbero disposte "casualmente" rispetto al nome. Non ha senso parlare di stabilità quando l'elemento rappresenta la propria chiave, ad esempio in un array di interi due '14' non sono distinguibili l'uno dall'altro dunque anche se venissero scambiati non potremmo accorgercene.

[modifica] Sul posto

Un algoritmo di ordinamento su array si dice sul posto se in ogni dato istante al più è allocato un numero costante di variabili, oltre all'array da ordinare: un algoritmo, quindi, è stabile se non utilizza array di supporto. Si parla solo di array, perché in una lista concatenata, lo spazio occupato è già doppio rispetto al numero di elementi (un valore per l'elemento e un puntatore per il prossimo).

[modifica] Algoritmi di ordinamento per confronto

In questa prima parte tratteremo soltanto di algoritmi di ordinamento per confronto, ossia che confrontano tra di loro, due elementi alla volta. Vedremo che, in alcuni casi, non è necessario confrontare gli elementi tra di loro. Ad esempio, come si fa ad ordinare un mazzo di 52 carte?

[modifica] Algoritmi di ordinamento "poco efficienti"

Esistono almeno tre algoritmi molto facili e di complessità temporale Θ(n²):

• Bubble sort
• Selection sort
• Insert sort

Per completezza vedremo brevemente gli ultimi due algoritmi, analizzandone la complessità

[modifica] Selection Sort

Informalmente l'algoritmo può essere descritto nel seguente modo: si cerca il minimo della sequenza ancora da analizzare e lo si scambia con il primo elemento ancora da analizzare fino a che non resta soltanto un elemento.

L'animazione "salta" un passaggio, ossia la ricerca del minimo che ha complessità lineare (in tutti i casi: peggiore, migliore o medio). Dunque per ogni elemento (in realtà l'ultimo elemento è già in ordine, dunque n-1 volte) viene ripetuta la ricerca del minimo. La prima volta si cercherà su n elementi, la seconda su n-1, la terza su n-2... Dunque la complessità è determinata dalla somma

Dunque il selection sort ha complessità temporale (per tutti i casi) quadratica. Ossia T_p(n) = T_m(n) = T_a(n) = Θ(n²) Dove T_p(n),T_m(n),T_a(n) sono rispettivamente il tempo impiegato nel caso peggiore, migliore e medio. Il selection sort non è sul posto poiché può invertire l'ordine di elementi della stessa chiave (il lettore può provare a trovare un esempio in cui tale algoritmo non sia sul posto). È stabile' poiché utilizza solo poche variabili locali (e non è ricorsivo). La proprietà più interessante del selection sort è quella che la parte già "analizzata" è ordinata, infatti da 0 a i l'array è ordinato, nessun elemento verrà aggiunto in quella parte. Ne diamo una versione in Java:

public static void ssort(int[] a) {
    int n = a.length;
    for(int i = 0; i < n-1; i++) {        
        scambia(a, i, indiceMinimoDa(a, i));
    }
}
 
static int indiceMinimoDa(int[] a, int k) { 
    int iMin = k;                             
    for(int i = k+1; i < a.length; i++)       
        if(a[i] < a[iMin]) iMin = i;            
    return iMin;                                            
}

[modifica] Insertion Sort

L'insertion sort è un algoritmo di ordinamento che si basa (come intuibile dal nome) sull'inserimento di un elemento all'interno di un array ordinato.

Inizialmente si considera il primo elemento come un array ordinato; si prosegue inserendo il secondo elemento al posto giusto: se è maggiore rimane dov'è se è minore (del primo elemento) si scambia. Così avanti come mostra l'animazione

L'algoritmo di inserimento deve scorrere in media metà array prima di trovare la posizione giusta per l'elemento da inserire. Nel caso peggiore dovrà scorrerlo tutto fino in fondo (se l'elemento era più piccolo di tutti quelli già inseriti), nel caso migliore dovrà effettuare solo un controllo (se è più grande di tutti quelli già inseriti). La sommatoria che descrive il caso medio è così definita

Dunque anch'essa quadratica (analogo discorso per il caso peggiore). Il caso migliore invece (che si presenta quando l'array è già ordinato) è lineare.

Dunque l'algoritmo di ordinamento ha la seguente complessità:

Caso peggiore: T_p(n) = Θ(n²) (Array ordinato all'inverso)

Caso medio: T_a(n) = Θ(n²)

Caso migliore: T_m(n) = Θ(n) (Array ordinato)

Anche in questo caso ne diamo una versione in Java:

public static void isort(int[] a){
    int j;
    for (int i =1;i<a.length;i++){
        int t = a[i];
        j=i;
        while(j>0 && t<a[j-1]){
            a[j]=a[j-1];
            j--;
            }
        a[j]=t;
    }			
}

[modifica] Algoritmi di ordinamento efficienti

[modifica] Merge Sort

Il merge sort è il primo algoritmo d'ordinamento ricorsivo che vediamo. Se ne può dare anche una versione iterativa di cui, però, vedremo soltanto il codice per completezza di trattazione. (Nota lessicale, d'ora in poi utilizzerò il termine "sequenza" sia per indicare array che liste concatenate; il mergesort può essere applicato, con le dovute precauzioni ad entrambi i tipi astratti).

Il merge sort è un algoritmo di tipo "Divide et Impera", ossia è diviso in due parti:

• "Divide" Dividere la sequenza in due parti (operazione banale per gli array, più complicata per una lista)
• "Imperia" Fondi le due sequenze in una che contiene tutti gli elementi in ordine.

Il mergesort per "fondere" le due sequenze utilizza, ovviamente, l'algoritmo di merge. Lo studente, a questo punto del corso dovrebbe sapere come funziona l'algoritmo di merge, ne faremo comunque una breve analisi.

Date due sequenze, S1 e S2, ordinate, per ottenere S3, anch'essa sequenza ordinata e tale che ogni elemento di S1 e S2 appartenga a S3 si scorrono S1 e S2 inserendo in S3 l'elemento più piccolo tra le due. Una volta terminata S1 (o S2) si completa inserendo in S3 i rimanenti elementi di S2 (o S1).

Nel mergesort S1 e S2 sono solitamente due sequenze interne alla sequenza originale, per identificarle servono quindi almeno 3 indici. La sequenza target deve essere un essere dichiarata e allocata a parte, poiché non è possibile riscrivere gli elementi sulla sequenza di partenza (quantomeno non è facile realizzare un algoritmo senza sequenza di appoggio).

Diamo qui un'implementazione del merge in Java

private static void merge(int[] a, int left, int mid, int right, int[] h) {
    //a ordinato da [left, mid] e [mid+1, right]
    int x = left;
    int y = mid + 1;
    int n = left;
    if (left>mid || mid>=right || a[mid] <= a[mid + 1]) {
        return;
    }
    while (x <= mid && y <= right) {
        if (a[x] <= a[y]) {
            h[n++] = a[x++];
        } else {
            h[n++] = a[y++];
        }
    }
    while (x <= mid) {
        h[n++] = a[x++];
    }
    while (y <= right) {
        h[n++] = a[y++];
    }
    for (int i = left; i <= right; i++) {
        a[i] = h[i];
    }
}

Il mergesort quindi, divide in due la sequenza da ordinare fino a che non rimane solo un elemento (che è ordinato), successivamente fonde i singoli elementi creando gruppi di due, i quali a loro volta verranno fusi tra loro creando la sequenza finale ordinata.

In pseudo codice il Mergesort può essere descritto così:

MergeSort(sequenza S){
    if(lunghezza(S) >1){
        S1, S2 <-- Dividi (S)
        MergeSort(S1)
        MergeSort(S2)
        S <-- Merge(S1, S2)
    }
}

Analizzando il caso in cui la sequenza è costituita da un array, possiamo notare come il lavoro sia effettuato esclusivamente dal merging, infatti dividere un array in due significa semplicemente scegliere l'indice medio. In una lista, invece, dividere a metà significa scorrere la lista almeno una volta (facendo saltare alternativamente i puntatori), con complessità lineare. In entrambi i casi, il merge ha una complessità lineare alla somma della lunghezza delle due sequenze (dunque la divisione della lista non influisce asintoticamente sulla complessità dell'algoritmo). Notare inoltre che il merge ha solo un caso migliore (lo studente cerchi di trovarlo dal codice dato sopra), perciò anche il mergesort presenterà solo un caso migliore (un array ordinato), mentre il caso medio corrisponderà a quello peggiore. L'equazione di ricorrenza (si veda le lezioni sulla ricorsione), per il caso peggiore e medio, sono le seguenti

Possiamo provare a risolverla manualmente per sostituzioni successive. (Vedremo in seguito il master theorem per risolvere questo tipo di equazioni).

Questa non è una vera e propria dimostrazione tuttavia, il risultato è giusto e se ne può dare una dimostrazione induttiva a posteriori.

Il caso migliore, che si presenta quando l'array è già ordinato, e il merge non fa niente, ha complessità lineare.

Dunque il mergesort ha complessità : migliore (di gran lunga migliore) di tutti gli algoritmi visti fino a qui. Il mergesort è stabile: nel merge è fondamentale la riga if (a[x] <= a[y]), infatti l'uguale permette di scegliere sempre per primo l'elemento di sinistra, ossia quello che, precedentemente all'ordinamento, veniva prima di un altro elemento, eventualmente con chiave uguale. Il megersort non è sul posto: oltre a essere ricorsivo (e quindi occupare spazio sullo stack) è necessario un array ausiliare; la complessità spaziale del merge è dunque Θ(n).

Essendo la versione ricorsiva molto facile da implementare, mostriamo solo la versione iterativa in Java:

public static void msortI(int[] a){
	int i, p,e,m;	
	int N = a.length;
	int[] helper = new int[N];
	i=0;
	p=1;
	while(p<N){		
		while(i<N){
			m = (i+p) >=N ? N : i+p;
			e = (i+2*p)>=N ? N : i+2*p;
			merge(a,i,m-1,e-1,helper);
			i+=2*p;
		}			
		p*=2;
		i=0;	
        }
}