Algoritmi di ordinamento · 7/7
Distribuisce i valori per intervallo, ordina localmente e concatena.
Ogni secchio rappresenta un intervallo ordinato rispetto agli altri. Dopo la distribuzione basta ordinare i valori dentro ciascun secchio e concatenarli da sinistra a destra.
La funzione di distribuzione cumulativa (CDF) di una variabile X associa a ogni soglia x la probabilità che X non la superi. È non decrescente, vale tra 0 e 1 e tende a 0 o a 1 agli estremi della retta.
Se F è continua e conosciuta, F(X) è uniforme tra 0 e 1. Per k bucket numerati da 0 a k−1 si usa b(x) = min(k−1, ⌊k F(x)⌋). Le soglie dei bucket sono i quantili F⁻¹(i/k): ogni intervallo contiene, nel modello, probabilità 1/k. Il minimo protegge il caso F(x)=1.
Per una variabile continua con densità f, si integra: F(x) = ∫₋∞ˣ f(t) dt. Se X è uniforme tra a e b, all’interno dell’intervallo F(x) = (x−a)/(b−a). Fuori da [a,b] vale 0 a sinistra e 1 a destra. Per esempio su [0, 100], F(35)=0,35: con 10 bucket, 35 va nel bucket 3.
Si sommano le probabilità dei valori non maggiori di x: F(x) = somma di P(X=v) per ogni v≤x. Se P(X=1)=0,2, P(X=2)=0,5 e P(X=3)=0,3, allora F(2)=0,7. La CDF ha salti: applicare F(X) direttamente non rende uniformi i bucket quando molti valori coincidono.
Da un campione di m osservazioni, F̂ₘ(x) = #{valori ≤ x}/m. Per i dati 1, 2, 2, 5, 8 si ottiene F̂₅(2)=3/5. Un campione rappresentativo può suggerire i quantili; stimarli ha però un costo e gli errori di stima possono sbilanciare i bucket.
Riprendiamo l’esempio di Algoritmi.pdf: punti distribuiti uniformemente nell’area di un disco di raggio R. Se la chiave è l’angolo θ, gli spicchi hanno ampiezza 2π/k e FΘ(θ)=θ/(2π). Se la chiave è la distanza r dal centro, anelli di uguale spessore non sono equilibrati: l’area cresce con r². Occorrono anelli di uguale area.
0 ≤ θ < 2π · FΘ(θ) = θ/(2π) · b(θ) = ⌊kθ/(2π)⌋
Con k=8, un punto a θ=π/2 entra nel bucket 2.
0 ≤ r ≤ R · Fᵣ(r) = πr²/(πR²) = (r/R)² · rᵢ = R√(i/k)
Con R=10 e k=4, il primo anello termina a r₁=5; ogni anello copre il 25% dell’area.
Seleziona un punto nel disco, oppure avanza con i controlli.
Ogni barra rappresenta un elemento. I colori distinguono gli elementi confrontati, il pivot o la chiave, la parte già definitiva e l’area attiva.
Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.
create k empty bucketsfor value in A index ← bucketFor(value) append value to bucket[index]for each bucket sort bucketconcatenate all buckets into ALa riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.
Con secchi ben scelti e pochi elementi per secchio, distribuzione e concatenazione costano Θ(n+k).
Assumendo valori uniformi e k=Θ(n), la dimensione attesa dei secchi è costante e il tempo atteso è Θ(n+k).
Se tutti gli elementi finiscono nello stesso secchio e questo usa insertion sort, il costo diventa Θ(n²).
I k secchi contengono complessivamente n elementi: Θ(n+k). Stabilità e costo dipendono dall’ordinamento interno.
La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.
La classificazione considera la versione dell’algoritmo mostrata in questa pagina.
Efficace quando la distribuzione è nota e quasi uniforme, per esempio misure normalizzate o coordinate spaziali.
Numero e confini dei secchi sono parte dell’algoritmo: una scelta che non riflette la distribuzione crea forti sbilanciamenti.