Algoritmi e Strutture Dati

Pila

Una Pila (o Stack) è una lista lineare a lunghezza variabile, dove inserimenti ed estrazioni vengono

effettuate solo in un estremo, detto testa (o top) della pila.

Si basa sul principio del “last in first out”, LIFO, ossia che l’ultimo elemento ad essere inserito è poi

il primo ad essere estratto. Operazioni su una Pila

push(e) Operazione di inserimento.

Viene inserito un elemento e al top della pila.

pop() Operazione di estrazione.

Viene estratto l’elemento in quel momento presente al top della pila.

isEmpty() Operazione di controllo se la pila è vuota (restituisce true) o meno (restituisce false).

Una Pila può essere implementata sia tramite una catena, con le operazioni di push e pop che

avverranno in testa alla catena, che tramite un vettore.

Per quanto riguarda l’implementazione attraverso un vettore, è necessario stabilire a priori la

dimensione n massima della pila e sarà necessario tenere conto della posizione dell’elemento top

attraverso un contatore, che sarà l’elemento nella posizione non vuota più a destra nel vettore.

x x x x x

0 1 2 3 top n-1

Assumendo che top = -1 indichi la pila vuota, le due operazioni di inserimento ed estrazione

possono essere schematizzate come segue:

Operazione di inserimento: push(e) Costo Algoritmo

top = top + 1;

se top ≥ n

allora overflow; O(1)

altrimenti

v[top] = e;

Operazione di estrazione: pop() Costo Algoritmo

se top = -1

allora underflow;

altrimenti O(1)

restituisci v[top];

top = top - 1;

Espressioni Infisse e Postfisse con una Pila

Attraverso una Pila è possibile trasformare una espressione infissa in una espressione postfissa

(ossia un’espressione scritta con l’operatore dopo i suoi operandi) e valutare, inoltre, quest’ultima.

Entrambi i processi di trasformazione e valutazione sono illustrati qui sotto.

Infissa a Postfissa Esempio

→

se “(“ niente;

→

se operando scrivi nel risultato;

→

se operatore push(operatore); Risultato:

→ ·

se ”)” scrivi(pop()) nel risultato; + +

·

· · ·

Valutazione Postfissa Esempio

→

se operando push(operando);

→

se operatore push(pop () operatore pop ());

2 1 6

8 4 24 7

9 415

17 17 408

5 5 5 5 5 2075

Coda

Una coda (o Queue) è una lista lineare, dove l’inserimento viene effettuato ad un estremo fondo (o

real) e l’estrazione dall’altro estremo testa (o front).

Si basa sul principio del “first in first out”, FIFO, ossia che il primo elemento ad essere inserito è poi

anche il primo ad essere estratto. Operazioni su una Coda

put(e) Operazione di inserimento.

Viene inserito un elemento e al rear della coda.

get() Operazione di estrazione.

Viene estratto l’elemento in quel momento presente al front della coda.

isEmpty() Operazione di controllo se la coda è vuota (restituisce true) o meno (restituisce false).

Come una Pila, anche una Coda può essere facilmente implementata attraverso un vettore.

Dunque, è necessario stabilire a priori la dimensione n massima della coda e sarà necessario

tenere conto della posizione nel vettore del front (testa) e del rear (fondo), attraverso due contatori

F e R.

F è, quindi, l’indice della posizione del vettore contenente la testa della coda; se la coda è vuota il

valore di F sarà uguale ad R (F = R).

R è, invece, l’indice della prima posizione libera del vettore, ossia dove verrà effettuato il

successivo inserimento.

Inizialmente viene posto F = R = 0, per indicare che la coda è vuota.

Ad ogni inserimento, R deve essere incrementato per indicare la posizione successiva libera.

Invece, ad ogni estrazione, F deve essere incrementato per indicare l’elemento testa successivo

della coda.

Questo tipo di implementazione presenta un problema: dopo molti inserimenti e cancellazioni, la

parte occupata dagli elementi della coda tende a spostarsi verso il fondo del vettore e, quando

R = n-1, non è più possibile inserire nuovi elementi, anche se si effettuassero delle estrazioni.

x x x

0 1 2 F R n-1

Per potere allora sfruttare sempre tutte le n posizioni del vettore, conviene pensare il vettore

stesso come una struttura circolare, in cui il primo elemento segue logicamente l’ultimo.

x x x x x x x

0 1 R F n-1

Questa modifica però presenta un problema, dato che nel caso in cui F = R non si è in grado di

distinguere il caso in cui la coda sia vuota da quello in cui la coda sia piena.

La soluzione che si può prendere in considerazione è quella di sacrificare una posizione del

vettore, quindi in un vettore di n elementi se ne potranno memorizzare n-1, e richiede di

incrementare subito R quando si vuole fare un inserimenti, in modo che se dopo l’incremento di R

risulta F = R, allora vuol dire che la coda contiene già n-1 elementi ed è quindi piena (overflow).

Se, invece, vi era F = R prima dell’incremento, cioè il vettore è vuoto, dopo l’incremento risulterà

F ≠ R.

Di seguito sono illustrati gli algoritmi di inserimento ed estrazione in una coda Q.

Operazione di inserimento: put(e) Costo Algoritmo

se R = n-1

allora A = 0;

altrimenti

A = R + 1;

se F = A O(1)

allora overflow;

altrimenti

Q[R] = e;

R = A;

Operazione di estrazione: get() Costo Algoritmo

se F = R

allora underflow;

altrimenti

restituisci Q[R];

se F = n-1 O(1)

allora F = 0;

altrimenti

F = F + 1;

Anche una Coda, comunque, può essere implementata attraverso le liste concatenate, in modo da

risolvere il problema di dover stabilire a priori il numero massimo di elementi inservibili nella coda

stessa.

Il front della coda, in questo caso, coinciderà con la testa della lista, mentre il rear coinciderà con la

coda della lista.

Per mantenere un riferimento alla posizione della testa e delle coda della lista si fa uso di due

puntatori head e tail.

Una Coda può anche essere memorizzata in un anello, con un puntatore all’ultimo elemento in

modo che in un solo passo si possa accedere alla testa.

Coda con Priorità

Una Coda con Priorità è un tipo di coda i cui elementi hanno associato un valore, detto priorità, in

base al quale sono vincolate le estrazioni.

Elementi con priorità maggiore vengono estratti per primi, mentre elementi con pari priorità

vengono estratti secondo il loro ordine di inserimento nella coda.

Si basa sul principio del “largest in first out”, LIFO, ossia che il primo elemento ad essere estratto è

quello ad avere priorità più alta. Operazioni su una Pila

construct Operazione di costruzione di una coda con priorità a partire da n dati.

Può essere realizzata da una serie di n insert.

insert Operazione di inserimento.

remove Operazione di estrazione.

replace Operazione di sostituzione dell’elemento con priorità maggiore con un elemento

qualsiasi.

Può essere realizzata combinando insert e remove.

change Operazione di modifica della priorità di un elemento.

Può essere realizzata combinando delete e insert.

delete Operazione di cancellazione di un elemento specifico.

join Operazione di fusione di due code con priorità.

L’implementazione più semplice di una coda con priorità è quella attraverso un vettore, che può

essere disordinato od ordinato in base alla priorità dei suoi elementi.

Di seguito sono illustrati gli algoritmi di inserimento ed estrazione in una coda con priorità Q,

implementata con un vettore disordinato, usando un contatore m per tenere memorizzata la

posizione dell’ultimo elemento inserito.

x x x x x

0 1 2 m n-1

Operazione di inserimento: insert(e) Costo Algoritmo

se m = n

allora overflow;

altrimenti O(1)

Q[m] = e;

m = m + 1;

Operazione di estrazione: remove() Costo Algoritmo

se m = 0

allora underflow;

altrimenti

max = 0;

per j = 1, …, n-1 O(m)

se Q[j] > Q[max]

allora max = j;

restituisci Q[max];

m = m - 1;

Q[max] = Q[m];

Di seguito sono, invece, illustrati gli algoritmi di inserimento ed estrazione in una coda con priorità

Q, implementata con un vettore ordinato in base alla priorità dei suoi elementi, usando un

contatore m per tenere memorizzata la posizione dell’ultimo elemento inserito.

Operazione di inserimento: insert(e) Costo Algoritmo

se m = n

allora overflow;

altrimenti

j = m - 1;

finché j ≥ 0 e Q[j] > e O(m)

Q[j+1] = Q[j];

j = j - 1;

Q[j+1] = e;

m = m + 1;

Operazione di estrazione: remove() Costo Algoritmo

se m = 0

allora underflow;

altrimenti O(1)

restituisci Q[m-1];

m = m - 1; Inserimento Cancellazione

Vettore Disordinato O(1) O(m)

Vettore Ordinato O(m) O(1)

Heap

Lo Heap è una struttura dati rappresentata da un vettore, occupato a partire dalla posizione di

indice 1, che soddisfa la condizione di heap.

La condizione di heap dice che per ogni j, 1 ≤ j ≤ n/2, la chiave in posizione j deve essere maggiore

delle due chiavi in posizione 2j e 2j+1.

L’elemento in posizione j viene chiamato padre, dei due figli rappresentati dagli elementi in

posizione 2j e 2j+1.

Uno Heap è dunque un vettore non completamente ordinato, in cui però la chiave più grande di

tutte si trova sempre nella prima posizione del vettore.

Se una coda con priorità venisse implementata attraverso uno Heap, tutte le sue operazioni

verrebbero eseguite in tempo logaritmico.

Questo accade poiché in uno Heap contenente m elementi, ogni volta che si passa dal padre ai

figli si raddoppia l’indice dell’elemento; partendo dall’elemento di indice 1 si può al massimo

raddoppiare log m volte, dopodiché si raggiunge la fine dello heap.

2

Allo stesso modo, partendo dall’elemento di indice m e saltando verso il padre si dimezza m e

questo può ripetersi al massimo log m volte, dopodiché si è raggiunta la cima dello heap.

2

In uno Heap, gli algoritmi agiscono apportando semplici modifiche strutturali, che però spesso

portano a violare la condizione di heap, ma in un secondo momento lavorano a ripristinare questa

condizione.

Alcuni algoritmi operano dalla cima verso il fondo dello heap, altri dal fondo verso la cima.

Di seguito sono descritte le operazioni di inserimento e di estrazione in uno heap H, di dimensione

n, con m dati già inseriti in esso.

Operazione di inserimento: insert(e) Costo Algoritmo

se m ≤ n-1 O(log m)

2

allora m = m + 1;

H[m] = e; Nell’operazione di inserimento, l’elemento e viene

upheap(m); inserito nella prima posizione libera dopo l’ultimo

altrimenti elemento nel vettore.

overflow;

upheap(k) Nell’algoritmo di inserimento insert(e) viene

temp = H[k]; richiamato il metodo upheap(k), che è responsabile

H[0] = +∞; del ripristino della condizione di heap, muovendosi

finché H[K/2] ≤ temp dal fondo verso la cima del vettore.

H[k] = H[k/2] Viene confrontato il padre dell’elemento inserito con

k = k/2; l’elemento e se esso risulta essere minore, essi

H[k] = temp; vengono sostituiti di posizione.

Operazione di estrazione: remove() Costo Algoritmo

se m > 0 O(log m)

2

restituisci H[1];

H[1] = H[m]; Nell’operazione di estrazione, viene restituito

m = m - 1; l’elemento in posizione 1 del vettore e,

downheap(1); successivamente, in quella posizione, viene inserito

altrimenti l’ultimo elemento presente nel vettore.

underflow; Infine, viene ripristinata la condizione di heap.

downheap(k)

temp = H[k]; Nell’algoritmo di estrazione remove() viene

finché k ≤ m/2 richiamato il metodo downheap(k), che è

j = 2·k; responsabile del ripristino della condizione di heap,

se (j < m) e (H[j] < H[j+1]) muovendosi dalla cima verso il fondo del vettore.

allora j = j + 1; Viene confrontato l’elemento in posizione k con i

se temp < H[j] suoi figli, se uno dei due risulta maggiore del padre,

allora H[k] = H[j]; quest’ultimo viene sostituito dal figlio maggiore.

k = j;

H[k] = temp;

Alberi

Gli Alberi sono delle strutture dati bidimensionali, consentono di rappresentare relazioni 1:n.

Esistono diversi tipi di alberi, tra i quali troviamo in ordine decrescente di generalità:

- Alberi (o Alberi Liberi)

- Alberi con Radice

- Alberi Ordinati

- Alberi m-ari (e Alberi Binari)

Un Albero T è una coppia di insiemi T = (N, A), dove V è l’insieme dei nodi (o vertici) ed A è

l’insieme degli archi (o rami) che collegano i nodi.

L’insieme A = { (x,y) | x,y N } è un insieme di coppie di elementi di N, detti archi, tali che per ogni

∈

coppia di nodi dell’albero esiste uno ed uno solo cammino che li unisce.

Un nodo (o vertice) è un oggetto contenente un’informazione.

Un arco (o ramo) è una connessione tra due nodi e, quindi, esprime una relazione tra i due.

Un cammino in un albero è una sequenza di nodi (v , v , …, v ), solitamente indicata dal simbolo π.

0 1 k

Quindi, ad esempio, il cammino da x ad y risulta essere π = (v , v , …, v ), con v = x e v = y, tali

0 1 k 0 k

∀

che (v , v ) A i = 1, …, k-1.

∈

i i+1

Si definisce lunghezza del cammino il numero di archi che lo compongono: l(π) = k.

Se alcune coppie di nodi sono unite da più cammini o non sono unite da alcun cammino, la

struttura non risulterà essere un albero, ma un grafo.

Un insieme disgiunto di alberi viene detto foresta.

Un albero con radice è un albero in cui un nodo viene scelto come radice dell’albero.

In questo modo esiste un elemento che non dipende da nessun altro ed ogni altro elemento

dipende da uno ed uno solo elemento.

In un albero con radice, ogni nodo è radice di un sottoalbero costituito dal nodo stesso e dai nodi

sotto di esso.

Ciascun nodo, esclusa la radice, ha esattamente un nodo al di sopra, detto padre, mentre i nodi al

di sotto vengono detti figli.

I nodi senza figli sono detti foglie.

Un albero ordinato è un albero con radice, in cui è significativo l’ordine con cui compaiono i figli di

ciascun nodo.

Un albero m-ario è un albero ordinato, in cui ogni nodo ha uno specifico numero m di figli (detto

arietà dell’albero).

Alberi Binari

Il più semplice albero m-ario è l’albero binario.

Un albero binario è un albero ordinato, formato da due tipi di nodi: i nodi esterni, che non hanno

figli, e i nodi interni, che hanno esattamente due figli, che, essendo ordinati, vengono chiamati figlio

sinistro e figlio destro.

La rappresentazione di un albero binario maggiormente usata è quella attraverso una struttura

concatenata con due puntatori per ogni nodo interno, dove il puntatore sinistro punta alla radice del

sottoalbero sinistro, mentre il puntatore destro punta al sottoalbero destro.

Per ogni albero ordinato esiste un albero binario corrispondente.

Per passare dall’albero ordinato all’albero binario viene seguita la rappresentazione in cui come

figlio sinistro dell’albero binario verrà scelto il primo figlio di un nodo dell’albero ordinato, mentre

come figlio destro il primo fratello.

PROPRIETÀ DEGLI ALBERI BINARI:

Un albero binario con n nodi interni ha n+1 nodi esterni.

• Il livello della radice è zero, il livello di ogni altro nodo è il livello del padre più uno.

• L’altezza di un albero è il massimo livello dei suoi nodi.

• La lunghezza di un cammino è il numero di archi di cui è composto il cammino.

• La lunghezza del cammino interno di un albero binario, è la somma delle lunghezze dei cammini

• che collegano la radice a tutti i nodi interni, cioè la somma dei livelli di tutti i nodi interni

dell’albero: ogni livello viene moltiplicato per quanti nodi contiene e la somma di tutti dà il

cammino interno.

Allo stesso modo, la lunghezza del cammino esterno di un albero binario è la somma delle

lunghezze dei cammini che collegano la radice a tutti i nodi esterni, cioè la somma dei livelli di

tutti i nodi esterni dell’alberi.

Considerando un albero binario con n nodi interni (e, quindi, n+1 nodi esterni), ed indicando con

• I la lunghezza del cammino interno e con E la lunghezza del cammino esterno, esiste la

n n

seguente relazione: E = I + 2n.

n n

Considerando un albero binario di altezza h con n nodi interni:

• Considerando un albero binario con n nodi interni:

• Un albero binario, se degenera in una lista, avrà altezza n, ossia il numero dei suoi nodi interi.

•

Attraversamento degli Alberi

Esistono due criteri di attraversamento per gli alberi ordinati: l’attraversamento anticipato e

l’attraversamento posticipato.

Per gli alberi binari, esiste anche l’attraversamento simmetrico.

Attraversamento Anticipato: attraversa(R) Descrizione

visita(R); L’attraversamento anticipato consiste nel visitare la

attraversa(left(R)); radice R e poi nell’attraversare in ordine anticipato

attraversa(right(R)); tutti i suoi sottoalberi, da sinistra a destra.

Attraversamento Posticipato: attraversa(R) Descrizione

attraversa(left(R)); L’attraversamento posticipato consiste

attraversa(right(R)); nell’attraversare in ordine posticipato tutti i

visita(R); sottoalberi, da sinistra a destra, ed infine visitare la

radice R.

Attraversamento Posticipato: attraversa(R) Descrizione

L’attraversamento simmetrico consiste

attraversa(left(R)); nell’attraversare in ordine simmetrico il sottoalbero

visita(R); sinistro, poi visitare la radice R e, quindi,

attraversa(right(R)); attraversare in ordine simmetrico il sottoalbero

destro.

Di seguito, viene illustrata l’implementazione dell’attraversamento anticipato di un albero con

radice R attraverso una pila astratta.

Attraversamento Anticipato: attraversa(R)

attraversa(R)

push(tree(R));

finchè(!empty())

x = pop();

se x = node(y) allora visita(y) attraversamento posticipato

se x = tree(y) allora push(tree(right(Y)))

push(tree(left(y)))

push(node(y)) attraversamento simmetrico

Di seguito sono illustrati alcuni esempi di attraversamento di alberi:

• ESEMPIO 1 (CON PILA ASTRATTA):

A

B C Attraversamento Anticipato: A B D C E F

D E F

node(A) node(B)

tree(B) tree(D) node(N) node(C) node(E)

tree(A) tree(C) tree(C) tree(C) tree(E) tree(F) node(E)

• ESEMPIO 2 (CON TRASFORMAZIONE IN AB):

Attraversamenti:

- Anticipato: A B E H F I J K C D G

- Posticipato: H K J I F E G D C B A

- Simmetrico: H E I J K F B C G D A

Alberi Binari di Ricerca

Un Albero Binario di Ricerca (ABR) è un albero binario che ha una chiave associata ad ogni suo

nodo e soddisfa la seguente proprietà: per ogni suo nodo, la chiave in esso memorizzata è

maggiore di tutte le chiavi memorizzare nei nodi del suo sottoalbero sinistro e minore di tutte le

chiavi memorizzate nei nodi del suo sottoalbero destro.

K

≤K ≥K

Le operazioni effettuabili su un albero binario di ricerca sono di carattere locale, come la ricerca di

un nodo, l’inserimento, la cancellazione, o di carattere globale, come l’ordinamento.

L’inserimento di un nodo avviene dopo aver ricercato la posizione che gli compete nell’albero,

ovvero confrontando inizialmente il nodo con la radice e poi proseguendo nel sottoalbero sinistro o

destro a seconda del valore della chiave del nodo.

Se la ricerca termina con successo, significa che il nodo è già presente nell’albero, altrimenti si

raggiunge un nodo il cui sottoalbero sinistro o destro è vuoto e, quindi, si può inserire il nodo come

figlio sinistro o destro del nodo.

La cancellazione di un nodo è, invece, più complessa: se il nodo da cancellare è una foglia, il

problema è banale.

Se, invece, il nodo da cancellare ha un sottoalbero destro o sinistro vuoto, basta, una volta

cancellato, sostituirlo con la radice del suo sottoalbero.

Se, però, il nodo da cancellare ha entrambi i sottoalberi non vuoti, per mantenere l’ordinamento è

necessario sostituirlo con il valore immediatamente successivo, che si trova come elemento più a

sinistra del sottoalbero destro del nodo da cancellare.

Per quanto riguarda l’ordinamento delle chiavi memorizzate in un ABR, è sufficiente elencare gli

elementi secondo l’attraversamento simmetrico per ottenerne l’ordine preciso.

Ogni albero binario di ricerca può essere costruito a partire dalle n! possibili permutazioni delle n

chiavi.

La complessità della ricerca in un ABR è strettamente legata alla forma dell’albero: se l’albero è

completo, ci saranno circa log n nodi in ogni cammino dalla radice ad un nodo esterno, ma se

2

l’albero degenera in una lista, si può avere anche un cammino di lunghezza n.

L’altezza di un ABR equivale al costo della ricerca nel caso pessimo, mentre la lunghezza del

cammino interno e di quello esterno sono correlate al costo medio, rispettivamente, della ricerca

con successo e senza successo.

Le operazioni di ricerca con successo, inserimento e ricerca senza successo in un ABR hanno un

costo medio di 2lnn ≈ 1.39log n.

2

Il costo medio per l’inserimento di una chiave è pari a .

Infatti il numero medio dei confronti fatti per inserire una chiave n si trova dividendo la lunghezza

media del cammino interno dell’albero per il numero totale dei suoi nodi.

Il costo medio per la ricerca con successo è pari a .

Infatti, il costo per la ricerca con successo di una chiave è uguale al costo per il suo inserimento,

più il confronto con se stessa.

Il costo medio per la ricerca senza successo è pari a .

Infatti il costo di una ricerca senza successo è pari alla lunghezza del cammino esteso, diviso il

numero n + 1 dei nodi esterni.

Ma, essendo E = I + 2n, dunque, si ha il risultato indicato.

n n

Le n! permutazioni di n chiavi generalo solo alberi binari distinti.

Alberi 2-3

Gli Alberi 2-3 sono dei particolari alberi binari, con la particolarità che crescono dalla parte della

radice e mantengono le foglie tutte sullo stesso livello.

Un Albero 2-3 è composto da nodi 2-3.

Un Nodo 2-3 è un insieme ordinato contenente due chiavi k e k , in ordine crescente, e tre

1 2

puntatori p , p e p , tali che:

0 1 2

p punta al sottoalbero contenente chiavi k tali che k < k .

• 0 1

p punta al sottoalbero contenente chiavi k tali che k < k < k .

• 1 1 2

p punta al sottoalbero contenente chiavi k tali che k > k .

• 2 2

k k

1 2

p p p

0 1 2

k < k k > k

k < k < k

1 2

1 2

Inoltre, gli Alberi 2-3 verificano le seguenti proprietà:

le foglie sono tutte sullo stesso livello;

• ogni nodo ha al più tre figli.

•

La ricerca di una chiave k in un Albero 2-3 avviene confrontando la chiave da ricercare con il

contenuto di un nodo a partire dalla radice.

In questo caso, però, in ciascun nodo ci possono essere due chiavi ed e dunque necessario

eseguire una successione di confronti:

se k < k , allora la ricerca prosegue nel sottoalbero indicato da p ;

• 1 0

se k = k , allora la ricerca termina con successo;

• 1

se nel nodo c’è una sola chiave, la ricerca prosegue nel sottoalbero indicato da p .

• 1

Invece, se nel nodo ci sono due chiavi, è necessario eseguire ulteriori confronti;

se k < k < k , allora la ricerca prosegue nel sottoalbero indicato da p .

• 1 2 1

se k = k , allora la ricerca termina con successo;

• 2

se k > k , allora la ricerca prosegue nel sottoalbero indicato da p .

• 2 2

L’inserimento di una nuova chiave avviene dopo aver eseguito una ricerca senza successo, ossia

una ricerca che si arresta su un nodo dal quale dovrebbe proseguire tramite un puntatore vuoto.

Le azioni successive dipendono dal nodo di arresto: se contiene una sola chiave, la nuova chiave

viene inserita nel nodo stesso, ordinata con quella precedente.

Se, invece, il nodo contiene già due chiavi, si considera l’insieme ordinato (k , k , k ) costituito

1 2 3

dalle due chiavi del nodo e dalla nuova chiave.

Il nodo di arresto viene suddiviso in due nodi contenenti rispettivamente k e k , mentre k viene

1 3 2

inserito nel padre del nodo di arresto, assieme ai due puntatori ai nodi contenenti k e k .

1 3

Questa operazione può ripetersi a ritroso fino alla radice e, nel caso in cui sia necessario

suddividere anche la radice, l’altezza dell’albero viene incrementata di una unità.

La cancellazione è un’operazione piuttosto complessa e consiste nel ricompattare gli eventuali

nodi interessati.

Spesso si preferisce effettuare una cancellazione logica delle chiavi, che risulta essere meno

complessa.

Questa consiste nell’associare ad ogni chiave un indicatore che vale 0 per tutti gli elementi

effettivamente presenti nell’albero e 1 per quelli cancellati.

In questo modo, cancellare una chiave significa mettere a 1 il suo indicatore, senza apportare

modifiche all’albero.

L’altezza h di un Albero 2-3 con n è così limitata: log (n+1) ≤ h ≤ log (n+1).

3 2

Dimostrazione:

Il numero minimo di chiavi presenti in un Albero 2-3 di altezza h corrisponde al caso in cui ogni nodo contiene una sola

chiave e, dunque, ha solo due figli. 2 h-1 h-1

Perciò, indicato con n il numero di chiavi dell’albero, risulta: n ≥ 1+2+2 +…+2 = 2 .

Il numero massimo di chiavi, invece, lo si ha quando in ogni nodo ci sono due chiavi e, dunque, ogni nodo ha tre figli,

2 h-1 2 h-1 h

perciò: n ≤ 2+2·3+2·3 +…+2·3 = 2(1+1·3+1·3 +…+1·3 ) = = 3 - 1.

Passando ai logaritmi, si ottiene il risultato sopracitato.

L’altezza dell’albero costituisce una limitazione superiore al costo delle operazioni di ricerca, di

inserimento e di cancellazione fisica.

Ad esempio, la complessità massimo della ricerca è cerca 1.5log (n+1).

2

Di seguito sono illustrati alcuni esempi di attraversamento di alberi:

• ESEMPIO 1: 5 11 27 42 1 14 33 7 3 89 40 12

5 — 11 — 27 14 — 27 — 42

5 11 11 11

5 27 42 1 5 27 42

1 — 5 — 7

11 27 11 27

1 5 14 42 1 5 14 33 42 33 — 24 — 39

11

5 27

1 3 7 14 33 42

11

5 27 42

1 3 7 14 33 89

11

5 27 42

1 3 7 12 14 33 40 89

• ESEMPIO 2: 10 30 20 35 25 27 22

10 — 20 — 30 25 — 30 — 35

10 30 20 20 30

10 30 35 10 25 27 35

22 — 25 — 27 25

20 30

10 22 27 35

• ESEMPIO 3: 70 76 37 82 29 56 42 47 21 41 85 35

37 — 70 — 76

70 76 70 70

37 76 82 29 37 76 82

29 — 37 — 56 37 70 37 70 42 — 47 — 56

29 56 76 82 29 42 56 76 82

47 47

37 70 37 70

29 42 56 76 82 21 19 41 42 56 76 82

76 — 82 — 85 21 — 29 — 35

47

37 70 82

21 29 41 42 56 76 85

47

29 70 82

37

21 41 42 56 76 85

35

Alberi Bilanciati (o AVL)

Un Albero Bilanciato (o AVL) è un albero di ricerca, i cui nodi hanno fattori di bilanciamento 0, 1

oppure -1.

Per fattore di bilanciamento di un nodo si intende la differenza tra l’altezza del suo sottoalbero

destro e l’altezza del suo sottoalbero sinistro.

Le operazioni di inserimento e cancellazione possono portare allo sbilanciamento dell’albero e,

quindi, devono essere accompagnate da alcune operazioni che consentano di ripristinare la

proprietà degli alberi AVL.

Le operazioni che ripristinano le proprietà di bilanciamento sono dette rotazioni.

Le rotazioni sono di due tipi: semplici (a destra o a sinistra), oppure doppie (a destra o a sinistra).

Di seguito sono illustrate le rotazioni in dei casi basilari, molto semplici.

Rotazione semplice a destra:

• -1 -2

A A A

0 -1 0

B B B

0 0

0

C A

C

Situazione iniziale: Inserimento a Rotazione semplice

l’albero è bilanciato sinistra nel a destra per

sottoalbero sinistro ribilanciare l’albero

Rotazione doppia a destra:

• 0

-1 -2 C

A A 0

0

0 +1 B A

B

B 0 C

C

Situazione iniziale: Inserimento a destra Rotazione doppia a

l’albero è bilanciato nel sottoalbero destra per

sinistro ribilanciare l’albero

Rotazione semplice a sinistra:

• +1 +2

A A A

0 0 0

B B B

0 0 0

C A C

Situazione iniziale: Inserimento a destra Rotazione semplice

l’albero è bilanciato nel sottoalbero a sinistra per

destro ribilanciare l’albero

Rotazione doppia a sinistra:

• 0

+1 +2 C

A A 0

0

0 -1 A B

B B

0 C

C

Situazione iniziale: Inserimento a Rotazione doppia a

l’albero è bilanciato sinistra nel sinistra per

sottoalbero destro ribilanciare l’albero

Lo sbilanciamento può, però, verificarsi in altri casi più complessi e non unicamente alla radice

dell'albero, ma anche alle radici dei suoi sottoalberi.

Di seguito sono mostrate le rotazioni in dei casi più generici.

Rotazione semplice a destra:

• -1 -2 0

A A B 0

0 -1 A

B B

h h h+1

S S

3 3 S

1

h h

h h h+1 h S

S S S S S 3

1 2 1 2 2

Situazione iniziale: l’albero Inserimento di e Rotazione semplice a destra

è bilanciato seguente sbilanciamento per ribilanciare l’albero

Rotazione doppia a destra:

• -1 -2

A A

0 +1

B B

h h

S S

2 2

0 -1

C C

h h

S S

1 1

h-1 h h-1

S S S S

3 4 3 4

Situazione iniziale: l’albero è Inserimento di e seguente

bilanciato sbilanciamento

0

C

0 1

B A

h h h-1 h

S

S S S

3

1 4 2

Rotazione doppia a destra per

ribilanciare l’albero

Rotazione semplice a sinistra:

• 1 2 0

A A B

0 0 0

B B A h+1

h h S

3

S S

1 1

h h h h+1 h h

S S

S S S S

2 2

3 3 1 2

Inserimento di e Rotazione semplice a sinistra

Situazione iniziale: l’albero seguente sbilanciamento per ribilanciare l’albero

è bilanciato

Doppia rotazione a sinistra:

• 1 2

A A

0 0

B B

h h

S S

1 1

0 0

C C

h h

S S

4 4

h

h-1 h-1

S S S S

2 3 2 3

Situazione iniziale: l’albero è Inserimento di e seguente

bilanciato sbilanciamento

0

C

0 1

A B

h h h-1 h

S S S S

1 2 3 4

Rotazione doppia a sinistra per

ribilanciare l’albero

• ESEMPIO 1: 37 70 76 29 56 42 21 25

• ESEMPIO 2: 1 2 3 4 5 6 7

• ESEMPIO 3: 5 20 13 70 56 43 9 3

Alberi di Ricerca Digitale (chiavi binarie)

Gli Alberi di Ricerca Digitale sono una struttura identica agli alberi binari (anche l’algoritmo di

ricerca è lo stesso), ad eccezione del fatto che la scelta di proseguire nel sottoalbero destro o

sinistro non è fatta in base al risultato del confronto tra chiavi, ma in base al valore di un

determinato bit della chiave da ricercare.

Inizialmente viene esaminato il bit più significativo: si prosegue nel sottoalbero sinistro se il bit vale

0, nel sottoalbero destro se il bit vale 1.

Si prosegue allo stesso modo su tutti gli altri bit della sequenza, finché non si trova la chiave,

oppure finché non si raggiunge un nodo esterno.

Il codice di ricerca è, quindi, lo stesso che vale per gli alberi binari, con la sola differenza che i

confronti fra chiavi sono sostituiti dalla chiamata della funzione bit(x, k), che restituisce il k-esimo

bit da destra della sequenza di bit x.

Ad esempio, data la tabella rappresentante una codifica delle chiavi con codici a 5 bit, dopo tutti gli

inserimenti si ottiene il seguente albero di ricerca digitale:

bit 4 3 2 1 0

1 0 1 0 1

U 0 1 1 1 0

N

E 0 0 1 0 1

S 1 0 0 1 1

0 1 1 0 1

M 1 0 0 0 0

P

I 0 1 0 0 1

O 0 1 1 1 1

0 0 1 0 0

D 1 0 0 1 1

R

C 0 0 0 1 1

A 0 0 0 0 1

L’inserimento avviene ricercando il nodo da inserire, finché non si raggiunge un nodo esterno.

A quel punto viene inserito il nodo.

In un Albero Digitale costruito con n chiavi, ciascuna di b bit, presenta i seguenti costi per le

operazioni di ricerca, inserimento e cancellazione di un elemento:

caso pessimo: b confronti.

• Infatti nessun cammino sarà più lungo del numero di bit di cui sono composte le chiavi.

caso medio: log n.

• 2

In generale, gli alberi digitali sono quasi bilanciati, visto che il successivo bit di una chiave

casuale ha uguale probabilità di essere 0 o 1.

Trie

Un Trie è un albero binario che ha una chiave associata a ciascuno dei suoi nodi esterni.

Risulta essere composto da due tipi di nodi: quelli interni, che contengono solo puntatori, e quelli

esterni, che contengono solo chiavi.

• Il Trie associato ad un insieme vuoto di chiavi è un albero vuoto.

• Il Trie associato ad una sola chiave è un nodo esterno contenente la chiave.

• Il Trie associato ad un insieme di chiavi di cardinalità maggiore di uno è un nodo interno, con

puntatore sinistro che punta al Trie associato alle chiavi il cui bit iniziale è 0 ed un puntatore

destro che punta al Trie associato alle chiavi il cui bit iniziale è 1.

La ricerca di un dato avviene attraversando l’albero in base al bit della chiave di ricerca, senza

però effettuare confronti finché non viene raggiunto un nodo esterno.

A questo punto viene effettuato il confronto della chiave di ricerca con la chiave del nodo e viene,

quindi, determinato il successo o il fallimento della ricerca.

L’inserimento di una nuova chiave prevede di fare una ricerca senza successo:

se il nodo esterno di arresto è vuoto, la nuova chiave viene inserita nello stesso nodo di

• arresto;

se il nodo d’arresto contiene già una chiave, esso viene sostituito da un nodo interno (o da più

• nodi interni, in base a quanti sono i bit che coincidono nella chiave cercata con quelli della

chiave d’arresto della ricerca) e dai nodi esterni vuoti in cui terminano i rami di ricerca senza

successo.

I costi di ricerca e di inserimento nei Trie sono analoghi a quelli degli alberi digitali di ricerca.

Per ogni insieme di chiavi esiste un unico Trie, infatti la sua struttura è indipendente dall’ordine di

inserimento delle chiavi.

Inoltre, a differenza di quello che accade negli alberi di ricerca digitale, le chiavi nei Trie appaiono

in ordine, leggendo le foglie da destra a sinistra.

4 3 2 1 0

bit

U 1 0 1 0 1

N 0 1 1 1 0

0 0 1 0 1

E 1 0 0 1 1

S

M 0 1 1 0 1

P 1 0 0 0 0

0 1 0 0 1

I 0 1 1 1 1

O

D 0 0 1 0 0

R 1 0 0 1 1

0 0 0 1 1

C 0 0 0 0 1

A

Alberi Digitali a Più Vie

Gli Alberi Digitali a Più Vie sono un modo per accorciare i cammini di un Trie, dato che una

caratteristica negativa di questi è rappresentata dai lunghi cammini in comune che possono avere

chiavi che hanno un prefisso molto lungo di bit uguali.

Chiavi che differiscono solo nell’ultimo bit, producono un

cammino lungo quanto la lunghezza delle chiavi stesse, anche

se loro fossero le due sole chiavi dell’albero, come in figura.

bit 5 4 3 2 1 0

1 0 1 0 1 0

U

N 0 1 1 1 0 0

E 0 0 1 0 1 0

1 0 0 1 1 0

S 0 1 1 0 1 0

M

P 1 0 0 0 0 0

I 0 1 0 0 1 0

0 1 1 1 1 0

O 0 0 1 0 0 0

D

R 1 0 0 1 1 0

C 0 0 0 1 1 0

0 0 0 0 1 0

A

Ricerca Casuale

La Ricerca Casuale è una tecnica di ricerca non basata sui confronti, che ha costo di ricerca

costante, indipendente dal numero di dati su cui viene effettuata la ricerca.

Questi metodi sono basati su trasformazioni delle chiavi in indirizzi e si basano sulla seguente

idea: date delle chiavi intere, distinte e comprese tra 1 e N, allora potremmo memorizzare il dato di

chiave i nella posizione i-esima di una tabella, rendendo l’accesso ai dati immediato.

I metodi Hash sono una generalizzazione di queste situazione, visto che le chiavi non soddisfano

sempre tali ottime proprietà.

Un metodo di ricerca Hash consiste nel calcolare una funzione hash che trasforma la chiave di

ricerca in un indirizzo di tabella in cui sono memorizzati i dati.

→

Questa funzione h è tale che h : K [0, …, m-1], dove K è l’insieme delle chiavi e ‘0, …, m-1’

sono gli indirizzi delle posizioni della tabella.

Idealmente a chiavi diverse k ≠ k dovrebbero corrispondere a due indirizzi differenti h(k ) ≠ h(k ),

1 2 1 2

purtroppo però, difficilmente, una funzione hash è invettiva e, quindi, due o più chiavi possono

produrre lo stesso indirizzo.

Quando per k ≠ k si ha h(k ) ≠ h(k ), si dice che si è verificata una collisione e che k e k sono

1 2 1 2 1 2

sinonimi.

Avendo una funzione hash h ed un metodo M per la risoluzione delle collisioni, la ricerca di una

chiave k funziona così:

si calcola h(k) e si controlla l’elemento in quella posizione;

1. se esso ha chiave k, la ricerca si conclude con successo.

2. In caso contrario, non si può sapere se k non è presente nella tabella, oppure, se al

momento di inserire k si era verificata una collusione e, dunque, k è stato posto in un’altra

posizione della tabella;

si applica a k il metodo M e, o si trova k, oppure si conclude che k non è presente.

3.

Se h è una buona funzione e produce poche collisioni, in un solo passo e con un solo confronto si

riesce ad accedere alla maggior parte dei dati.

In caso di collisioni, se M è un buon metodo, il numero di accessi è estremamente ridotto e,

dunque, il tempo complessivo di ricerca è quasi costante.

Le Funzioni Hash

Una funzione Hash deve trasformare chiavi (interi, stringhe) in interi compresi tra 0 e m-1, dove m

è il numero di elementi della tabella.

Una buona funzione hash ha le seguenti proprietà:

deve essere facile da calcolare, per non appesantire le operazioni ulteriori alla ricerca;

1. deve generare valori distribuiti uniformemente nell’intervallo [0, …, m-1].

2.

Una funzione Hash invettiva da K a [0, …, m-1] si dice perfetta.

Per insiemi di chiavi di tipo numerico, le funzioni hash più semplici sono del tipo h(k) = k mod m,

dove [0, …, m-1] è l’intervallo di distribuzione.

Per chiavi alfabetiche è necessario vi sia una regola di trasformazione in valori numerici.

Metodi per la risoluzione delle collisioni

I metodi di risoluzione delle collisioni possono essere suddivisi in due categorie: quelli che

sfruttano strutture concatenate per memorizzare i sinonimi e quelli che calcolano nuovi indirizzi.

Catene Separate: questo metodo di risoluzione di collisioni organizza la tabella in modo che i

• suoi elementi contengano solo puntatori a catene: in ciascuna catena vengono inseriti tutti i dati

tra di loro sinonimi, quindi quelli per i quali la funzione hash ha calcolato come indirizzo la

posizione della tabella contenente il puntatore alla testa della catena.

L’inserimento di una nuova chiave k avviene calcolando h(k) e inserendo k nella catena indicata

dal puntatore che si trova nella posizione h(k) della tabella.

La ricerca avviene in modo simile, accedendo ad una catena tramite il valore della funzione

hash e, poi, scorrendola sequenzialmente.

Questo è l’unico caso di tabella hash in cui è possibile memorizzare un numero n di elementi

maggiore della lunghezza m della tabella.

Esempio:

h(k) = (k mod 11) 1 19 5 12 18 3 8 9 14 7 16 24 23 13 27 34 38

0 34

1 12 23

1 1 13

2 3 14

3

4 38

5 16 27

5

6 18 7

7 19 8

8

9 9

10

Catene Unite: ogni elemento della tabella è formato da due campi, uno contenente la chiave e

• l’altro un indice.

Ogni elemento viene inserito nella posizione che gli spetta secondo il valore della funzione hash

se essa risulta essere libera e viene posto l’indice a -1.

Se, invece, si dovesse verificare una collisione, la chiave k viene inserita nella prima posizione

(successiva alla posizione h(k)) della tabella e l’indice della h(k) assume il valore di questa

posizione, ossia indica la posizione di un sinonimo della chiave presente in h(k).

Ha il vincolo n ≤ m, dove n è il numero di chiavi ed m la dimensione della tabella.

Esempio:

h(k) = (k mod 11) 1 19 5 12 18 3 8 23 14 7 17

Chiave Indice

0 14 -1

1 1 2

2 12 4

3 3 0

4 23 -1

5 5 -1

6 17 -1

7 18 10

8 19 9

9 8 -1

10 7 -1

Indirizzamento Aperto (o Hash Lineare): simile al metodo delle catene unite, nell’Hash Lineare

• però vengono soppressi gli indici e viene scelto di effettuare la ricerca dei sinonimi di una chiave

k in modo sequenziale, partendo dalla posizione h(k).

Questo metodo aumenta il numero di confronti necessari per la ricerca, ma risparmia lo spazio

necessario alla memorizzazione degli indici.

La ricerca termina senza successo solo quando viene trovata una posizione vuota nella tabella.

Il costo della ricerca dipende dal rapporto n/m, detto fattore di caricamento della tabella.

Algoritmo di Inserimento L’inserimento di una chiave k nella tabella v[0, …,

x = h(k); m-1] viene realizzato attraverso un ciclo, in cui viene

finché v[x] != -1 supposto che gli elementi vuoti di v abbiamo valore

x = (x+1) % m; -1.

v[x] = k; La tabella viene considerata circolare.

Il valore della posizione in cui viene inserita la chiave k dipende dal valore calcolato dalla funzione

hash h (k), ma anche dal numero di passi che serve fare prima di inserire k nella tabella.

0

Viene indicata con h (k) la posizione esaminata al passo i-esimo, dove h (k) = (h (k) + i) mod m.

i i 0

Quando le collisioni vengono risolte con l’Hash Lineare, il numero di tentativi richiesti per ricercare

un elemento in un tabella hash di dimensione m che contiene n = αm chiavi è:

per ricerche con successo.

per ricerche senza successo.

Il valore viene detto fattore di caricamento della tabella, poiché indica il rapporto fra il

numero di posizioni occupate della tabella stessa e il numero di posizioni totali.

Tanto più è basso il fattore di caricamento della tabella, tanto migliori saranno le prestazioni del

metodo hash.

L’Hash Lineare presenta però due inconvenienti:

se per due chiavi distinte k e k si ha h (k ) = h (k ), allora anche h (k ) = h (k ) per ogni

1. 1 2 0 1 0 2 i 1 i 2

valore di i, ovvero la ricerca di due sinonimi procede esaminando sempre le stesse

posizioni.

Questo fenomeno viene detto agglomerazione primaria.

se anche due chiavi non sono sinonimi, si può verificare che h (k ) = h (k ) per un certo i ≠ j.

2. i 1 j 2

Anche in questo caso, i passi successivi per la ricerca delle due chiavi coincidono, quindi

h (k ) = h (k ) per ogni valore di r > 0.

i+r 1 j+r 2

Questo fenomeno viene detto agglomerazione secondaria.

Questi due fenomeni di aggregazione significano che ci vogliono molti confronti per trovare sia k

1

che k .

2

Tanto più grande è un gruppo di chiavi, tanto maggiore è la possibilità che esso cresca

ulteriormente, provocando un deterioramento delle prestazioni della tabella per le operazioni di

inserimento e ricerca.

Per risolvere questi problemi sono state introdotte alcune tecniche, come:

Hash Casuale:

• h (k) = (h (k) + r ) mod m

i 0 i

Dove r sono numeri casuali dipendenti solo da i.

i

Risolve solo l’agglomerazione secondaria.

Hash Doppio:

• ’ ’’

h (k) = (h (k) + ih (k)) mod m

i ’ ’’

Risolve sia l’agglomerazione primaria che l’agglomerazione secondaria, purché h e h siano

scelte in modo opportuno.

Quando le collisioni sono risolte con l’hash doppio, il numero medio di tentativi per la ricerca di una

chiave in una tabella hash di dimensione m che contiene n = αm chiavi è:

per ricerche con successo.

per ricerche senza successo.

Il costo per inserire la prima chiave è pari al costo di una ricerca senza successo in una tabella con

n = 0 chiavi, dunque è pari ad 1.

Il costo per inserire la seconda chiave è pari al costo di una ricerca senza successo in una tabella

con n = 1 chiavi, dunque è pari a .

Il costo per inserire la terza chiave è pari al coso di una ricerca senza successo in una tabella con

n = 2 chiavi, dunque è pari a .

Continuando così, il costo medio di una ricerca con successo risulta essere appunto .

Esempio (con indirizzamento aperto):

1 19 5 20 18 3 8 9 14 7 24 43 39 13 16 12 62

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

19 1 20 3 39 5 24 7 8 9 43 62 12 13 14 16 18

Per quanto riguarda l’operazione di cancellazione all’interno delle Tabelle Hash, essa dipende dal

metodo usato per la risoluzione delle collisioni.

Per le tecniche che usano catene, la cancellazione avviene nel modo tipico delle catene.

Nelle altre situazioni si preferisce l’uso della cancellazione logica, per evitare eventuali

malfunzionamenti nelle operazioni di ricerca.

Confronto fra i vari metodi di ricerca

Spazio Ricerca Inserimento Cancellazione Ordinamento

Vettore n elementi O(log n) O(n) O(n) O(n)

2

Ordinato

Catena n elementi + n O(n) O(1) O(1) O(n)

Ordinata puntatori

n elementi + 2n

Alberi AVL O(log n) O(1) O(1) O(n)

2

puntatori

Tabelle Hash m > n elementi O(1) O(1) O(1) O(n log n)

2

Le Tabelle Hash sono da preferirsi agli Alberi perché sono più semplici e presentano tempi di

ricerca molto buoni.

Gli Alberi, però, presentano dei vantaggi rispetto alle Tabelle Hash: sono dinamici (non è

necessario conoscere a priori quante chiavi verranno inserite) e mantengono l’ordinamento delle

chiavi.

Selection Sort

Il metodo di ordinamento per selezione, noto come Selection Sort, è di tipo quadratico ed agisce

su un vettore di dati, lavorando sul posto.

Viene cercato inizialmente il più piccolo elemento del vettore stesso e viene scambiato con quello

che si trova nella prima posizione; viene cercato poi il secondo elemento più piccolo del vettore e

viene scambiato con quello che si trova nella seconda posizione e continua in questo modo finché

tutto il vettore non risulta essere ordinato.

Selection Sort Costo Algoritmo

per i = 0 a i = n-2

min = i;

per j = i+1 a n-1

se a[j] < a[min] 2

Sono richiesti circa n / 2 confronti e n - 1 scambi

min = j; per ordinare un vettore di n elementi.

temp = a[min];

a[min] = a[i];

a[i] = temp;

L’algoritmo di ordinamento per selezione non è stabile, quindi non conserva l’ordine relativo di

chiavi uguali.

Esempio (in rosso l’elemento più piccolo, in grigio la parte ordinata ad ogni giro):

503 87 512 61 908 170 897 275 653 426

503 87 512 61 908 170 897 275 653 426

61 87 512 503 908 170 897 275 653 426

61 87 512 503 908 170 897 275 653 426

61 87 170 503 908 512 897 275 653 426

61 87 170 275 908 512 897 503 653 426

61 87 170 275 426 512 897 503 653 908

61 87 170 275 426 503 897 512 653 908

61 87 170 275 426 503 512 897 653 908

61 87 170 275 426 503 512 653 897 908

61 87 170 275 426 503 512 653 897 908

61 87 170 275 426 503 512 653 897 908

Insertion Sort

Il metodo di ordinamento per inserzione, noto come Insertion Sort, è un metodo di ordinamento di

tipo quadratico.

Considerando un gruppo di dati contenuti in un vettore a, si considerano in successione gli

elementi e per ogni valore di un indice i, tra 1 e n-1, si inserisce l’elemento a[i] nella giusta

posizione tra gli elementi a[0, …, n-1].

L’inserimento avviene spostando gli elementi più grandi di una posizione a destra e poi inserendo

l’elemento nella posizione rimasta vuota.

Insertion Sort Costo Algoritmo

per i = 0 a i = n-1

v = a[i];

j = i; 2

L’algoritmo richiede circa n / 4 confronti ed

finché a[j-1] > v altrettanti spostamenti per ordinare un vettore di n

a[j] = a[j-1]; dati.

j = j-1;

a[j] = v;

L’algoritmo di ordinamento per inserzione è stabile.

Esempio (in verde l’elemento inserito, in rosso gli elementi spostati per l’inserimento, in grigio gli

elementi ancora non considerati):

20 35 18 8 14 41 3 39

20 35 18 8 14 41 3 39

20 35 18 8 14 41 3 39

18 20 35 8 14 41 3 39

8 18 20 35 14 41 3 39

8 14 18 20 35 41 3 39

8 14 18 20 35 41 3 39

3 8 14 18 20 35 41 39

3 8 14 18 20 35 39 41