Counting sort: differenze tra le versioni

Versione delle 00:54, 18 mag 2009

Versione delle 14:38, 29 giu 2009

Riga 18:

== Complessità ==

L'algoritmo esegue due [[iterazione|iterazioni]], una di lunghezza <math>n</math> (la lunghezza dell'array da ordinare) per il calcolo delle occorrenze dei valori e una di lunghezza <math>mk</math> (pari a <math>max(A)-min(A)+1</math>) per la l'impostazione delle posizioni finali dei valori.: Lala [[O-grande|complessità]] totale è quindi <math>O(n+mk)</math>, dove <math>n</math> è la lunghezza dell'array da ordinare e <math>m</math> è pari a <math>max(A)-min(A)+1</math> (<math>max(A)</math> e <math>min(A)</math> sono rispettivamente 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 mk è <math>O(n)</math>, nel qual caso l'algoritmo è <math>O(n)</math>, altrimenti risulterebbero più veloci altri algoritmi.

==Pseudocodice==