Algoritmi e Strutture dati

O P

eseguita un’ulteriore chiamata sulla parte che rimane della sequenza, che ha dimensione #

& &

(base di , ossia il più grande intero minore di ). C’è poi la procedura merge, che ha

# #

θ().

complessità Il tempo di calcolo totale T(n) è quindi espresso in maniera ricorsiva:

θ(1) = 1

() = Q θ()

RM NS + RO PS + + 2 > 1

2 2

Questa è un’equazione di ricorrenza, ossia un’espressione che contiene se stessa ma con un

argomento più piccolo di quello iniziale. Volendo risolvere questa ricorrenza si può ricorrere

all’”albero delle chiamate”:

# Assumo che n sia una potenza di 2;

# ⋅

Assumo che il costo dell’istruzione merge sia c n.

Valutando il passo ricorsivo, il tempo di calcolo si può quindi riscrivere come:

() = R S + R S + ⋅ = 2 R S + ⋅

2 2 2

$

Da qui, T( ) vale:

#

R S = 2 R S + ⋅

2 4 2

$

E T( ) corrisponde a:

'

R S = 2 R S + ⋅

4 8 4 $

Dato che n è una potenza di 2, la diramazione proseguirà fino ad ottenere T( ) = T(1), ma T(1)

$

è un valore noto, pari a 1. Arrivati a questo punto i T(1) da sommare saranno n. 11

.

I livelli che si creano, ovvero il numero di passaggi fino ad arrivare a T(1), sono #

Sommando i tempi di calcolo così ottenuti, livello per livello, si arriva a:

() = ⋅ ⋅ + = θG ⋅ ()H

#

Il funzionamento del merge-sort è mostrato nell’immagine seguente:

TEOREMA DELL’ESPERTO

Un ulteriore modo per calcolare i tempi di esecuzione degli algoritmi ricorsivi consiste nel

teorema dell’esperto. Data un’equazione di ricorrenza del tipo:

() = ⋅ R S + ()

()* +,- ()* +

# ∃ > 0 | () = ( ) ≥ 1, > 0, ∈ ℕ () = θ( )

Se allora

* *

()* + ()* +

# )

() = θ( () = θ( ⋅ )

Se allora

* * # $

()* +.-

# ∃ > 0 | () = Ω( ) ∃ < 1 | ⋅ R S ≤ ⋅ ()

Se ed

* /

() = θ(())

definitivamente allora

QUICK-SORT

Il quick-sort è un algoritmo di ordinamento basato sul divide et impera, alternativo al merge-

sort. Dato un vettore V[l…r] da ordinare, opera come di seguito:

Passo 1:

# Sceglie un elemento di V, detto pivot (k);

# Partiziona V[l…r] in due sottovettori V[l…q] e V[q+1…r], con q da determinare in

modo tale che, riarrangiando gli elementi di V mediante scambi, si ottenga che:

≤

Tutti gli elementi di V[l…q] siano k;

o ≥

Tutti gli elementi di V[q+1…r] siano k.

o 12

Passo 2:

# Ordina ricorsivamente V[l…q] e V[q+1…r] eseguendo i tre passi sui due sottoarray.

Passo 3:

# Combina i sottoarray.

Lo pseudocodice è il seguente:

Per quanto riguarda la procedura partition, ne esistono due: quella di Hoare e quella di Lomuto.

Quella di Hoare funziona come di seguito:

# Sceglie il primo elemento dell’array o del sottoarray, quindi V[l], come pivot;

# ≤

Scansiona V a partire dall’ultimo elemento e si ferma quando trova un elemento

pivot;

# ≥

Scansiona V a partire dal primo elemento e si ferma quando trova un elemento pivot;

# Scambia i due elementi.

A livello di pseudocodice l’implementazione è la seguente:

dove il valore dx che viene restituito corrisponde a q nella procedura del quick-sort. 13

Il tempo di esecuzione del quick-sort su un vettore V di n elementi è determinato dalla seguente

equazione di ricorrenza:

() = () + ( − ) + θ() θ(),

in quanto la procedura partition ha complessità alla quale vanno aggiunti il tempo di

esecuzione del quick-sort sul primo sottoarray di dimensione q ed il tempo di esecuzione del

secondo, di dimensione n – q.

Nel caso base, ossia quando l’array ha lunghezza 1, l’unica istruzione da eseguire è il primo

controllo, quindi il tempo di esecuzione è:

T() = 1 = θ(1)

Nel caso il vettore abbia lunghezza > 1, considero ora il caso peggiore, ossia degli input V tali

per cui il partizionamento, per ogni chiamata ricorsiva, sia sempre il più sbilanciato possibile,

avendo quindi un solo elemento da una parte e tutti i restanti dall’altra. Il valore q varrebbe

quindi 1 e l’equazione di ricorrenza assumerebbe la forma:

() = (1) + ( − 1) + θ()

Per trovare T(n - 1) si può sostituire tale espressione a T(n), ottenendo quindi:

( − 1) = (1) + ( − 2) + θ( − 1)

quindi, unendola alla precedente, rimane:

() = (1) + (1) + ( − 2) + θ( − 1) + θ()

ma tale sostituzione si può applicare anche a T(n – 2), che diventa:

( − 2) = (1) + ( − 3) + θ( − 2)

() = (1) + (1) + (1) + ( − 3) + θ( − 2) + θ( − 1) + θ()

θ(1).

e così via, per n – 1 volte, fino ad arrivare a T(n – (n – 1)), quindi a

Si arriva quindi ad un’equazione della forma:

$ ( + 1) # #

) )

() = + θ ]^ ` = + θ a − 1b = + θ( = θ(

2

0 2 #

Consideriamo ora il caso migliore, quindi la condizione in cui, per ogni chiamata ricorsiva,

3.4

=

l’array sia perfettamente bilanciato, quindi il partizionamento è tale che . L’equazione

#

di ricorrenza diventa dunque:

() = 2 ⋅ R S + θ()

2

Questa equazione è analoga a quella del merge-sort, e si è dimostrato nel paragrafo dedicato

θ( ⋅ ()).

che ha complessità

Nonostante la complessità sia analoga o maggiore di quella del merge-sort, il quick-sort ha

θ

costanti (c e c ) più piccole nel calcolo di rispetto a quelle del merge-sort, risultando quindi

1 2

più efficiente, a meno del caso peggiore. Inoltre, a differenza di quest’ultimo, il quick-sort è in

loco, in quanto la procedura partition necessita di un numero di variabili aggiuntive costante

ed indipendente dalla dimensione dell’input. 14

# )

θ(

Per evitare la complessità nel caso peggiore, che si verifica quando l’array è già ordinato,

si può modificare la procedura partition in modo tale che il pivot scelto non sia il primo

elemento del vettore ma la sua mediana.

Un’alternativa altrettanto valida consiste nell’impostare come pivot un valore casuale

compreso tra la prima e l’ultima posizione:

Di seguito lo pseudocodice della partition alternativa a quella di Hoare, ossia quella di Lomuto:

Graficamente, il quick-sort funziona come di seguito:

COUNTING SORT

Il counting sort è un algoritmo di ordinamento che opera per conteggio. Non è sempre

utilizzabile, ma solo qualora si conosca il range di valori da ordinare, contenuti in un dato

vettore A. I passaggi che effettua sono: 15

# Si contano le occorrenze di ogni valore del range e si mette questo conteggio in un

vettore C ausiliario, in modo da sapere il numero di elementi che precedono ogni valore

del range nell’ordine (quindi il numero di elementi minori o uguali all’elemento stesso);

# Si modifica C sommando, per ogni casella, quella corrente a quella precedente;

# Si scorrono gli elementi del vettore di partenza A, a partire dall’ultima posizione,

inserendo ogni elemento nella posizione corretta in un altro array B di dimensione

analoga ad A in base alle informazioni ottenute nello step precedente, inserite in C.

Graficamente, il funzionamento del counting sort è:

RADIX SORT

Il radix sort è un algoritmo di ordinamento non basato sul confronto, ma:

# Parte dall’analisi della cifra meno significativa e raggruppa gli elementi all’interno di

contenitori (bucket), in base al valore della cifra che si sta analizzando (bucket 0…9).

Procederà poi, nelle successive iterazioni, ad analizzare la seconda cifra meno

significativa e così via;

# Gli elementi vengono inseriti all’interno del bucket in ordine di apparizione nell’array;

# Ad ogni iterazione si ricostruisce l’array partendo dal bucket 0 ed inserendo ogni

elemento di ogni bucket nell’ordine in cui è stato inserito al passo precedente;

# Effettua un numero di passaggi pari al numero di cifre dell’elemento maggiore;

# Risulta vantaggioso quando l’array da ordinare è di grandi dimensioni.

Graficamente, il funzionamento del radix sort è: 16

PILE (STACK)

Una pila (stack) è un insieme dinamico, quindi variabile nel tempo, definito su un dominio D.

Può essere identificata come una sequenza S dove:

# S = <> (sequenza vuota).

oppure

# S = < a , , … , > | ∀ ∈ {1, 2, … , } ∈ , dove a è l’elemento in cima alla

n

" # $ 0

pila S.

Questi insiemi dinamici vengono manipolati ed utilizzati dagli algoritmi. La manipolazione

avviene tramite operazioni dette di modifica (come inserimento e cancellazione), ma ne

esistono altre che non vanno a modificare l’insieme dinamico, nonostante siano anch’esse a

disposizione degli algoritmi; queste operazioni sono dette interrogazioni o query (come i vari

controlli). Le operazioni di inserimento e cancellazione effettuate su una pila S qualunque sono

tali che l’ultimo elemento inserito in S è il primo ad essere cancellato, secondo la politica LIFO.

OPERAZIONI

Sia l’insieme di tutte le possibili pile su un dominio D. Le operazioni su di cui un algoritmo

può disporre sono le seguenti:

# Push (inserimento):

: × →

∀(, ) ∈ ×

S = <> (, ) =< > ∈

Se

o S = < a , … , > (, ) = < a , … , > ∈

Se

o " $ " $."

)

PUSH(, richiede in input una coppia: una pila ed un elemento del dominio.

# Pop (cancellazione):

⁄

: {<>} → ×

∀