Una matriz de longitud N puede contener valores 1,2,3 ... N ^ 2. ¿Es posible ordenar en tiempo O (n)?

Question

Dada una matriz de longitud N. Puede contener valores que van desde 1 a N ^ 2 (N al cuadrado) ambos inclusive, los valores son integral. ¿Es posible clasificar esta matriz en tiempo O (N)? Si es posible, ¿cómo?

Editar:. Esto no es una tarea

Answer 1

Escribir cada número entero en base de N, que es cada X puede ser representado como (x1, x2) con x = 1 + x1 + x2 * N. Ahora puede ordenar que dos veces con contar especie, una vez en x1 y una vez en x2, lo que resulta en la matriz ordenada.

Answer 2

Sí, puede, utilizando Radix sort con N cubos y dos pasadas. Básicamente, se trata a los números que tienen 2 dígitos en la base de N .

Answer 3

Es posible ordenar cualquier matriz de enteros con un valor máximo bien definido en el tiempo O(n) usando un radix especie . Esto es probablemente el caso para cualquier lista de números enteros que encuentro. Por ejemplo, si se ordenar una lista de números enteros de precisión arbitraria que no sería cierto. Pero todos los tipos integrales la C han bien definidos intervalos fijos.