Counting sort: differenze tra le versioni

Versione delle 21:04, 30 mar 2007

Versione delle 21:29, 13 apr 2007

Riga 5:

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).

==Pseudocodice==

'''Algoritmo in C++'''

countingSort(A[])

//Cacolo degli elementi max e min

max ← A[0]

min ← A[0]

for i ← 1 to length[A] do

if (A[i] > max) then

max ← A[i]

else if(A[i] < min) then

min ← A[i]

//Costruzione dell'array C

* crea un array C di dimensione max - min + 1

for i ← 0 to length[C] do

C[i] ← 0 //inizializza a zero gli elementi di C

for i ← 0 to length[A] do

C[A[i] - min] = C[A[i] - min] + 1 //aumenta il numero di volte che si è incontrato il valore

//Ordinamento in base al contenuto dell'array delle frequenze C

k ← 0 //indice per l'array A

for i ← 0 to length[C] do

valore ← i + min

while C[i] > 0 do //scrive C[i] volte il valore nell'array A

A[k] ← i + min

k ← k + 1

C[i] ← C[i] - 1

==Implementazioni==

'''===Algoritmo in C++'''===

void countingSort(int* A, int lengthA)

Riga 34 ⟶ 61:

}

'''===Algoritmo in Java'''===

void countingSort(int[] A)