Algoritmi - Ordinamento, strutture dati, alberi, code di priorità e tabelle hash

Ordinamento

Insertion sort

InsertionSort(A)

N ← lunghezza(A)

for j ← 2 to n do

// inserisce A[j] nella sequenza ordinata A[1...j-1]

x ← A[j]

i ← j–1

while i >= 1 and x < A[i] do

A[i+1] ← A[i]

i ← i–1

A[i] ← x

• Best case: O(n)
• Worst case: O(n²)
• Stabile: sì
• In place: sì

Merge sort

MergeSort(A, p, r)

if p < r then

q ← (p+r)/2

MergeSort(A, p, q)

MergeSort(A, q+1, r)

Merge(A, p, q, r)

Merge(A, p, q, r)

n ← q-p+1

n ← r-q

for i ← 1 to n do

L[i] ← A [p+i-1]

for j ← 1 to n do

R[j] ← A[q+j]

L[i+1] ← R[j+1] ← +∞

i ← j ← 1

for k ← p to r do

if L[i] <= R[j] then

A[k] ← L[i]

i ← i+1

else then //L[i] > R[j]

A[k] ← R[j]

j ← j+1

• Best case: O(n log n) (se n potenza di 2)
• Avarage case: O(n log n)
• Stabile: sì
• In place: no

Quick sort

QuickSort(A, p, q)

if p < q then

i ← Partition(A, p, q)

QuickSort(A, p, i-1)

QuickSort(A, i+1, q)

Partition(A, p, q)

i ← p

j ← q

x ← A[p]

while i < j do

while A[j] > x do

j ← j-1

if i < j then

t ← A[j]; A[j] ← A[i]; A[i] ← t; i ← i+1;

while A[i] < x do

i ← i+1

if i < j then

t ← A[j]; A[j] ← A[i]; A[i] ← t; j ← j-1;

return i

• Best case: O(n log n) (se Partition ritorna sempre la mediana)
• Worst case: O(n²)
• Avarage case: O(n log n)
• Stabile: no
• In place: sì

Se invece di usare la funzione Partition che divide l’array in maniera casuale usassi la funzione Deterministic Selection (che ritorna in i la posizione occupata dalla mediana nell’array non ordinato) anche il Worst case sarebbe O(n log n)

Counting sort

Si basa sull’ipotesi che ognuno degli n elementi in input sia un intero nell’intervallo da 1 a k. Conviene usare questo algoritmo se k è non troppo grande, altrimenti avrei un’occupazione della memoria eccessiva dato che non è in place, bensì l’utilizzo della memoria è legato a k (O(k)).

CountingSort(A, B, k)

for i ← 1 to k do

C[i] ← 0

for j ← 1 to lunghezza(A) do

C[A[j]] ← C[A[j]]+1 // C[i] contiene il numero di elementi uguali a i

for i ← 2 to k do

C[i] ← C[i] + C[i-1] // C[i] ora contiene il numero di elementi <= di i

for j ← lunghezza(A) down to 1 do

B[C[A[j]]] ← A[j]

C[A[j]] ← C[A[j]] -1

• Best, worst ed avarage case: O(n)
• Stabile: sì
• In place: no

Radix sort

Ordina n numeri ognuno di d cifre così: prima ordina i numeri in base alla cifra meno significativa (+ a destra), poi in base a quella alla sua sinistra e cosi via finché non arriva alla cifra più significativa. O(n).

Bucket sort

Assume che l’input sia generato da un processo casuale che distribuisce gli elementi in modo uniforme nell’intervallo [0,1)

BucketSort(A)

n ← lunghezza(A)

for i ← 1 to n do

inserisci A[i] nella lista B[n A[i]]

for i ← 0 to n-1 do

ordina la lista B[i] con l’InsertionSort

concatena insieme le liste B[0], B[1], … , B[n-1] in questo ordine

T(n) = O(n)

Deterministic selection

Ritorna la posizione occupata nell’array non ordinato dall’elemento di rango k.

Funzionamento:

1. Divide gli n elementi dell’array in input in n/5 gruppi di 5 elementi ciascuno e al più un gruppo costituito dai rimanenti n mod 5 elementi: O(1)
2. Trova la mediana di ogni gruppo ordinandolo con l’Insertion Sort e poi prendendo l’elemento in posizione 3
3. Usa Selection ricorsivamente per trovare la mediana delle mediane chiamandolo su un insieme di n/5 elementi
4. Partiziona l’array in input attorno alla mediana delle mediane ottenendone il rango
5. Se k = rango delle mediana delle mediane ho fatto, se è < richiamo Deterministic Select sul gruppo a sx, se è > lo richiamo sul gruppo a destra

DeterministicSelect(A, k)

if n = 1 then

return the first element of A

Dividi A in g=n/5 gruppi di 5 elementi ciascuno ottenendo A₁, A₂, … A_g

for i ← 1 to g do

trova la baby mediana x in A_i

x ← DeterministicSelect({x₁, x₂, … x_g}, g/2) //trova la mediana delle mediane

Partiziona A in:

1. L: elementi in A più piccoli di x
2. E: elementi in A uguali a x
3. G: elementi in A più grandi di x

if k <= |L| then

DeterministicSelect(L, k)

else if k <= |L| + |E| then

return x

else DeterministicSelect(G, k - |L| - |E|)

T(n) = O(n)

Strutture dati

Pile

• Gestite con LIFO
• Insert: Push
• Delete: Pop
• Operazioni da garantire: push, pop, size, isEmpty

- Realizzazione con un array

Array S di N posti, con elementi immagazzinati da S[0] a S[t]

t: indice dell’ultimo elemento inserito nella pila in S (primo elemento da restituire)

Gli indici iniziano da 0

Inizialmente t è inizializzato a -1 (pila vuota)

Numero degli elementi nella pila: t+1

Algoritmi:

push(o)

if t+1 = N then

return “Errore: pila piena”

t ← t+1

S[t] ← o

pop()

if t < 0 then

return “Errore: pila vuota”

e ← S[t]

S[t] ← null

t ← t-1

return e

isEmpty()

if t < 0 then

return true

else return false

T(n) di push, pop, isEmpty: O(1)

Code

• Gestite con FIFO
• Insert: enqueue
• Delete: dequeue
• f (front): punta al primo elemento inserito (quello restituito dalla dequeue)
• r (rear): punta alla prima posizione dopo quella dell’ultimo elemento inserito (punta a dove verrà inserito il nuovo elemento dalla enqueue)

- Realizzazione con un array

Array Q di N posti, con elementi immagazzinati da Q[f] a Q[r-1]

Inizialmente f = r = 0

La coda è vuota se f = r

enqueue: incrementa r di 1

dequeue: incrementa f di 1

Utilizzando l’array come una coda circolare, f e r non sono limitati da N: scorrendo l’array da sinistra a destra si va da Q[0] a Q[N-1] e poi di nuovo a Q[0]

Quindi ogni volta che incremento f o r, computo quest’incremento come (f+1) mod N o (r+1) mod N

Per poter distinguere fra coda piena e coda vuota si impone che Q non può immagazzinare più di N-1 elementi ((N-f+r) mod N <= N-1)

Algoritmi:

enqueue(o)

if (N-f+r) mod N = N-1 then

return “Errore: coda piena”

Q[r] ← o

r ← (r+1) mod N

dequeue()

if f = r then

return “Errore: coda vuota”

temp ← Q[f]

Q[f] ← null

f ← (f+1) mod N

return temp

T(n) di enqueue e dequeue: O(1)

Liste

Al contrario di pile e code permettono l’accesso in qualsiasi posizione

- Index based lists (array)

• La sequenza S contiene n elementi
• Ci si riferisce unicamente ad ogni elemento attraverso il suo indice
• L’indice di un elemento è il suo rango (numero di elementi prima di lui in S)
• Indice iniziale: 0
• Indice finale: n-1
• L’indice è differente da quello degli array perché questo non è statico
• Operazioni:
  1. get(r): ritorna l’elemento di S con indice r
  2. set(r, e): rimpiazza con e l’elemento con indice r e restituisce quest’ultimo
  3. add(r, e): inserisce un nuovo elemento e in S con indice r
  4. remove(r): elimina da S l’elemento con indice r
• Sono implementate con un Array A di dimensione N (n < N) in cui A[i] immagazzina (una referenza a) l’elemento con indice i

Algoritmi:

add(r, e)

if n = N then

return “L’array è pieno”

if r < n then

for i ← n-1 down to r do

A[i+1] ← A[i] // fa spazio per il nuovo elemento

A[r] ← e

n ← n+1

remove(r)

e ← A[r]

if r < n-1 then

for i ← r to n-2 do

A[i] ← A[i+1] // fa scorrere a sinistra gli elementi dopo r

n ← n-1

return e

Metodo Tempo

get(r) O(1)

set(r, e) O(1)

add(r,