Overview
Fisher-Yates walks backward through a list and swaps each item with a random earlier item, including itself.
FoundationSource checked
Fisher-Yates Shuffle
Randomly shuffles a list so every ordering is equally likely.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Beginner
- Family
- Random Permutation
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Knuth Shuffle
Core Concepts
uniform random indexin-place swapremaining suffixunbiased permutationrandom drawuniform permutationin-place updaterandom permutation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use it when every permutation of a finite list should be equally likely.
- Use it for shuffling cards, randomized test cases, or sampling without replacement.
- Use a seedable random source when results must be reproducible.
When Not to Use
- Avoid it when the random source is biased or unsuitable for the application.
- Avoid sort-by-random-key substitutes when unbiased permutations matter.
- Avoid it for cryptographic shuffling unless using a cryptographically secure random source.
What It Does
- Randomly permutes a list
- Uses one random choice per position
Use Cases
- Card shuffling
- Randomizing test order
- Sampling without replacement
Inputs
- Array or list
- Uniform random number source
Outputs
- Shuffled array or list
Key Formulas (1)
Swap index
j = random integer in [0, i]
j = random integer in [0, i]Chooses an unbiased partner for the current suffix position.
Pseudocode
- 1.Start at the last index
- 2.Choose a random index from zero through the current index
- 3.Swap the current item with the random item
- 4.Move one position left
- 5.Repeat until the start is reached
Canonical Example
- Input
- items = [A, B, C], chosen indexes while moving right-to-left = [1, 0]
- Output
- [C, A, B]
- Explanation
- The algorithm swaps each current position with a uniformly chosen position from the unshuffled prefix.
Implementation Notes
- For index i moving downward, choose j uniformly from 0 through i.
- Swap items i and j in place.
- Keep the random-number source injectable for testing.
Common Pitfalls
- Choosing the random index from the wrong range.
- Using modulo reduction in a way that biases random indexes.
- Forgetting that reproducible tests need explicit seeding.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow each position swapping with a random earlier position.
Step 1 of 5: Start at the last index
array-shuffleNotes
The inclusive random-index range is the detail that preserves uniformity.
Sources (1)
What each reference supports for this entry.
The Art of Computer Programming, Volume 2
BookRandomness reference for Fisher-Yates Shuffle's uniformity argument, recurrence, or random-selection procedure.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageDepends onLinear Congruential Generator
Fisher-Yates requires a source of random indices.
Conceptual neighborReservoir Sampling
Both sample without bias from discrete items.
Related Algorithms
Tags
RandomnessShuffleIn Place