How to randomly sort a sequence efficiently and simply?

Question

Let me ask whether my instant simple algorithm has serious flaws ,for cryptography use, or not. Which is supposed to randomly change the order on a given sequence S[1..n] of the length n. Assume I have a good random number generator random() which returns a random integer in the range [1..n].

while true
  for i in 1..n
    r=random()
    swap S[i] and S[r]

If it does not have serious flaws , when can I finish the while loop? Is there any well known algorithm which also easy to write a computer program?

Thank you in advance.

Answer 1

The algorithm you suggest will not give you uniform distribution, so I guess it's not really what you want. A simple reason is that there are $n^n$ possible and equally probable runs of the algorithm (you choose a random number in $[1..n]$ and you do it $n$ times), while there are $n!$ different permutations. Since $n! \not | \ \ n^n$, it is certain that some permutations will get a larger chance of being chosen (though I don't have a clue which ones these are).

The links provided by Rahul Narain will point you to the right sources.