Università degli Studi di Palermo Facoltà di Ingegneria

Note introduttive su: Analisi della complessità degli algoritmi

Algoritmi di ordinamento

Edoardo Ardizzone & Riccardo Rizzo

Appunti per il corso di Fondamenti di Informatica

A.A. 2004 - 2005

Corso di Laurea in Ingegneria Informatica

Introduzione all’analisi della complessità. Ricerca lineare. I metodi di ordinamento, che verranno introdotti nella seconda parte di queste note, rappresentano una ottima occasione per introdurre un argomento classico dell’informatica, la valutazione della efficienza del software. Un programma è tanto più efficiente quanto più basso è il suo costo (o complessità) computazionale, che dipende dalla memoria centrale e dal tempo necessari per la sua esecuzione. Tranne che in contesti specialistici e per applicazioni avanzate (sistemi embedded, architetture specializzate, etc), che saranno analizzate in corsi successivi, i bassi costi attuali di realizzazione fisica delle memorie e le elevate capacità di indirizzamento dei moderni elaboratori rendono meno significativa la valutazione del primo elemento. Pertanto il costo computazionale di un programma verrà considerato in questa sede dipendente solo dal tempo di esecuzione. Il tempo di esecuzione di un programma dipende: - dalla velocità di esecuzione della macchina, intesa come esecutore astratto del linguaggio di

programmazione, e quindi sia dalle caratteristiche dell’hardware che da quelle del compilatore (o dell’interprete) adoperato;

- dalle caratteristiche dei dati sui quali il programma opera, e in particolare dal numero degli elementi realmente significativi nel problema in esame: è intuitivo che ordinare 10 numeri interi è meno costoso che ordinarne 10000.

Questo tipo di dipendenza rende ardua una valutazione assoluta della efficienza di un modulo, e praticamente impossibile il confronto tra due moduli che svolgono lo stesso compito utilizzando algoritmi differenti: non vi è nessuna certezza che se un modulo A è più veloce di un modulo B su un PC, lo sia anche su un elaboratore di classe superiore. Inoltre A potrebbe richiedere meno tempo di B se i dati sono disposti in un certo modo, ma B potrebbe essere più veloce per un’altra disposizione dei dati. Il problema può essere semplificato sulla base delle seguenti considerazioni. Per quanto riguarda la dipendenza dalla macchina, nonostante le forti differenze tra le prestazioni degli elaboratori reali, la loro architettura e, di conseguenza, il loro repertorio istruzioni hanno caratteristiche comuni, per quanto differenti possano essere le modalità di indirizzamento, il numero e il tipo dei registri, la durata del ciclo macchina, etc.: sicuramente in tutte le macchine è presente la capacità di reperire e depositare dati in memoria, e di trasformarli applicando semplici operazioni. Inoltre, a parità di codice sorgente e di hardware, i codici oggetto prodotti da compilatori più o meno sofisticati, eventualmente utilizzando in modo più o meno spinta le proprietà dell’hardware, differiranno normalmente per il fatto che una certa istruzione del codice sorgente sia tradotta, ad esempio, in una sequenza di 4 istruzioni macchina piuttosto che di 7. Supponendo che il tempo di esecuzione di ogni istruzione macchina sia lo stesso, si avrà un guadagno di tempo, impiegando il codice prodotto dal compilatore più sofisticato, di 3/7 del tempo impiegato se si utilizza il codice prodotto dal secondo compilatore, indipendentemente dal numero di volte in cui deve essere eseguita l’istruzione sorgente. In sostanza, la qualità della macchina (hardware più software di base) incide al più per un fattore costante sul tempo di esecuzione complessivo di un qualsiasi programma: se l’esecuzione di un programma, avente i dati di ingresso d, su una macchina M richiede un tempo t = f(d), lo stesso programma su una macchina M’ avrà un tempo di esecuzione t’ = c·f(d). Pertanto, anche se il valore di c può essere notevole (e questo giustifica le differenze di prezzo tra elaboratori di classe diversa), la valutazione dell’efficienza di un programma può essere effettuata, a meno di un fattore costante, prescindendo dalle caratteristiche della macchina. Per quanto riguarda la dipendenza dai dati, come detto, è naturale aspettarsi che il tempo di esecuzione di un programma aumenti al crescere della dimensione del problema, che normalmente (ma non necessariamente) può essere espressa come numero di elementi di un vettore, come numero di righe di una tabella, come numero di parole di un testo, etc. Le precedenti considerazioni permettono di definire un approccio alla analisi approssimata della complessità di un programma, che viene illustrato in dettaglio prendendo in considerazione il problema della ricerca di un elemento in una sequenza (di interi, in questo caso), realizzata

mediante un array. L’algoritmo utilizzato è quello di ricerca lineare (o esaustiva), che prevede il confronto dell’elemento cercato con tutti gli elementi dell’array. Il seguente metodo, codificato in modo volutamente ridondante, costituisce una prima implementazione della ricerca lineare, restituendo la posizione dell’elemento cercato, se presente nell’array, oppure -1: public int firstLinearSearch( int a[], int key ) { int n = a.length; // n.ro elementi dell’array int pos = -1; // valore da restituire se elemento non trovato for (int counter = 0; counter < n; counter++) if ( a[counter] == key ) pos = counter; // elemento trovato else pos = pos; // solo per bilanciare il n.ro di istruzioni eseguite return pos } In questo caso, la dimensione del problema è n. L’esecuzione delle prime due istruzioni richiede un tempo totale c1 indipendente dal valore di n, così come indipendente da n è il tempo c3 necessario per l’esecuzione dell’istruzione di ritorno successiva al ciclo for. Per quanto riguarda invece il ciclo for, poiché la inizializzazione della variabile di controllo viene eseguita una volta sola, il suo tempo di esecuzione può essere incluso in c1. Il tempo c2 richiesto per una singola esecuzione del corpo del ciclo è quello richiesto per l’esecuzione del test dell’istruzione if e per l’esecuzione o dell’una o dell’altra assegnazione di un valore a pos (una delle due assegnazioni viene comunque eseguita). In questo tempo, che non dipende da n, vanno inclusi anche il tempo necessario per il singolo incremento della variabile di controllo e per una singola esecuzione del test di continuazione del ciclo. Il numero di ripetizioni del ciclo è invece ovviamente legato al valore di n. Pertanto si può scrivere per il tempo totale di esecuzione del metodo: t = c1 + c2 · n + c3

Questa equazione non precisa il tempo reale di esecuzione del frammento di programma, ma fornisce informazioni utili ad una valutazione approssimativa dello stesso. Intanto essa separa la dipendenza dalla macchina dalla dipendenza dai dati, e mostra come un eventuale cambiamento delle caratteristiche hardware e software della macchina, che può modificare i valori di c1, c2 e c3, non altera in ogni caso la dipendenza lineare del tempo di esecuzione dalla dimensione del problema. Pertanto, se quest’ultima raddoppia, si avrà un tempo di esecuzione “quasi” doppio, non esattamente doppio per la presenza delle costanti. Per valori abbastanza grandi di n, è intuibile che la dipendenza lineare dai dati contribuisca al tempo di esecuzione molto più della dipendenza dalla macchina. Si può pertanto concludere che la complessità computazionale del metodo firstLinearSearch è, al crescere della dimensione del problema, lineare con essa. Si dice in questo caso che la complessità asintotica del programma è O(n), cioè è dello stesso ordine di grandezza di n. In generale, se un programma ha costo f(n), si dirà che la complessità è O(f(n)). Nei casi più frequenti, f(n) è lineare o logaritmica o quadratica, più raramente cubica o esponenziale. Si noti tuttavia che in molti casi il costo di un programma può dipendere non solo dalla dimensione dei dati, ma anche dai particolari valori dei dati stessi, cioé dalla loro distribuzione, come risulta anche dall’esempio seguente, che costituisce peraltro una implementazione più realistica della ricerca lineare. public int otherLinearSearch( int a[], int key ) { int n = a.length; // n.ro elementi dell’array for (int counter = 0; counter < n; counter++) if ( a[counter] == key ) return counter; // elemento trovato return –1 // elemento non trovato }

E’ evidente che questa volta il tempo di esecuzione della ricerca dipende non solo dalla dimensione dei dati, ma anche dalla posizione nella sequenza dell’elemento cercato. Infatti firstLinearSearch scandisce sempre tutto l’array, mentre otherLinearSearch interrompe la scansione non appena trova l’elemento cercato, se esiste. L’espressione del tempo di esecuzione, ricavabile con una analisi analoga a quella condotta in precedenza, è la seguente: t = k1 + k2 · m + k3 dove le costanti k1, k2 e k3 differiscono, sia pure di poco, dalle costanti c1, c2 e c3, anche se l’istruzione return counter viene eseguita al più una volta, quando l’elemento viene trovato. La differenza fondamentale sta però nel fatto che m coincide con n solo se l’elemento cercato è l’ultimo della sequenza, oppure se esso non si trova nella sequenza. In tutti gli altri casi, m è minore di n, e in alcuni casi molto minore (per esempio, se la sequenza contiene 10000 elementi e l’elemento cercato è il primo). Sarebbe naturalmente troppo complicato determinare espressioni analitiche, per quanto approssimate, del tempo di esecuzione che tengano conto di tutte le possibili distribuzioni dei dati. Si preferisce pertanto limitare la trattazione ad alcuni casi di maggiore interesse, come il caso migliore, il caso peggiore, il caso medio. Il caso migliore si ha in corrispondenza ai valori dei dati per i quali si ottiene il costo computazionale minore, mentre il caso peggiore corrisponde alla configurazione dei dati che determina il costo maggiore. La stima del costo nel caso medio si ottiene valutando la media aritmetica dei costi rispetto a tutti i possibili dati di ingresso. Per il metodo otherLinearSearch, il caso migliore è quello in cui l’elemento cercato è il primo della sequenza, e il programma effettua una sola iterazione, e quindi un solo confronto; il caso peggiore è quello in cui l’elemento cercato è l’ultimo della sequenza, o non è presente (n confronti); il caso medio (solo se la ricerca ha esito positivo) richiede (n + 1)/2 confronti, se si assume che tutti gli elementi dell’array possano essere cercati con uguale probabilità. Infatti, dato che in tal caso la probabilità è pari a 1/n, si ha per il numero medio di confronti da effettuare:

( )( )2

1EProb11

+==∑∑

==

nniii

n

i

n

i

essendo Prob(E(i)) la probabilità che l’elemento da cercare sia quello in posizione i. Il caso medio richiede quindi, nel caso della ricerca lineare, circa la metà dei confronti necessari nel caso peggiore. In generale, il modo più utile di valutare la complessità computazionale è quello di considerare il caso peggiore, che permette di determinare una espressione del costo f(n), funzione solo della dimensione dei dati, tale che in nessun caso a dimensione n il tempo di esecuzione può risultare superiore a f(n). L’analisi del caso peggiore consente in altre parole di determinare una maggiorazione certa sul comportamento di un programma. Applicando il criterio del caso peggiore alla ricerca lineare, si ottiene che i due metodi firstLinearSearch e otherLinearSearch sono equivalenti dal punto di vista dell’efficienza di esecuzione. Però è intuitivo come normalmente otherLinearSearch si comporti meglio di firstLinearSearch, e l’analisi del caso medio lo conferma. In generale, l’analisi del caso medio può fornire informazioni aggiuntive di grande utilità e pertanto nel seguito si farà riferimento al caso peggiore e, quando necessario, al caso medio. Una conseguenza delle approssimazioni introdotte nella valutazione della complessità è la sua indipendenza dal linguaggio di programmazione adoperato. In effetti, la complessità asintotica è normalmente valutata in relazione all’algoritmo impiegato, piuttosto che al codice che lo implementa. Inoltre, il modello di costo adottato per la valutazione approssimata della complessità assegna un costo (convenzionalmente) unitario a ciascuna istruzione semplice, indipendentemente dalla sua effettiva complessità matematica, e quindi dal numero più o meno elevato di istruzioni macchina

necessarie per la sua effettuazione. Del pari unitario è considerato il costo di un test (di fine ciclo, di una istruzione if, etc.), mentre si assume nullo il costo della mera attivazione di un modulo di programma (trascurando quindi il tempo necessario per il passaggio dei parametri, per l’allocazione di variabili locali, etc.). Se un programma è costituito da due parti P e Q che vengono eseguite sequenzialmente, e il costo delle quali è, rispettivamente, O(f(n)) e O(g(n)), allora il costo complessivo del programma è O(max(f(n), g(n))). Questo risultato si generalizza al caso di un programma costituito da un numero qualunque di parti eseguite sequenzialmente. Se un programma richiede per k volte l’esecuzione di un frammento di codice la cui complessità, relativa alla i-esima esecuzione, è O(fi(n)), il costo complessivo sarà

( )( )∑i i nfO

Nel caso particolare in cui la complessità relativa a ciascuna esecuzione del frammento di programma è la stessa, si ha ovviamente che il costo complessivo è O(k · f(n)). Infine, si può notare come alcune operazioni contribuiscano maggiormente di altre al costo di un algoritmo. Negli esempi finora mostrati, sono rilevanti, in quanto ripetute più volte, le operazioni effettuate dentro il ciclo for, piuttosto che quelle esterne ad esso. Questa considerazione può essere generalizzata: date le approssimazioni introdotte, la valutazione della complessità può essere direttamente effettuata in molti casi con riferimento ad una o più operazioni dominanti dell’algoritmo. Tali operazioni dominanti, se esistono, possono normalmente essere individuate analizzando i cicli più interni dell’algoritmo. Se una operazione dominante è eseguita d(n) volte, la complessità del frammento di programma che la contiene è O(d(n)).

Ricerca binaria Si consideri adesso il caso di una sequenza ordinata di n valori (per esempio in ordine crescente), contenuta come prima in un array a. Si ha pertanto: [ ] [ ]1+≤ iaia per 0 1−<≤ ni

La ricerca di un determinato elemento all’interno di una sequenza ordinata può essere effettuata in modo molto più efficiente rispetto alla ricerca lineare, utilizzando un algoritmo di ricerca binaria o dicotomica, che deve il suo nome al fatto di essere basato su un ciclo che, ad ogni passo, dimezza la porzione di sequenza in cui effettuare la ricerca. Per l’applicabilità dell’algoritmo, oltre all’ordinamento della sequenza è necessario che la struttura dati che la contiene sia accessibile in modo diretto, come è appunto il caso di un array. L’algoritmo può essere illustrato informalmente nel modo seguente: 1. Si esegue un primo confronto tra l’elemento cercato e l’elemento median della sequenza.

L’elemento mediano di una sequenza ordinata di n elementi è quello di posto . Se n è pari, l’elemento mediano è per convenzione quello di posto n/2.

2/ n

2. Se l’elemento mediano coincide con l’elemento cercato, la ricerca termiAltrimenti si tratta uno dei due casi seguenti: 2.1. L’elemento mediano è maggiore dell’elemento cercato: ciò implica c

cercato esiste nella sequenza, non può che trovarsi nella sua prima metà. 2.2. L’elemento mediano è minore dell’elemento cercato: ciò implica che, se l

esiste nella sequenza, non può che trovarsi nella sua seconda metà. In ogni caso, la ricerca continua restringendo l’analisi alla sola metàpotenzialmente in grado di contenere l’elemento cercato, e ripetendo i pass

o

na con successo.

he, se l’elemento

’elemento cercato

della sequenza i 1 e 2, fino alla

individuazione dell’elemento cercato o finché la porzione di sequenza indagata si riduce ad un solo elemento che non è quello cercato.

Il metodo seguente implementa l’algoritmo di ricerca binaria in maniera iterativa:

public int bynarySearch( int a[], int key ) { int n = a.length; // n.ro elementi dell’array int low = 0; // indice basso della porzione di array analizzata int high = n - 1; // indice alto della porzione di array analizzata int middle; // indice del mediano while ( low <= high ) { // ciclo di analisi, termina quando low > high middle = ( low + high ) / 2; if ( key == a[middle] ) return middle; //ricerca terminata con successo else if ( key < a[middle] ) high = middle – 1; //vai nella prima metà else low = middle + 1; // vai nella seconda metà } // fine ciclo di analisi return –1 // elemento non trovato } L’analisi approssimata della complessità del metodo porta all’espressione: t = c1 + c2 · m + c3 essendo, come nei casi precedenti, c1 e c3 i tempi di esecuzione delle parti esterne al ciclo, che sono costanti in quanto indipendenti dai dati, e c2 il tempo necessario per l’esecuzione di una singola iterazione del ciclo. m è il numero di volte che il ciclo viene ripetuto. In realtà, se la ricerca termina con successo, il tempo di esecuzione dell’ultima iterazione è sicuramente inferiore a c2, in quanto viene eseguita una istruzione contro una istruzione e un test delle iterazioni precedenti. Inoltre, l’istruzione return esterna al ciclo viene eseguita solo se la ricerca non ha successo, quindi c3 dovrebbe essere preso in considerazione solo per questo caso. L’equazione data, tuttavia, può essere ancora accettata in quanto sicuramente non migliorativa della realtà. Per determinare il valore di m in funzione dei dati di ingresso, si osservi che nel caso migliore m vale 1, in quanto viene eseguita una sola iterazione del ciclo. Nel caso peggiore, che è quello di ricerca infruttuosa, si esce dal ciclo quando high diventa più grande di low, cioè dopo un numero di dimezzamenti della porzione di sequenza da indagare uguale a n2logL’espressione del tempo di esecuzione diviene quindi:

3221 log cncct ++= e si può concludere che la complessità asintotica della ricerca binaria è O(log(n)). Rispetto alla ricerca lineare, questo rappresenta un miglioramento notevolissimo. Se n = 1000, nel caso peggiore il tempo di esecuzione della ricerca binaria è (circa) 10/1000 di quello della ricerca lineare, mentre se n = 1000000 il tempo di esecuzione si riduce addirittura a 20/1000000. Si dice che la ricerca binaria ha nel caso peggiore una complessità inferiore di un ordine di grandezza a quella della ricerca lineare. Il concetto di ordine di grandezza può essere formalizzato. Date due funzioni di variabile intera, f(n) e g(n), strettamente maggiori di 0 e monotone crescenti (ipotesi assai ragionevoli per funzioni che descrivono il tempo di esecuzione di un algoritmo), si dice che f(n) è O(g(n)), ovvero che le due funzioni sono dello stesso ordine, se:

( ) ( )( ) cngnfn

=∞→

lim

essendo c una costante non nulla e finita. Invece l’ordine di f(n) è minore (maggiore) di quello di g(n) quando:

( ) ( )( ) ( ∞==∞→

0lim ngnfn

)

Le implicazioni pratiche dei concetti appena trattati possono essere notevoli. Si supponga che un certo problema possa essere risolto da programmi di complessità di ordine crescente, come indicato nella seguente tabella, che mostra i tempi di esecuzioni per diversi valori della dimensione dei dati. Per fissare le idee si suppone di utilizzare un elaboratore capace di compiere un milione di operazioni al secondo.

Complessità n =10 n =100 n =1000 log n 3.32 µsec 6.64 µsec 9.96 µsec

n 10 µsec 100 µsec 1 msec n2 100 µsec 10 msec 1 sec n3 1 msec 1 sec 1000 sec 2n 1.024 msec 10 milioni di volte

l’età della terra ----

Si può notare che, al crescere della complessità e delle dimensioni, la difficoltà del problema può diventare rapidamente non gestibile. Nella letteratura specializzata, vengono in realtà definiti problemi trattabili, cioè problemi di cui sia realistico calcolare la soluzione con uno strumento automatico, i problemi per i quali esiste un algoritmo la cui complessità sia di un ordine di grandezza polinomiale. Tutti gli altri sono considerati intrattabili. Esistono anche dei problemi, detti NP-completi, per i quali esiste il sospetto, ma non ancora la certezza matematica, che siano intrattabili. In pratica, anche un problema trattabile può diventare intrattabile al crescere della dimensione. Per esempio, dalla tabella precedente, nel caso della complessità cubica, con n = 10000 si otterrebbe un tempo di esecuzione di 1000000 di secondi, cioè di più di 11 giorni. Esistono infine anche dei problemi algoritmicamente insolubili, per i quali cioé non sono ancora stati individuati degli algoritmi, e quindi non ha senso parlare di soluzione automatica.

Il problema dell’ordinamento

L'ordinamento dei dati è una delle applicazioni informatiche basilari in pressocché tutti i contesti applicativi. Il suo scopo è anche quello di facilitare le ricerche dei dati all'interno di insiemi di dati ordinati. In generale i dati possono essere molto complessi, per esempio si può trattare di oggetti caratterizzati da molti attributi. Si chiama chiave l’attributo scelto come base per l'ordinamento. In generale, supponendo che siano dati gli elementi:

a1, a2, ,an ordinare consiste nel permutare questi elementi secondo un ordine:

ak1, ak2

, ,akn

tale che, data una funzione di ordinamento f, risulti:

f ak1f ak2

f akn Nel seguito la chiave si considera intera e gli altri attributi di ciascun elemento vengono trascurati.

Un metodo di ordinamento è detto stabile se mantiene inalterato l'ordine relativo dei dati aventi chiavi uguali; se gli elementi sono già ordinati secondo una chiave secondaria la stabilità del metodo di ordinamento è spesso desiderabile. Le prestazioni degli algoritmi di ordinamento sono normalmente confrontate considerando operazioni dominanti quali il numero di confronti fra gli elementi ed il numero di trasposizioni di elementi. I metodi di ordinamento più semplici sono i metodi di ordinamento diretto, che richiedono un numero di confronti dell’ordine di N2, essendo N il numero di elementi da ordinare. In generale, i metodi di ordinamento diretto sono adatti ad illustrare le caratteristiche principali dei metodi di ordinamento, sono brevi e facili da capire, ma in genere adatti ad ordinare insiemi di elementi di piccola dimensione. I metodi di ordinamento diretto trattati nel seguito sono il metodo di ordinamento per selezione, il metodo di ordinamento per inserzione e il metodo di ordinamento a bolle o bubblesort. Verrà anche trattato un metodo non diretto ma normalmente più efficiente, il metodo di ordinamento veloce o quicksort. Tutti gli algoritmi verranno illustrati con riferimento ad array di numeri interi.

Ordinamento per selezione

Nell'ordinamento per selezione si procede per passi successivi: si seleziona il minimo degli elementi dell’array e lo si scambia con il primo (o ultimo) elemento, quindi si esclude questa posizione dalla analisi e si cerca nuovamente il minimo, posizionandolo al secondo (o penultimo) posto dell'array, e così via, fino al completo ordinamento dell’array. Si supponga per esempio di dover ordinare in senso crescente il seguente array:

21 19 32 9 12

Primo passo

Trovato il minimo, lo si scambia con l'elemento più a sinistra:

21 19 32 9 12

Secondo passo

Il primo elemento dell'array è adesso l’elemento più piccolo, e il minimo va cercato fra gli elementi rimanenti, segnati in giallo. Trovato il minimo, lo si sposta al secondo posto.

9 19 32 21 12 Gli altri passi di ordinamento sono simili. Il numero complessivo di passi da eseguire è pari alla lunghezza dell’array meno 1. Il seguente metodo selectionSort implementa l'ordinamento per selezione di un array. Esso ha a sua volta bisogno di due metodi: minPos per trovare la posizione del minimo di una parte dell’array (cui va passata come argomento la posizione da cui cominciare la ricerca del minimo) e swap capace di

scambiare di posto due elementi di un array. Di seguito si riporta il codice relativo ai tre metodi. public void selectionSort (int[] b) { for ( int i=0; i < b.length-1; i++) { int mPos = minPos(b, i); //trova il minimo nell'array, da i alla fine swap(b, mPos, i); // scambia gli elementi } }//fine metodo selectionSort //----------------------------------- public int minPos (int[] a, int from) { int posMinimo=from; for (int i=from+1; i< a.length; i++) if ( a[i] < a[posMinimo] posMinimo=i; return posMinimo; } //------------------------------------ public void swap (int[] v, int i, int j) { int temp=v[i]; v[i]=v[j]; v[j]=temp; }

Per determinindividuare unminimo di uquest’ultimo hcorpo è a sua essere considquante volte velementi, l’algper la ricerca nel secondo pelementi rimaelementi. Il nGauss):

Si è sfruttato i

(21

=∑=

MMjM

j

L'ordine di grper selezione distribuzione caso, in partic

Complessità dell'algoritmo di ordinamento per selezione

are la complessità asintotica dell'algoritmo di ordinamento per selezione si puòa eventuale operazione dominante. Ad ogni passo l’algoritmo effettua la ricerca del

na porzione di array, seguita dallo scambio tra due elementi dell’array. Mentrea un tempo di esecuzione costante, la ricerca del minimo richiede un ciclo for, il cuivolta basato sul confronto fra due elementi dell'array. Questo confronto può pertantoerato come l’operazione dominante dell’intero algoritmo. Basta quindi determinareiene eseguito il confronto fra due elementi dell'array. Supponendo che l'array abbia Noritmo esegue N – 1 passi. Durante il primo passo, la porzione di array da visitare

del minimo è di N – 1 elementi, e questo è anche il numero di confronti da effettuare;asso occorre invece eseguire N – 2 confronti per trovare il minimo tra gli N – 1sti; nel k-simo passo si eseguono N – k confronti per trovare il minimo di N – k + 1umero di confronti da eseguire può essere calcolato con la seguente formula (di

( ) ( ) ( ) ( ) ( )2

12111

1

1

1

1

−=

−−−=−−=− ∑∑

−

=

−

=

NNNNNNkNNkNN

k

N

k

l noto risultato: )1+

andezza del numero dei confronti è pertanto N2, per cui l’algoritmo di ordinamento ha complessità O(N2). Si osservi che questa conclusione è indipendente dalla dei dati. In altri termini, l’ordinamento per selezione ha complessità O(N2) in ogni olare anche se l’array fosse inizialmente già ordinato.

Ordinamento per inserzione lineare

In questo algoritmo di ordinamento si considera l'array diviso in due parti: una parte già ordinata, ed una ancora da ordinare. Per ogni passo dell'algoritmo si prende un elemento dalla parte non ordinata dell’array e lo si inserisce al posto che gli compete nella parte ordinata. L'algoritmo termina quando si esauriscono gli elementi della parte non ordinata. Supponendo che gli elementi debbano essere ordinati per valori non decrescenti, l'algoritmo può essere così illustrato:

Il puntatore ordinati punta alla prima locazione della porzione non ordinata.

L'elemento viene memorizzato in una variabile temporanea temp.

A partire dall'ultimo elemento della parte ordinata, il contenuto della variabile temporanea è confrontato con ciascun elemento della parte ordinata.

Se il contenuto di temp risulta minore dell'elemento dell'array, si passa al successivo confronto, dopo aver spostato l’elemento verso destra di una posizione.

Se si trova un elemento dell'array minore di temp allora il contenuto di temp viene inserito nel posto immediatamente a destra di questo elemento.

Si sposta verso destra il riferimento alla porzione non ordinata, e si ripete il ciclo.

L'algoritmo puo' essere implementato in un unico metodo che si riporta sotto: public void insertionSort (int[] v) { int i; // scandisce i dati nella parte ordinata int ordinati; //puntatore al primo elemento della parte non ordinata = //numero di elementi ordinati boolean ins; //indica se e' possibile inserire l'elemento fra quelli //ordinati for ( ordinati=1; ordinati < v.length; ordinati ++) { temp=v[ordinati]; ins=false; i=ordinati; // i punta al primo elemento della parte non ordinata while (!ins && i>0) //si scorre la parte ordinata if (temp < v[i-1]) { v[i]=v[i-1]; //si sposta l'elemento a destra i--; } else ins=true; //altrimenti si inserisce al posto dell'elemento //corrente v[i]=temp; } }

Complessità dell'algoritmo di ordinamento per inserzione lineare

Il ciclo esterno viene eseguito N – 1 volte, se N è il numero degli elementi dell'array, mentre il numero di iterazioni del ciclo interno dipende da i e da v[i]. Il tempo di esecuzione c2 di una iterazione del ciclo interno è invece costante rispetto a questi due elementi. Si ha pertanto:

∑−

=

+−=1

121 )1()(

N

kkmcNcNf

essendo c1 il tempo di esecuzione della parte del ciclo esterno che precede il ciclo interno, mentre mk è il numero di iterazioni del ciclo interno alla k-esima iterazione del ciclo esterno (che coincide peraltro con il numero di confronti da effettuare, per cui il confronto è l’operazione dominante). Per determinare il valore di mk, si supponga di essere nel caso peggiore. Il caso peggiore è quello in cui, ad ogni iterazione del ciclo esterno, l’elemento preso in esame, cioé temp, è minore di tutti gli elementi della porzione non ordinata dell’array, cioé se l'array è inizialmente ordinato in maniera decrescente e lo si vuole ordinare in maniera crescente. In questo caso occorre eseguire un confronto durante la prima iterazione del ciclo esterno, due confronti durante la seconda e k nella k-esima. Pertanto:

( )21)1()1()( 21

1

121

NNcNckcNcNfN

k

−+−=+−= ∑

−

=

La complessità dell’ordinamento per inserzione lineare, nel caso peggiore, è pertanto ancora O(N2). Se invece l’array fosse inizialmente già ordinato, si dovrebbe eseguire un solo confronto ad ogni iterazione del ciclo esterno, e pertanto la complessità sarebbe O(N).

Ordinamento a bolle (bubblesort)

L'algoritmo sfrutta il fatto che in un array ordinato, per esempio per valori non decrescenti, l’elemento nella generica posizione i-esima è non maggiore dell’elemento nella posizione i + 1-

leSort (int[] b) {

pass++) // ciclo esterno (n.ro passate)

chiaramente il confronto tra due elementi contigui ventuale scambio. L’istruzione viene eseguita (N – 1) (N – 1) volte, per cui

{ r non avvenuto scambio gth; pass++) // ciclo esterno (n.ro passate)

{ swap( b, i, i + 1); // eventuale scambio

esima, per ogni i compreso tra 0 e N - 2, essendo N gli elementi dell’array. Pertanto l’ordinamento può essere ottenuto con una serie di iterazioni, durante ognuna delle quali ciascun elemento è confrontato con il successivo, e scambiato con esso se la relazione di ordinamento non è già soddisfatta. Durante ogni passata vengono quindi confrontate tutte le coppie di elementi contigui: se in una coppia il primo valore è minore o uguale al secondo, gli elementi restano inalterati, viceversa se il primo valore è maggiore del secondo, i due elementi vengono scambiati di posto. Il nome dell’algoritmo è giustificato dal fatto che i valori più piccoli salgono gradualmente verso la cima dell’array (considerando la posizione di indice 0 come cima dell’array), proprio come avviene alle bolle d’aria immerse in un liquido. L’algoritmo richiede N - 1 iterazioni. Il metodo seguente implementa l’algoritmo: public void firstBubb for ( int pass = 1; pass < b.length;

{ for ( int i = b.length – 2; i >= 0; i--) // ciclo interno (n.ro confronti)

{ if ( b[i] > b[i + 1] ) swap( b, i, i + 1); // eventuale scambio

// fine ciclo interno } } // fine ciclo esterno } rt // fine metodo firstBubbleSo

L’istruzione dominante di questo metodo è dell’array, seguito dall’ela complessità è O(N2). Osserviamo però che al termine della prima passata, che inizia confrontando l’ultimo elemento con il penultimo, l’elemento più piccolo dell’array sarà correttamente collocato nella prima posizione dell’array stesso. La seconda iterazione potrà quindi prendere in considerazione solo gli N - 1 elementi più grandi non ancora ordinati. Al termine della seconda passata, il secondo elemento più piccolo sarà collocato correttamente in seconda posizione. La terza iterazione potrà quindi prendere in considerazione solo gli N - 2 più grandi elementi non ancora ordinati. Al termine della k-esima passata, il k-esimo elemento più piccolo sarà collocato correttamente in k-esima posizione, e così via, fino al completo ordinamento dell’array. Inoltre, non è detto che tutte le N – 1 iterazioni del ciclo esterno siano necessarie. Se durante una passata, infatti, non si verifica alcuno scambio, l’array risulta già ordinato, e non è necessario ricorrere ad ulteriori iterazioni. Pertanto, l’algoritmo può essere modificato, in modo da adattare la sua complessità alla configurazione dei dati, come nella seguente versione: public void bubbleSort (int[] b) boolean noswap; // flag vero pe

r ( int pass = 1; pass < b.len fo { noswap = true;

r ( int i = b.length – 2; i >= pass - 1; i--) // ciclo interno (n.ro foconfronti) { if ( b[i] > b[i + 1] ) // confronto noswap = false; }

} // fine ciclo internop ) return; if ( noswa

} // fine ciclo esterno

} // fine metodo bubbleSort

Complessità dell'algoritmo di ordinamento a bolle In questa formulazi l’algoritmo esegue one, se l’array è inizialmente già ordinato (caso migliore), solo la prima iterazione del ciclo esterno, e poi termina. La complessità è determinata quindi solo dal ciclo interno, ed è pertanto O(N). Se l’array è inizialmente ordinato a rovescio (caso peggiore), sono necessarie tutte le N – 1 iterazioni del ciclo esterno, perchè dopo ognuna di esse solo un elemento si troverà nella posizione corretta. Durante la pass-esima iterazione del ciclo esterno, peraltro, sono necessarie N – 1 – (pass –1) = N – pass iterazioni del ciclo interno. Pertanto:

( ) ( )1)1()1()(1

221

1

21 passcNNcNcpassNcNcNfNN

=−−+−=−+−= ∑∑−−

( ) ( ) ( )21)1(

211)1( 21221

11

NNcNcNNcNNcNc

passpass

−+−=

−−−+−=

==

La complessità dell’algoritmo di ordinamento a bolle, nel caso peggiore, è pertanto O(N2).

rdinamento veloce (quicksort)

più semplice ordinare più vettori piccoli piuttosto che uno molto grande. Per ottenere le parti più piccole, si divide l'array in due parti, separate da un

O

L'algoritmo si basa sulla osservazione che è

elemento centrale detto sentinella o pivot (cardine): una parte contiene elementi tutti minori del pivot e una parte contiene tutti elementi maggiori del pivot. Le due parti così ottenute vengono ulteriormente divise in due, attorno ad altri due elementi pivot, e così via, fino a quando ogni parte è costituita da soli due elementi, che vengono ordinati facilmente. Si noti come i subarray via via più piccoli risultino ordinati fra di loro, ma siano in generale disordinati al loro interno. La classe seguente, che implementa l'ordinamento veloce, è ripresa da [3], ed è disponibile all'indirizzo . http://www.horstmann.com/bigjava.html public class QuickSorter { private int[] a; (int[] anArray) {

public QuickSorter a = anArray; } void sort() {

- 1);

public sort(0, a.length } lic void sort(int from, int to) {

int p = partition(from, to);

pub if (from >= to) return; sort(from, p); sort(p + 1, to); } vate int partition(int from, int to) pri

{

int i = from - 1;

a[i] < pivot) i++; j--; while (a[j] > pivot) j--;

int pivot = a[from]; int j = to + 1; while (i < j) { i++; while ( if (i < j) swap(i, j); } return j; } vate void swap(int i, int j) {

a[i] = a[j];

metodo sort divide il vettore in due parti e viene chiamato ricorsivamente sulle due parti del ttore stesso. Le due parti del vettore sono ottenute usando il metodo che, posto il

pri int temp = a[i]; a[j] = temp; } } Ilve partition

valore pivot uguale al primo elemento dell'array da ordinare (pivot = a[from]), organizza le due parti del vettore in modo che a sinistra stiano solo gli elementi che risultato minori di pivot e a destra gli elementi maggiori di pivot. Se due elementi non rispettano questa relazione, il metodo partition utilizza il metodo swap per scambiarne la posizione; come si può vedere, partition non ordina il vettore, in quanto il semplice scambio non assicura che le due parti del vettore siano ordinate al loro interno. L'ordinamento del vettore nella sua globalità si ottiene per il fatto che le parti del vettore vanno diventando sempre più piccole rimanendo ordinate fra di loro. La routine partition si arresta quando j punta al primo valore minore del pivot ed i punta al primo valore maggiore del pivot. Il programma è illustrato dall'esempio in figura:

Il pivot non è inserito fra le due parti in cui ilvettore è diviso, ma è lasciato sempre nella partedi destra, ed è riordinato nelle passatesuccessive. Questo è il motivo per cui lachiamata a sort ogni volta deve considerare glielementi da from a p e da p+1 a to. Si notianche che ogni elemento è spostato una solavolta.

Un altro algoritmo, ottenuto modificando di poco il precedente, posiziona invece subito il pivot al

public int partition2(int from, int to)

< pivot) i++;

blic void sort2(int from, int to)

to);

In questo caso il pivot è

e

i

stati

posto giusto. Sotto si riportano i metodi modificati.

{ int pivot = a[from];

int i = from; int j = to;

) while (i < j {

while (a[i] while (a[j] > pivot) j--; if (i < j) swap(i, j); }

turn j; re } pu {

if (from >= to) return; int p = partition2(from, sort(from, p-1); sort(p + 1, to); }

portato subito al posto giusto e non deve esserpiù considerato nelle successive chiamate dsort. Inoltre in questo caso gli elementi possono essere spopiu' volte, si osservi per esempio il pivot della prima iterazione.

Complessità dell'algoritmo di ordinamento veloce

Il metodo sort, a parte le due attivazioni ricorsive, esegue un numero di operazioni che dipende da partition. A sua volta, partition ha una complessità che dipende dal numero di iterazioni del ciclo while (i < j). Questo numero è al più to + 1 – (from – 1), dato che ad ogni iterazione viene incrementato i e decrementato j. Pertanto la complessità di partition è lineare con il numero di elementi sui quali opera. La complessità di sort dipende inoltre chiaramente dal numero di attivazioni ricorsive di sort stesso, e quindi dalla scelta del pivot. Indicando con f(N) la funzione, ancora ignota, che esprime il tempo di esecuzione necessario per ordinare un array di Nelementi, si ha:

>−++=

=1 se)()(1 se

)(NtNftfcNNc

Nf

Si è supposto che la prima attivazione di sort richieda di ordinare un vettore di t elementi e uno di N – t elementi. Questa equazione di ricorrenza ammette soluzioni diverse al variare di t. Il caso peggiore dell’algoritmo è quello in cui ogni volta viene scelto come pivot l’elemento più grande (o più piccolo) del vettore. Se, come nel metodo mostrato in precedenza, il pivot coincide ogni volta con il primo elemento dell’array, il caso peggiore è dunque quello di un array già ordinato. Infatti, in questo caso, ogni volta l’array viene partizionato in due parti, una avente un solo elemento e l’altra i rimanenti. Ricordando che, se si prescinde dal costo delle attivazioni ricorsive, la complessità è lineare, per la complessità di sort si può così affermare: costo di sort(0,N-1) = O(N) + costo di sort(0,N-2) sort(0,N-2) = O(N-1) + costo di sort(0,N-3) sort(0,N-3) = O(N-2) + costo di sort(0,N-4) .... = ..... sort(0,1) = O(2) + costo di sort(0,0) sort(0,0) = O(1)

Sommando si ottiene, per il caso peggiore, la complessità O(N2), dello stesso ordine, cioé, degli altri algoritmi di ordinamento meno sofisticati finora visti. L’analisi del caso peggiore non permette però di spiegare il buon comportamento pratico del quicksort. E’ utile a tal proposito una analisi del caso migliore. Questo si verifica quando il pivot è scelto in modo tale da suddividere in due parti di uguale lunghezza. L’equazione di ricorrenza diviene infatti:

( )22)2()2()( NfcNNfNfcNNf +=++= Si può dimostrare che la soluzione di questa equazione è O(NlogN), e si dimostra altresì che questa è anche la complessità dell’algoritmo nel caso medio. Intuitivamente, il comportamento generalmente efficiente dell’algoritmo quicksort si spiega proprio con il fatto che è improbabile che il pivot divida l’array in due parti, di cui una molto più grande dell’altra. E’ invece molto più probabile che l’array sia diviso in due parti aventi all’incirca lo stesso numero di elementi, realizzando quindi una situazione di caso migliore.

Bibliografia

1. Niklaus Wirth "Algoritmi+Strutture Dati=Programmi", Tecniche Nuove, 1987. 2. Luca Cabibbo "Fondamenti di Informatica, Oggetti e Java", Mc Graw-Hill, 2004. 3. Horstmann-"Concetti di informatica e fondamenti di Java 2", Apogeo, 2002. 4. C. Batini et al. “Fondamenti di programmazione dei calcolatori elettronici”, F. Angeli, 1992. 5. S. Ceri, D. Mandrioli, L. Sbattella “Informatica arte e mestiere”, McGraw-Hill, 1999.