Implementazioni di algoritmi/Bucket sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m ha spostato Bucket sort a Algoritmi/Bucket sort: convenzioni di nomenclatura (sottopagino correttamente) |
sistemo link, aggiungo template |
||
Riga 1:
{{
Il '''Bucket sort''' è un [[w:algoritmo di ordinamento]] per valori numerici interi con [[complessità]] lineare O(n+m), dove n è la lunghezza dell'array e m è il valore massimo che può esserci nell'array. Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è piccolo rispetto a n o comunque comparabile, altrimenti risulterebbero più veloci altri algoritmi.
L'algoritmo è semplice ed intuitivo: si prepara un array C di dimensione pari a m (cioè al valore massimo che può essere nell'array) con C[i] che rappresenta la frequenza dell'elemento i nell'array di partenza A. Si visita l'array A aumentando l'elemento di C corrispondente. Dopo si visita l'array C in ordine e si scrivono su A, C[i] copie del valore i.
==Spiegazione astratta==
L'algoritmo come detto in precedenza usa un [[w:array|vettore]] ausiliario( da ora in poi ''Y'') dove la t-esima cella contiene la frequenza dell'elemento t nel [[w:array|vettore]] di input (da ora in poi ''X'').
Per fare un esempio, se ''X'' fosse cosi strutturato:
Riga 37:
==Analisi dell'algoritmo==
La complessità del Bucket Sort è ''O(n + m)'' infatti la [[w:Teoria_della_complessit%C3%A0_algoritmica|complessità]] per inizializzare il vettore Y e leggerlo per ricostruire X è ''O(m)'', mentre la [[w:Teoria_della_complessit%C3%A0_algoritmica|complessità]] del terzo ciclo for è ''O(n)''.
Da questo possiamo capire l'utilità del Bucket Sort: infatti se m = ''O(n)'' allora la [[w:Teoria_della_complessit%C3%A0_algoritmica|complessità]] totale dell'algoritmo è ''O(n)''.
==Implementazioni==
===[[C (linguaggio)|C]]===
<source lang="C">
Riga 86:
</source>
[[Categoria:Algoritmi di ordinamento]]
| |||