Appunti di Informatica

Questa versione col flag si comporta meglio della precedente solo nel caso

migliore in cui passa da n^2 confronti a n.

Questi due algoritmi di ordinamento sono cosiddetti per confronto, si basano sul

confronto tra il valore di due elementi, quindi possono essere usati su qualunque tipo

di dati, e necessitano come minimo di n*log(n) operazioni per ordinare una lista.

Per introdurre algoritmi di tipo ricorsivo dobbiamo introdurre il concetto di divide et

impera: divido il problema in input in k sotto problemi e opero ricorsivamente ( se al

suo interno sono presenti chiamate a se stesso per gestire sotto problemi analoghi a

quello dato ) sui k sotto problemi di dimensioni inferiore n/k.

Una volta risolti i sotto problemi si combinano le soluzioni trovate per creare la

soluzione al problema dato.

d) Merge sort:

un esempio di algoritmo che si basa sul divide et impera è il merge sort:

esso divide gli N elementi della sequenza in due sotto sequenze di N/2

elementi ciascuna, le ordina usando ricorsivamente il merge sort, fino ad

arrivare a sotto sequenze di lunghezza 1, e infine le fonde per produrre come

risposta la sequenza ordinata.

Per fondere le due sotto sequenze ordinate si parte dal presupposto che il

minimo della sequenza fusa sia il più piccolo tra i minimi delle due sotto

sequenze, quindi si generano due indici che tengono conto degli elementi

ancora da fondere e si fa progredire quello che indicizza l’elemento più

piccolo; la complessità di questa procedura è N sia nel caso migliore che in

quello peggiore.

Il costo dell’algoritmo del merge sort è espresso dalla risoluzione

dell’equazione di ricorrenza attraverso il teorema del Master; si ha come

risultato che sia nel caso peggiore che nel caso migliore:_ il costo sia n*log(n).

e) Quick sort:

L’idea alla base dell’algoritmo è quella di scegliere casualmente un elemento

separatore, detto pivot, e separare attraverso il partition ( si permuta, cioè

trovare le diverse combinazioni tali che a sinistra del pivot vi saranno solo

elementi minori e viceversa a destra) l’insieme da ordinare in due sotto

insiemi, per poi ordinare ricorsivamente entrambi.

Partition pone due indici, uno col compito di scandire la lista dall’inizio fino al

pivot e l’altro dal pivot fino alla fine, fermandosi quando gli indici si

incontrano.

una volta che il primo incontra un elemento maggiore si ferma aspettando che

il secondo trovi un elemento minore, una volta localizzati i due elementi si

scambiano.

Il tempo di esecuzione del partition è N sia nel caso migliore che in quello

peggiore; per il tempo di esecuzione del quick sort dipende da quanto l

partizionamento sia sbilanciato e nel caso peggiore, col pivot che è un estremo

della porzione da ordinare, sommando i costi ad ogni livello di ricorsione

otteniamo N^2. Nel caso migliore e nel caso medio però viene eseguito molto

più velocemente con una ricorrenza di N*log(N).

Alberi di decisione

Gli ordinamenti per confronti possono essere visti astrattamente in termini di alberi di

decisione: un albero binario usato per rappresentare la sequenza di confronti che

vengono effettuati da un ordinamento.

Ogni nodo interno è etichettato con i:j e corrisponde al confronto tra a(i) e a(j); il

sotto albero sx. definisce i successivi confronti nel caso in cui a(i)<a(j).

Relazione di ricorrenza

Il costo di esecuzione è espresso dalla seguente funzione ricorsiva ( equazione di ricorrenza ):

{ C se n ≤ 0

( ) = ( )

T n n

( )+ ( )

+

d n a∙ T f n se n> 0

b

Legenda:

c: costante positiva

a: numero di sotto stanze

n/b: dimensioni delle sotto stanze

d(n): costo per dividere in a sotto stanze

f(n): costo per ricombinare le a sotto stanze, ovvero N sia nel caso di merge che col quick