mastorna.it
EN

Algoritmi di ordinamento · 7/7

Bucket sort

Distribuisce i valori per intervallo, ordina localmente e concatena.

Tempo medioΘ(n + k) MemoriaΘ(n + k) StabileDipende In placeNo

Come funziona

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.

Invariante: Ogni valore nel secchio i è non maggiore dei valori nei secchi successivi; resta da ordinare soltanto all’interno di ciascun secchio.

Simulazione passo passo

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.

Confronti
0
Scritture
0
Scambi
0
Passaggio / livello
0
attivo confronto pivot / chiave definitivo

Pseudocodice collegato alla simulazione

  1. create k empty buckets
  2. for value in A
  3. index ← bucketFor(value)
  4. append value to bucket[index]
  5. for each bucket
  6. sort bucket
  7. concatenate all buckets into A

La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.

Studio della complessità

Caso miglioreΘ(n + k)

Con secchi ben scelti e pochi elementi per secchio, distribuzione e concatenazione costano Θ(n+k).

Caso medioΘ(n + k)

Assumendo valori uniformi e k=Θ(n), la dimensione attesa dei secchi è costante e il tempo atteso è Θ(n+k).

Caso peggioreΘ(n²)

Se tutti gli elementi finiscono nello stesso secchio e questo usa insertion sort, il costo diventa Θ(n²).

Spazio ausiliarioΘ(n + k)

I k secchi contengono complessivamente n elementi: Θ(n+k). Stabilità e costo dipendono dall’ordinamento interno.

Proprietà in breve

Stabilità condizionale

La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.

Non in place

La classificazione considera la versione dell’algoritmo mostrata in questa pagina.

Quando usarlo e che cosa evitare

Buona scelta quando…

Efficace quando la distribuzione è nota e quasi uniforme, per esempio misure normalizzate o coordinate spaziali.

Errore comune

Numero e confini dei secchi sono parte dell’algoritmo: una scelta che non riflette la distribuzione crea forti sbilanciamenti.