Otras soluciones aportadas dependen de una llamada a sort()
. Si el lenguaje con que trabajas tiene implementada esa función, puede ser una buena solución. Sin embargo si trabajas en lenguajes que no disponen de sort()
, tendrías que implementar tú una, lo que complicaría innecesariamente el problema. Además esta solución tendría complejidad mayor de O(N), pues es necesario primero un bucle de complejidad O(N) para generar los números aleatorios y luego otro de complejidad O(N·log(N)) para ordenarlos (suponiendo que se usa el algoritmo de ordenación QuickSort, que es uno de los más óptimos posibles y el que está implementado en la mayoría de los lenguajes)-
Se me ha ocurrido otro algoritmo sencillo que no depende de sort()
y que tiene complejidad O(N), que es el siguiente:
- Sea N la longitud del array menos 1
- Repetir mientras N > 0:
- Generar un número aleatorio R entre 0 y N (ambos inclusive)
- Intercambiar los elementos en posición R y N
- Decrementar N
El algoritmo parte de la siguiente idea. Imagina que tienes un mazo de cartas real. Una forma muy simple de mezclarlas sería ir tomando cartas al azar del mazo y dejándolas sobre la mesa, una encima de otra. Una vez todas están en la mesa, estarán mezcladas. En cada "iteración" de este bucle te van quedando menos cartas en la mano.
Una simulación literal de esto sería tomar un elemento al azar de la lista y llevarlo a otro array (la "mesa" donde se dejan las cartas). Después, para completar la simulación de que se ha extraido una carta, el array original debe "menguar", lo que se implementaría desplazando una posición atrás todos los elementos del array original a partir del elemento elegido.
El algoritmo que propongo se ahorra el desplazamiento, moviendo en su lugar al hueco el último dato de la lista. Esto va cambiando la lista original cada vez que se elige un elemento, pero lo mismo nos da que esté desordenada con respecto a su estado inicial ¡estamos barajando! También nos ahorramos la segunda lista usando como "mesa" la propia lista, en sus posiciones finales. Es por tanto eficiente en tiempo y en memoria, al usar una única lista.
Una implementación (por ejemplo en Python) sería:
import random
def barajar(lista):
N = len(lista)-1
while N > 0:
R = random.randint(0,N)
aux = lista[R]
lista[R] = lista[N]
lista[N] = aux
N-=1
# Demo
lista = list(range(20)) # numeros del 0 al 19 ordenados
barajar(lista)
print(lista)
Produce por ejemplo:
[3, 5, 14, 6, 12, 18, 11, 15, 7, 4, 2, 8, 17, 9, 1, 0, 19, 16, 10, 13]
Edición
Tras investigar un poco descubro que (obviamente) el algoritmo se le había ocurrido antes a otro :-) Concretamente, se trata del algoritmo de Fisher-Yates, popularizado por Donald Knuth en su libro The art of computer programming. Parece ser que es un algoritmo muy usado, por ser óptimo en espacio y en tiempo de ejecución.