Discussione:Bucket sort

L'algoritmo descritto non è il Bucket Sort bensì il Counting Sort. Confornta pagina in inglese

Sistemato, grazie per la segnalazione. --Giuseppe (msg) 01:40, 1 mag 2008 (CEST)

Implementazioni

Ricordo a tutti che le implementazioni in specifici linguaggi vanno messe su Wikibooks, come da decisione della comunità. Il link a wikibooks è in fondo alla voce, nella sezione Altri progetti. Grazie. --Giuseppe (msg) 16:45, 27 gen 2010 (CET)

Complessità Temporale

La complessità nel caso pessimo è O(N^2). Se infatti tutti i valori capitassero in un unico bucket, si tratterebbe di fare Insertion Sort su N, che ha complessità nel caso pessimo O(N^2).

Aggiungo: la descrizione iniziale è errata. Non è infatti necessario che i valori stiano in un intervallo limitato, ma piuttosto che siano date delle misure di probabilità sulla distribuzione dei valori. Ineffetti più ho una misura precisa di dove possono cadere i valori, più riesco a creare dei bucket equiprobabili e quindi ad avere delle liste equamente lunghe.

Esempio 1: Se fisso l'intervallo (0,10) per i miei valori, ma poi il 99% dei valori finisce nel primo bucket, diventa insertion sort. Esempio 2: Se i miei valori possono assumere qualsiasi valore nei Naturali, basta fissare un certo X per cui tutti i valori maggiori di X finiscono in quel bucket, e se comunque ho, per dire, dieci bucket tutti con probabilità del 10%, bucket sort lavora bene. — Questo commento senza la firma utente è stato inserito da ProudIT‎ (discussioni · contributi) 12:56, 31 mar 2015 (CEST).

Più tardi verifico sul Cormen. Intanto, come per tutte le altre voci, se ritieni che ci sia un errore indica se (1) la fonte di riferimento riporta una diversa informazione o (2) esiste una fonte differente che fornisce una diversa informazione. I ragionamenti personali, per quanto accurati, si configurano come ricerche originali. --Giuseppe (msg a baruneju) 19:42, 31 mar 2015 (CEST)

Ho visto che sono state apportate delle correzioni al testo. Già meglio ma rimane comunque impreciso il riferimento di "Intervallo divisi in uguale lunghezza". Ripeto, non è una questione di "uguale lunghezza" ma uguale probabilità. Se abbiamo una distribuzione uniforme in uno spazio lineare, ok, sono d'accordo (è il caso che propone il Cormen). Ma è un'assunzione non necessaria. Bucket può essere più forte di così (di fatto il Cormen è solo un libro introduttivo).

Se abbiamo dei punti che cadono casualmente in un cerchio, e vogliamo ordinarli per distanza dal centro col bucket-sort, dobbiamo tenere conto del rapporto quadratico tra area e raggio, e dobbiamo creare dei bucket che rendano l'area delle corone equivalenti, per cui la lunghezza dei bucket sarà meno che proporzionale al loro numero (si noti che la distribuzione resta uniforme, quello che mi interessa è che NON PER FORZA la lunghezza dei bucket deve essere la stessa).

Serve una fonte per dire che 2 è il secondo numero dei Naturali? Non credo. Se non serve per quello, non serve neanche per capire che il mio ragionamento è logico, in quanto esso è di fatto una dimostrazione valida dell'asserto.

Comunque, se proprio serve:

http://www.codeproject.com/Questions/399805/Bucket-Sort-of-Points-in-a-Unit-Circle

--Proud (msg) 12:42, 3 apr 2015 (CEST)