Guida Counting sort

[ptm]

Algoritmi di ordinamento -> Counting sort

Il counting sort è un algoritmo di ordinamento lineare per l'ordinamento di n interi compresi in un certo intervallo.
Dato un array X di n interi compresi in un intervallo [0,k] abbiamo due fasii:

1. Utilizzo di un array Y che contiene k contatori tale che Y="numero di volte che il valore i compare nell'array X" (figura 1)
   [*]Ricostruzione di X; l'indice i di Y è il valore da ricopiare, mentre Y è il numero di copie di i. Si scorre Y da sinistra verso destra e, se Y=c, si copia in X il valore i per c volte (figura 2)
   

Figura 1

Figura 2​

Codice

Una possibile implementazione del counting sort è quella che segue

Perfavore, Entra oppure Registrati per vedere i codici!

 

[Dvdxseo]

Possiamo anche dire che è lineare nella dimensione dell'array se k = O(n), nel senso che la dimensione dell'intervallo dovrebbe essere relativamente piccola rispetto alla dimensione dell'array e che Counting Sort è un algoritmo di ordinamento stabile (cosa importante per l'implementazione di Radix Sort).

Grazie per averlo pubblicato :P