Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ordinamenti lineari
(per dati di input con proprietà particolari)
1
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Un semplice esempio
• Supponiamo che gli n elementi da
ordinare siano tutti appartenenti
all’intervallo [1,n]
• In quanto tempo possiamo ordinarli?
• O(n)
• Contraddice il lower bound?
• No, perché non è un algoritmo basato su
confronti!
2
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
IntegerSort: fase 1
Per ordinare n interi con valori in [1,k]
Mantiene un array Y di k contatori tale che Y[x] = numero
di volte che il valore x compare nell’array di input X
X
5
1
6
8
6
Y
0
1
0
2
0
3
0
4
1
5
X
5
1
6
8
6
Y
1
1
0
2
0
3
0
4
1
5
0
6
1
6
0
7
0
7
0
8
1
8
5
1
6
8
6
1
1
0
2
0
3
0
4
1
5
5
1
6
8
6
1
1
0
2
0
3
0
4
1
5
0
6
0
7
0
8
2
6
0
7
1
8
5
1
6
8
6
1
1
0
2
0
3
0
4
1
5
1
6
0
7
0
8
(a) Calcolo di Y
3
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
IntegerSort: fase 2
Scorre Y da sinistra verso destra e, se Y[x]=k, scrive in
X il valore x per k volte
X
1
1
Y
1
1
0
2
0
3
0
4
X
1
5
6
6
Y
0
1
0
2
0
3
0
4
1
5
0
5
2
6
2
6
0
7
0
7
1
8
1
8
0
1
0
2
0
3
0
4
1 5
6
6
0
1
0
3
0
4
0
2
1
5
0
5
2
6
0
6
0
7
0
7
1
8
1
8
1
5
0
1
0
2
0
3
0
4
1
5
1
5
6
6
8
0
1
0
2
0
3
0
4
0
5
2
6
0
7
1
8
0
6
0
7
1
8
(b) Ricostruzione di X
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
IntegerSort (X, k)
1.
Sia Y un array di dimensione k
2.
for i=1 to k do Y[i]=0
3.
for i=1 to n do incrementa Y[X[i]]
4.
j=1
5.
for i=1 to k do
6.
while (Y[i] > 0) do
7.
X[j]=i
8.
incrementa j
9.
decrementa Y[i]
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
IntegerSort: analisi
• Tempo O(k) per inizializzare Y a 0
• Tempo O(n) per calcolare i valori dei contatori
• Tempo O(n+k) per ricostruire X
O(n+k)
Tempo lineare se k=O(n)
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
BucketSort
Per ordinare n record con chiavi intere in [1,k]
• Basta mantenere un array di liste, anziché di
contatori, ed operare come per IntegerSort
• La lista Y[x] conterrà gli elementi con chiave
uguale a x
• Concatenare poi le liste
Tempo O(n+k) come per IntegerSort
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
BucketSort (X, k)
1.
Sia Y un array di dimensione k
2.
for i=1 to k do Y[i]=lista vuota
3.
for i=1 to n do
4.
if (chiave(X[i]) [1,k] ) then errore
5.
else appendi il record X[i] alla lista Y[chiave(X[i])]
6.
7.
8
for i=1 to k do
copia ordinatamente in X gli elemeti della lista Y[i]
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Stabilità
• Un algoritmo è stabile se preserva l’ordine iniziale
tra elementi con la stessa chiave
• domanda: il BucketSort è stabile?
• Il BucketSort può essere reso stabile appendendo
gli elementi di X in coda alla opportuna lista Y[i]
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
RadixSort
• Cosa fare se il massimo valore k=ω(n), ad
esempio se k = (nc)?
• Rappresentiamo gli elementi in base b, ed
eseguiamo una serie di BucketSort
• Partiamo dalla cifra meno significativa verso
quella più significativa
Per
b=10
10
2397
4368
5924
5924
2397
4368
5924
4368
2397
4368
2397
5924
2397
4368
5924
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Correttezza
• Se x e y hanno una diversa t-esima cifra, la
t-esima passata di BucketSort li ordina
• Se x e y hanno la stessa t-esima cifra, la
proprietà di stabilità del BucketSort li
mantiene ordinati correttamente
Dopo la t-esima passata di BucketSort, i
numeri sono correttamente ordinati rispetto
alle t cifre meno significative
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Tempo di esecuzione
• O(logb k) passate di bucketsort
• Ciascuna passata richiede tempo O(n+b)
O( (n+b) logb k)
logk
Se b = (n), si ha O(n logn k)=O n
logn
Tempo lineare se k=O(nc), c costante
12
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Riepilogo
• Nuove tecniche:
– Divide et impera (MergeSort, QuickSort)
– Randomizzazione (QuickSort)
– Strutture dati efficienti (HeapSort)
• Proprietà particolari dei dati in ingresso possono
aiutare a progettare algoritmi più efficienti:
algoritmi lineari
• Alberi di decisione per la dimostrazione di
delimitazioni inferiori
13
Copyright © 2004 - The McGraw - Hill Companies, srl