How Python random shuffle works?

Question

How shuffle from random works in Python?

I ask because it works very fast. When I try to write shuffle it works 1 minute for 10^6 element, but Python shuffle does that in 8 sec?

• sloth: Why not just look at the source code?
• ratchet freak: best shuffle algorithm is the fisher-yates shuffle, it runs in O(n) time and is proven to be a perfect shuffle (assuming good random source)
• Martijn Pieters: @ratchetfreak: Python uses Fisher-Yates.
• whatsisname: What is your algorithm for shuffle?
• Cristian Ciupitu: @sloth, by the way, Raymond Hettinger proposed a universal practice of docs linking back to source code back in 2011.

Answer 1

Python's random.shuffle uses the Fisher-Yates shuffle, which runs in O(n) time and is proven to be a perfect shuffle (assuming a good random number generator).

It iterates the array from the last to the first entry, switching each entry with an entry at a random index below it.

The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result...

The modern... solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to O(n), compared to O(n²) for the naive implementation. This change gives the following algorithm (for a zero-based array).

To shuffle an array a of n elements (indices 0..n-1):
 for i from n − 1 downto 1 do
 j ← random integer with 0 ≤ j ≤ i
 exchange a[j] and a[i]