c se n < b
T (bαnc) + T (dβne) + n se n ≥ b.
presentata nel corollario 6.2, possiamo concludere che per ogni t > 32 l’algoritmo lavora in tempo T (n) = O(n) nel caso peggiore.
Scegliendo t = 2 possiamo fissare H = 50 e otteniamo la seguente procedura: Procedura Seleziona(A = (A[1], A[2], . . . , A[n]), k)
ifn < 50then begin
ordina (A[1], A[2], . . . , A[n])
returnA[k]
end else
begin
dividi A in dn/5e sequenze S1, S2, . . . , Sdn/5e
fork ∈ {1, 2, . . . , dn/5e}docalcola la mediana Mkdi Sk M := Seleziona((M1, M2, . . . , Mdn/5e), d10ne)
calcola il vettore A1 degli elementi di A minori di M calcola il vettore A2 degli elementi di A uguali a M calcola il vettore A3 degli elementi di A maggiori di M
ifk ≤ |A1|then returnSeleziona(A1, k)
if|A1| < k ≤ |A1| + |A2|then returnM
if|A1| + |A2| < kthen returnSeleziona(A3, k − |A1| − |A2|)
end
8.7 Bucketsort
Gli algoritmi che abbiamo presentato nelle sezioni precedenti sono tutti basati sul confronto e non uti-lizzano alcuna specifica propriet`a degli elementi da ordinare. In questa sezione presentiamo invece un algoritmo che dipende dalle propriet`a dell’insieme dal quale gli oggetti della sequenza di input sono estratti.
Come vedremo, il procedimento che illustriamo `e stabile, cio`e fornisce in uscita un vettore nel quale gli elementi che hanno lo stesso valore conservano l’ordine reciproco che possedevano nella sequenza di input. Questa propriet`a `e spesso richiesta dalle procedure di ordinamento poich´e i valori di ingresso possono essere campi di record che contengono altre informazioni e che sono originariamente ordinati secondo un criterio differente. In molti casi, qualora due elementi abbiano lo stesso valore, si vuole conservare l’ordine precedente.
L’idea dell’algoritmo Bucketsort viene solitamente presentata attraverso un semplice esempio. Sup-poniamo di voler ordinare n interi x1, x2, . . . , xn, che variano in un intervallo [0, m − 1], dove m ∈ IN. Se m `e abbastanza piccolo, pu`o essere conveniente usare il seguente procedimento:
begin
for i ∈ {0, 1, . . . , m − 1}docrea una lista L(i) inizialmente vuota
for j ∈ {1, 2, . . . , n}doaggiungi xj alla lista L(xj) concatena le liste L(1), L(2), . . . , L(m) nel loro ordine
end
La lista ottenuta dalla concatenazione di L(1), L(2), . . . , L(m) fornisce ovviamente la sequenza ordina-ta.
Questo metodo richiede chiaramente O(m + n) passi e risulta quindi lineare se m ha lo stesso ordine di grandezza di n, migliorando quindi, in questo caso, le prestazioni degli algoritmi presentati nelle sezioni precedenti.
Con alcune variazioni la stessa idea pu`o essere usata per ordinare una sequenza di parole su un alfabeto finito. Sia Σ un alfabeto finito formato da m simboli distinti e denotiamo con Σ+ l’insieme delle parole definite su Σ (esclusa la parola vuota). Definiamo ora l’ordinamento lessicografico su Σ+ che, come `e ben noto, corrisponde al tradizionale ordinamento delle parole in un dizionario. Sia una relazione d’ordine totale su Σ e siano x = x1x2· · · xk e y = y1y2· · · yh due parole in Σ+, dove xi, yj ∈ Σ per ogni i e ogni j. Diciamo che x precede lessicograficamente y (x ≤` y) se:
- x `e un prefisso di y, cio`e k ≤ h e xi = yiper ogni i ≤ k,
- oppure esiste j, 1 ≤ j ≤ k, tale che xi = yiper ogni i < j, xj 6= yje xj yj. `
E facile verificare che ≤` `e una relazione d’ordine totale su Σ+. Descriviamo allora una procedura per ordinare, rispetto alla relazione ≤`, una n-pla di parole su Σ+, tutte di lunghezza k. Applicando il procedimento illustrato sopra l’algoritmo costruisce la lista delle parole di ingresso ordinate rispetto all’ultima lettera. Successivamente, si ordina la lista cos`ı ottenuta rispetto alla penultima lettera e si prosegue nello stesso modo per tutte le k posizioni in ordine decrescente. Come dimostreremo in seguito la lista che si ottiene risulta ordinata rispetto alla relazione ≤`.
Esempio 8.1 Consideriamo l’alfabeto {a, b, c}, dove a b c, e applichiamo il metodo illustrato alla sequenza di parole
bacc, abac, baca, abbc, cbab.
L’algoritmo esegue 4 cicli, uno per ogni posizione delle parole di ingresso. Denotiamo con La, Lb, Lcle liste delle parole che hanno rispettivamente la lettera a, b, c nella posizione corrente. Le liste al termine di ciascun ciclo sono le seguenti:
1) La= (baca) Lb= (cbab)
Lc= (bacc, abac, abbc)
2) La= (cbab, abac) Lb= (abbc) Lc= (baca, bacc)
3) La= (baca, bacc) Lb= (abab, abac, abbc) Lc= ()
4) La= (abab, abac, abbc) Lb= (baca, bacc) Lc= ()
Descriviamo ora nel dettaglio la procedura. Siano a1, a2, . . . , am gli elementi di Σ considerati nell’ordine fissato. L’input `e dato da una sequenza di parole X1, X2, . . . , Xn tali che, per ogni i ∈ {1, 2, . . . , n}, Xi = bi1bi2· · · bik dove bij ∈ Σ per ogni j. Per ogni lettera ai, L(ai) denota la lista relativa alla lettera ai; all’inizio di ogni ciclo ciascuna di queste `e vuota (Λ). Denotiamo inoltre con Q la lista contenente la concatenazione delle L(ai) al termine di ogni iterazione. `E evidente che in una reale implementazione le liste L(ai) e Q non conterranno effettivamente le parole di ingresso ma, pi`u semplicemente, una sequenza di puntatori a tali stringhe.
Procedura Bucketsort
Input: una sequenza di parole X1, X2, . . . , Xntali che, per ogni i ∈ {1, 2, . . . , n}, Xi = bi1bi2· · · bikdove bij ∈ Σ per ogni j = 1, 2, . . . , k.
begin
fori = 1, 2, . . . , ndoaggiungi Xiin coda a Q
for j = k, k − 1, . . . , 1do begin for` = 1, 2, . . . , mdoL(a`) := Λ while Q 6= Λdo begin X :=Front(Q) Q :=Dequeue(Q)
sia atla lettera di X di posto j
Inserisci in coda(L(at), X)
end
for` = 1, . . . , mdoconcatena L(a`) in coda a Q
end end
Teorema 8.5 L’algoritmo Bucketsort ordina lessicograficamente una sequenza di n parole di lunghezza
k, definite su un alfabeto di m lettere, in tempo O(k(n + m)).
Dimostrazione. Si prova la correttezza dell’algoritmo per induzione sul numero di iterazioni del loop
pi`u esterno. Al termine della i-esima iterazione la lista Q contiene le parole ordinate lessicograficamente rispetto alle ultime i lettere. Osserva infatti che, se alla i+1-esima iterazione, due parole sono poste nella stessa lista L(at), queste mantengono l’ordine reciproco che possedevano al termine dell’i-esimo ciclo. Nota infine che ogni ciclo richiede O(n + m) passi per analizzare uno dopo l’altro gli elementi di Q e concatenare le liste L(at). Quindi O(k(n + m)) passi sono necessari per terminare l’implementazione.
Concludiamo ricordando che l’algoritmo presentato pu`o essere migliorato ed esteso al caso in cui le parole di ingresso sono di lunghezza diversa. Se L `e la somma delle lunghezza delle parole di ingresso si possono ordinare queste ultime in tempo O(m + L).
Esercizi
1) Tra gli algoritmi di ordinamento presentati nelle sezioni precedenti quali sono quelli stabili?
2) Ricordando l’algoritmo per il calcolo della mediana di una sequenza, descrivere una nuova versione di Quicksort che richiede un tempo O(n log n) nel caso peggiore.
Strutture dati e algoritmi di ricerca
Analizzando un problema, spesso ci si accorge che esso pu`o essere agevolmente risolto mediante sequen-ze di prefissate operazioni su opportuni insiemi. In altri termini, il progetto di un algoritmo risolutivo per il problema risulta agevolato se ci si riferisce ad una “naturale” struttura di dati, dove conveniamo di chiamare struttura dati la famiglia di tali insiemi ed operazioni.
L’individuazione di una struttura di dati permette di suddividere il problema in (almeno) due fasi: 1. progetto di un algoritmo risolutivo “astratto” espresso in termini di operazioni della struttura di
dati.
2. progetto di algoritmi efficienti per la rappresentazione dei dati e l’implementazione delle oper-azioni sul modello di calcolo a disposizione.
Questa impostazione unisce semplicit`a, chiarezza e facilit`a di analisi. Infatti la correttezza dell’algo-ritmo “eseguibile” pu`o essere ottenuta considerando separatamente la correttezza dell’algodell’algo-ritmo “as-tratto” e quella dell’implementazione delle operazioni. Infine, si pu`o osservare che molti problemi ammettono come “naturale” la stessa struttura dati: particolare attenzione andr`a in tal caso dedicata all’implementazione efficiente delle operazioni (algoritmi di base).
Questo approccio `e gi`a stato utilizzato nel capitolo 4 per introdurre le strutture dati di base quali vettori, liste, pile, ecc. Vogliamo ora studiare l’argomento con maggiore sistematicit`a presentando una nozione generale di struttura dati.