Fisher-Yates shuffle

(algorithm)

Definition: Randomly permute N elements by exchanging each element e_i with a random element from i to N. It consumes Θ(N log N) bits and runs in linear time.

Generalization (I am a kind of ...)
perfect shuffle, permutation.

Note: The algorithm can be viewed as a reverse selection sort. It is described in some detail as algorithm P in [Knuth98, vol. 2, p 145].

Author: PEB

Implementation

Ben Pfaff's answer to how can I shuffle the contents of an array? (C). An implementation (Java) due to Sedgewick and Wayne, including an explanation of unfair shuffle algorithms (search for Shuffling).

More information

R. A. Fisher and F. Yates, Example 12, Statistical Tables, London, 1938.
Richard Durstenfeld, Algorithm 235: Random permutation, CACM 7(7):420, July 1964.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 19 December 2005.
HTML page formatted Mon Sep 11 09:46:03 2006.

Cite this as:
Paul E. Black, "Fisher-Yates shuffle", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 19 December 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/fisherYatesShuffle.html