Ordenar parece ser necesario, sí.
Sin embargo, debido a que los valores ordenados son dígitos consecutivos, puede realizar la ordenación en tiempo lineal utilizando una ordenación por radix.
Si está utilizando una matriz dispersa e inmutable, por ejemplo, el tipo de matriz de Haskell, puede intercalar la lógica de clasificación en la función de permutación inversa.
Soy un poco flojo para proporcionarle un código válido de Haskell, pero se vería así:
foldl (uncurry Array.set) Array.empty $ zip [1..]
Como dije, esta no es la interfaz de Haskell Arrays y probablemente haya tenido algún tipo de vudú equivocado en alguna parte, pero hace el truco en tiempo lineal: cada valor se combina con su índice, y cada par se asigna a Array.set para poner el valor en el índice en el que aparece.
Por ejemplo (y usando su ejemplo), el primer elemento, 3 , se convertiría en (3, 1) ; dada esta tupla, (uncurry Array.set) pondría el valor 1 en el índice 3. El siguiente elemento se comprimiría a (8,2) , lo que da como resultado que 2 se coloque en la 8ª posición. Etc.
- ¿Hay un árbol que pueda agregar y eliminar nodos más rápido que AVL?
- Cómo convertirse en un maestro en programación dinámica
- ¿De qué sirve el hashing en C?
- ¿Diferencia entre algoritmo de relleno de inundación y relleno de límite en gráficos de computadora?
- ¿Cómo funciona el algoritmo de Youtube en términos de tendencias de un video?
