Uma matriz de comprimento n pode conter valores 1,2,3… n^2. É possível classificar no tempo O (n)?

Question

Dada uma matriz de comprimento N. Ele pode conter valores de variando de 1 a n^2 (n quadrado) Ambos inclusivos, os valores são integrantes. É possível classificar essa matriz no tempo O (n)? Se possível, como?

EDIT: Este não é um dever de casa.

Answer 1

Escreva cada número inteiro na base n, ou seja, cada x pode ser representado como (x1, x2) com x = 1 + x1 + x2*n. Agora você pode classificá -lo duas vezes com a contagem, uma vez no X1 e uma vez no X2, resultando na matriz classificada.

Answer 2

Sim, você pode usar Radix Sort com N baldes e dois passes. Basicamente, você trata os números como tendo 2 dígitos na base N.

Answer 3

É possível classificar qualquer variedade de números inteiros com um valor máximo bem definido em O(n) tempo usando um Radix Sort. É provavelmente o caso de qualquer lista de números inteiros que você encontrar. Por exemplo, se você estivesse classificando uma lista de números inteiros de precisão arbitrária, não seria verdade. Mas todos os tipos integrais C têm faixas fixas bem definidas.