Implementazioni di algoritmi/Counting sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m ha spostato Counting sort a Algoritmi/Counting sort: convenzioni di nomenclatura |
sistemo link, aggiungo template indice e interprogetto |
||
Riga 1:
{{
Il '''Counting sort''' è un [[w:algoritmo|algoritmo]] di [w:algoritmo di ordinamento|ordinamento]] per valori numerici interi con [[w:complessità|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 31:
==Implementazioni==
===[[w:C (linguaggio)|C]]===
<source lang="C">
void countingSort(int v[], int dim, int ris[])
Line 52 ⟶ 51:
</source>
===[[w:C++|C++]]===
<source lang="cpp">
void counting_sort(int *nums, int size)
Line 86 ⟶ 85:
</source>
===[[w:Java|Java]]===
<source lang="java">
void countingSort(int[] A)
Line 115 ⟶ 114:
</source>
== Altri progetti ==
{{interprogetto|w=Counting sort|w_etichetta=questo algoritmo}}
[[
{{Avanzamento|100%|4 marzo 2008}}
| |||