Bucket sort con libreria STL in C++

Ultimi Sorgenti

Algoritmo di ordinamento Bucket sort con STL

Screen	Screen non uppato.
Linguaggio	Cpp
Descrizione	Si tratta del Bucket sort, uno degli algoritmi di ordinamento a complessità lineare (nel caso migliore) realizzato con l'ausilio della libreria STL del C++. Vengono generati n numeri di input e si suppone che questi, uniformemente distribuiti all'interno di un certo intervallo, vengano divisi in un numero stabilito a priori di "bucket" (= "secchi", che non sono altro che liste lineari) e poi si procede con l'ordinamento delle singole liste; fatto questo, basta stampare ordinatamente gli elementi dal primo della prima lista all'ultimo dell'ultima, ottenendo così l'output ordinato. L'algoritmo ovviamente funziona sempre, anche se ha senso solo se accade che i numeri siano distribuiti uniformemente all'interno dell'intervallo (in questo caso [0,99]): in tal caso in ciascun bucket avremo non più di un certo numero di elementi, quindi l'algoritmo di ordinamento richiamato su di essi avrà un tempo di esecuzione costante C, ed essendo ripetuto n volte (per gli n bucket), avremo un tempo di esecuzione totale Cn, che è lineare (quindi migliore della complessità nlogn degli algoritmi divide et impera, che essendo basati su confronti non potranno mai avere complessità minore). Questo ovviamente presuppone anche che il numero dei bucket* sia proporzionato al numero degli elementi di input. In questa implementazione i bucket sono dieci, e ciò dipende solo da esigenze pratiche perché se fossero stati di più la stampa sarebbe risultata troppo disordinata (ciò non toglie che si può sempre modificare, magari limitando la stampa all'input e all'output senza quella intermedia).
Os	XP
Autore	YuYevon
Posted By	k8
Data Add	February 13, 2009, 2:48 am
Last Edit	Nessuna modifica.
Commenti	0
Voti	0
Voto Medio	0.0
Visite	1110
Visite Uniche	986
Num.Download	79
Download	Click

Stats Beta 1

Spazio Visitatori

Prima di inviare il tuo commento assicurati che: sia in tema con l'articolo e contribuisca alla discussione in corso non abbia contenuti offensivi nei confronti di chicchessia non abbia contenuti che violini le leggi italiane non contenga indirizzi e-mail Nome(Richiesto) : E-mail (richiesta, ma non sarà mostrata ai visitatori) : Sito Internet (opzionale) : Commento (richiesto) :
Vota

Non ci sono commenti.

Tag Cloudbucket sort × STL C++ bucket sort × algoritmo di ordinamento ×

Navigazione

Link

Cerca

sorgenti.big-bug.net,sottodominio di www.big-bug.net,nasce nel 2008 da un idea di k8 per rinnovare il sito principale.
Offre il download gratutito e senza registrazione di numerosi sorgenti in diversi linguaggi di programmazione.
Buona navigazione.

Non ancora provato il simulatore di gioco winforlife? E le estrazioni winforlife già controllate?