sort array de tamaño n

Question

si una matriz de tamaño n tiene solo 3 valores 0, 1 y 2 (se repite cualquier cantidad de veces), ¿cuál es la mejor manera de ordenarlos? lo mejor indica complejidad considerar el espacio y el tiempo la complejidad tanto

Answer 1

Contar las ocurrencias de cada número y luego llenar la matriz con los conteos correctos, esto es O(n)

Answer 2

sonido es muy parecido a la bandera nacional holandesa Problema de Dijkstra.

Si necesita una solución que no utiliza el conteo, echa un vistazo a http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Answer 3

solución al estilo de C no probado:

int count[3] = {0, 0, 0}; 

for (int i = 0; i < n; ++i) 
    ++count[array[i]]; 

int pos = 0; 
for (int c = 0; c < 3; ++c) 
    for (int i = array[c]; i; --i) 
     array[pos++] = c; 

Answer 4

Haskell dos forro:

count xs = Map.toList $ Map.fromListWith (+) [ (x, 1) | x <- xs ] 

countingSort xs = concatMap (\(x, n) -> replicate n x) (count xs) 

> countingSort [2,0,2,1,2,2,1,0,2,1] 
[0,0,1,1,1,2,2,2,2,2]