Radix-Sort(A,d) // A[i] = cd...c2c1

for j = 1 to d // A è ordinato rispetto alle cifre cj-1...c1

“usa un algoritmo stabile per ordinare A rispetto alla j-esima cifra” // A è ordinato rispetto alle cifre cj...c1

// A è ordinato

Radix-Sort(A,d) // Complessità for j = 1 to d “usa Counting-Sort per ordinare A rispetto alla j-esima cifra”

))((),,( bndbdnT RS Complessità:

dove b è la base della numerazione e d è il numero di cifre dei numeri da ordinare.

Dovendo ordinare n numeri di m bit ciascuno possiamo scegliere r < m e suddividere i numeri in d=m/r “cifre” di r bit ciascunaIn questo caso la base della numerazione è b=2r e Radix-Sort richiede tempo ))2)(/(( rnrm

Quindi il valore ottimo di r dipende soltanto da n ed è approssimativamente log2 n.

La funzione ha un minimo per)2)(/()( rnrmrf r tale che nrr 22 log)12ln(log

Algoritmo Bucket-Sort

L’algoritmo Bucket-Sort assume che i valori da ordinare siano dei numeri reali in un intervallo semiaperto [a,b).

Per semplicità di esposizione assumiamo che l’intervallo sia [0,1).

1. Divide [0,1) in n parti uguali e inizializza un array B[0..n-1] di liste vuote (i bucket)

2. Mette in ciascuna lista B[k] gli elementi A[i] che cadono nella k-esima parte di [0,1)

3. Ordina ciascuna lista

4. Ricopia in A tutti gli elementi delle liste nell’ordine B[0],B[1],…,B[n-1]

Bucket-Sort per ordinare l’array A procede come segue:

A .781

.172

.393

.264

.725

.946

.217

.128

.239

.6810

B0 /

1 /

2 /

3 /

4 /

5 /

6 /

7 /

8 /

9 /

.78 /

.17 /

.39 /

.26 /

.72 /

.94 /

.21 /

.12 /

.23 /

.68 /

.12 / .17 /

.21 / .23 / .26 /

.72 / .78 /

.39 /

.68 /

.94 /

A .121

.172

.213

.234

.265

.396

.687

.728

.789

.9410

Bucket-Sort(A) n = A.length for i = 0 to n-1 “crea la lista vuota B[i]” for i = 1 to n “metti A[i] nella lista B[ nA[i] ]” // Gli elementi dell’array A sono stati tutti // inseriti nelle liste B[0],B[1],...,B[n-1] // Gli elementi di una lista B[i] sono minori degli // elementi della lista successiva B[i+1] for i = 0 to n-1 “ordina la lista B[i]” “copia in A le liste B[0],B[1],...,B[n-1]” // A è ordinato

Bucket-Sort(A) // Complessità

n = A.length //

for i = 0 to n-1

“crea la lista vuota B[i]” //

for i = 1 to n

“metti A[i] nella lista B[nA[i]]” //

for i = 0 to n-1

“ordina la lista B[i] con InsertSort” //

“copia in A le liste B[0],...,B[n-1]” //

)(n

)1(

)(n

1

0

2n

i inO

)(n

1

0

2)()(n

i iBS nOnnT

Nel caso peggiore in cui tutti gli elementi vanno a finire in un’unica lista abbiamo:

)()()()( 22max nOnOnnT BS

Nel caso migliore in cui gli elementi si distribuiscono uno per lista abbiamo:

)()()()(min nnOnnT BS Anche per il caso medio, se si assume che i valori in ingresso siano uniformemente distribuiti nell’intervallo [0,1), si dimostra che: )()(med nnT BS

Per dimostrarlo ci servono alcune semplici nozioni di calcolo delle probabilità.

Supponiamo di estrarre casualmente un valore x da un insieme X di possibili valori.

Non necessariamente tutti i valori x hanno la stessa probabilità di essere estratti.

Indichiamo con px la probabilità che venga estratto x

Xx

xxpX ]E[

Il valore medio che ci aspettiamo di ottenere si dice valore atteso di X ed è

1Xx

xpNaturalmente

Ad esempio se X è l’insieme delle possibili vincite alla roulette quando puntiamo 100 € su di un numero allora X contiene i due valori:

- 3600 € con probabilità 1/37 (si vince 36 volte la posta e i numeri della roulette sono 37 contando anche lo 0 dove vince sempre il banco) e

- 0 € con probabilità 36/37

Il valore atteso della vincita è allora

30.9737

360

37

13600]E[

XxxxpX

Dunque paghiamo 100 € per ricevere in media soltanto 97,30 € !!!!

Vediamo un altro esempio: X è l’insieme delle possibili vincite al Lotto quando puntiamo 100 € su di un terno.

X contiene i due valori: - 450000 € con probabilità 1/11748 (la vincita è 4500 volte

la posta e la probabilità che esca il terno è 1/11748) .- 0 € con probabilità 11747/11748.

Il valore atteso della vincita è allora

30.3811748

117470

11748

1450000]E[

XxxxpX

Dunque paghiamo 100 € per ricevere in media soltanto 38,30 €.Gli altri 61,70 € se li tiene lo stato come tassa sulla speranza

Il valore atteso gode delle seguenti proprietà:

]E[]E[]E[ YXYX qualunque siano le due variabili casuali X ed Y (anche se non sono tra loro indipendenti)Inoltre se le due variabili X ed Y sono indipendenti: ]E[]E[]E[ YXXY

Se c è una costante:

]E[]E[ YccY

Per ragioni di simmetria il valore atteso è lo stesso per tutte le liste.

Ci possiamo quindi limitare a calcolare il valore atteso relativo alla prima lista:

Tornando alla complessità media di Bucket-Sort e usando le proprietà del valore atteso:

)]E[()(

)]()(E[)(1

0

2

1

0

2med

n

i i

n

i iBS

nOn

nOnnT

]E[ 21n

Per calcolare definiamo le variabili casuali indicatrici

per cui

ni

iXn1

1

altrimenti0

[1] lista nella messo viene][ se1 BiAX i

Se A[i] è scelto casualmente, la variabile Xi ha valore 1 con probabilità 1/n e 0 con probabilità (n-1)/n.

Il valore atteso ènn

n

nX i

110

11]E[

ni

iXn1

1 1]E[]E[

]E[ 21n

Usando le variabili casuali indicatrici Xi possiamo calcolare:

][E]E[])E[(]E[

11

11

2

1

21

njni

ji

njni

jini

i XXXXXn

jinjni

jini

i XXX

111

2 ][E]E[]E[

nn

n

nX i

110

11]E[ 222

2

1]E[]E[

nXX ji

nnnn

nn

nnn

jinjnini

12

1)1(

111]E[

2

11

21

21

1

0

22 ]E[)()(

n

i iBS

med ncnnT

Quindi, assumendo che i valori siano dei reali uniformemente distribuiti in [0,1):

1

02 )1

2()(n

i ncn

)(2)( 22 ncncn

Algoritmi per statistiche d’ordine Problema della statistica d’ordine

Input: Un insieme A di n numeri ed un intero k compreso tra 1 ed n

Output: x A, k-esimo in ordine di grandezza

x A è il k-esimo in ordine di grandezza se gli altri n-1 elementi si possono ripartire in due gruppi: un gruppo di k-1 elementi tutti minori o uguali di x ed un gruppo di n-k elementi tutti maggiori o uguali di x.

Casi particolari:

k = 1 (minimo)

k = n (massimo)

k = (n+1)/2 (mediana inferiore o mediana)

k = (n+1)/2 (mediana superiore)

Minimo o massimo

Quanti confronti servono per trovare il minimo (o il massimo)?Minimo(A) // Massimo(A) è analogo min = A[1] for i = 2 to A.length

if min > A[i] min = A[i]

return min

n-1 confronti come limite superiore

Ma anche n-1 confronti come limite inferiore!

Possiamo escludere che un elemento sia il minimo soltanto dopo aver verificato che esso è maggiore di un altro!!

Dunque n-1 confronti è un limite stretto per calcolare il minimo e tale limite vale anche per il massimo.

Per escludere n-1 elementi servono quindi almeno n-1 confronti.

Min-Max(A) if A.length dispari max = min = A[1], i = 2 else if A[1] < A[2] min = A[1], max = A[2], i = 3 else min = A[2], max = A[1], i = 3

Minimo e massimo Quanti confronti servono per trovare assieme il minimo e il massimo?

while i ≤ A.length if A[i] < A[i+1]

if min > A[i] min = A[i]

if max < A[i+1] max = A[i+1] else

if min > A[i+1] min = A[i+1]

if max < A[i] max = A[i] i i+2 return min,max

se n dispari i confronti sono:

meno di 3 confronti ogni 2 elementi

nnn

2

3

2

3

2

3

2

13

se n pari i confronti sono:

nnn

2

32

2

3

2

231

Statistica d’ordine in tempo medio lineare

Il problema della statistica d’ordine:

Input: Un insieme A di n valori ed un intero k compreso tra 1 ed n

Output: x A, k-esimo in ordine di grandezza

Per semplicità supponiamo valori distinti

Si può risolvere in tempo medio lineare con un algoritmo Select ottenuto modificando Randomized-Quicksort

Complessità: minima O(n), massima O(n2)

Randomized-Select(A,p,r,k) // 1 ≤ k ≤ n if p == r return A[p] q = Randomized-Partition(A,p,r) // A[p..q-1] < A[q] < A[q+1..r] i = q - p+1 if k == i return A[q] elseif k < i return Randomized-Select(A,p,q-1,k) else return Randomized-Select(A,q+1,r,k-i)

r

pq

RSmed

RSmed qrpqT

nabnnT )),(max(

1)(

cT RSmed )1(

Limite superiore per la complessità media

1

0

))1,(max(1 n

i

RSmed iniT

nabn

spezzando la sommatoria in corrispondenza dell’elemento medio si ottiene

1

0

))1,(max(1

)(n

i

RSmed

RSmed iniT

nabnnT

1

2/)1(

2/)1(

0

)(1

)1(1 n

ni

RSmed

n

i

RSmed iT

ninT

nabn

dove il ≤ è dovuto al fatto che quando n è dispari il termine mediano viene sommato due volte.

1

2/)1(

2/)1(

0

)(1

)1(1 n

ni

RSmed

n

i

RSmed iT

ninT

nabn

1

2/)1(

)(2

)(n

ni

RSmed

RSmed iT

nabnnT

Con la sostituzione j = n - i - 1 nella prima sommatoria si ottiene

1

2/)1(

1

2/)1(

)(1

)(1 n

ni

RSmed

n

nj

RSmed iT

njT

nabn

Le due sommatorie sono uguali e quindi

Usiamo il metodo di sostituzione assumendo che la soluzione sia del tipo

21)( knknT RSmed

Se esistono due costanti k1 e k2 che soddisfano

per ogni n>1 abbiamo trovato la soluzione.

1

2/)1(

)(2

)(n

ni

RSmed

RSmed iT

nabnnT

cT RSmed )1(

Per n = 1 otteniamo k1 + k2 = cPer n > 1 dobbiamo dimostrare che

)()(

2 1

2/)1(

nTiTn

abn RSmed

n

ni

RSmed

Ossia sostituendo k1n + k2 da entrambe le parti

21

1

2

121 )(

2knkkik

nabn

n

ni

21

1

2

121 )(

2knkkik

nabn

n

ni

1

2

121

1

2

121 )

2

1(

2 )(

2 n

ni

n

ni

kn

kn

abnkikn

abn

2

1)

2

1(

2 21

nnk

nk

nabn

2)

22(

22

11 nk

kn

k

nabn

211

2)

2( k

kan

kb

è vera per ogni n se e

21211

2)

2( knkk

kan

kb

11

2k

kb 0

21

ka

La disequazione k1 + k2 = c per il caso base fornisce infine k2 = c - k1

ossia quando k1 ≤ 2b e k1 ≤ 2a

Dunque con k1 = min(2b,2a) e k2 = c - k1

21)( knknT RSmed

è una soluzione e quindi )()( nOnT RSmed