Counting sort: differenze tra le versioni

Versione delle 22:03, 4 mar 2008

Versione delle 14:50, 26 mar 2008

Riga 1:

{{S|informatica}}

{{WIP|Baruneju}}

Il '''Counting sort''' è un [[algoritmo di ordinamento]] per valori [[numero intero|numerici interi]] con [[Teoria della complessità computazionale|complessità]] lineare. L'algoritmo si basa sulla conoscenza a priori dell'[[Intervallo (matematica)|intervallo]] in cui sono compresi i valori da ordinare.

== Descrizione intuitiva ==

Il '''Counting sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità]] lineare O(n+m), dove n è la lunghezza dell'array e m è pari a max(A)-min(A)+1 (max(A) e min(A) sono rispettivamenti l'elemento più grande e l'elemento più piccolo dell'array) ovvero è il range dei valori contenuti nell'array. Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è piccolo rispetto a n, altrimenti risulterebbero più veloci altri algoritmi.

L'algoritmo conta il numero di occorrenze di ciascun valore presente nell'[[array]] da ordinare, memorizzando questa informazione in un array temporaneo di dimensione pari all'intervallo di valori. Il numero di

== Complessità ==

Il '''Counting sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità]] lineare O(n+m), dove n è la lunghezza dell'array e m è pari a max(A)-min(A)+1 (max(A) e min(A) sono rispettivamenti l'elemento più grande e l'elemento più piccolo dell'array) ovvero è il range dei valori contenuti nell'array. Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è piccolo rispetto a n, altrimenti risulterebbero più veloci altri algoritmi.

L'algoritmo è semplice ed intuitivo: si calcolano i valori max(A) e min (A) e si prepara un array C di dimensione pari all'intervallo dei valori con C[i] che rappresenta la frequenza dell'elemento i+min(A) 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+min(A).

Riga 29 ⟶ 36:

k ← k + 1

C[i] ← C[i] - 1

== Bibliografia ==

* {{cita libro| Thomas | Cormen | Introduction to Algorithms | 1998 | The MIT Press | Cambridge, Massachussetts | coautori=Charles E. Leiserson, [[Ronald Rivest]]| capitolo=Sorting in Linear Time | ed=20 }}

== Altri progetti ==