cf.completefrontend
ARRAYS & HASHING · CORE

Fisher-Yates shuffle

Shuffle an array fairly in one pass by swapping each position, from the back, with a random position at or before it.

Time O(n)Space O(n) for the copy4 practice problemsStep-through picture

The idea

Shuffling means putting items in a random order where every possible order is equally likely. That last part is easy to get wrong: many quick tricks favor some orders over others.

The Fisher-Yates shuffle (also called the Knuth shuffle) goes from the last index down to index 1. At each index i, it picks a random index j from 0 to i, including i itself, and swaps the items at i and j. After that, position i is final and never touched again.

Each step picks uniformly from the items not yet placed, so every order comes out with exactly the same chance. The code takes a random function so tests can pass in fixed numbers and get the same shuffle every time.

An everyday example

Drawing names from a hat

To put people in a random speaking order, write each name on a slip and put the slips in a hat. Without looking, draw a slip: that person speaks last. Draw again from the slips that are left: that person speaks second to last. Keep going until the hat is empty. Each draw is fair because every remaining slip is equally likely to come out.

How the example maps to the code
In the exampleIn the code
The slips still in the hatresult[0..i], the part not yet placed
Drawing one slip at randomj = Math.floor(random() * (i + 1))
Putting that person in the next speaking spot from the endSwapping result[i] and result[j]
One fewer slip in the hati--

From the slow way to fisher-yates shuffle

  1. A fair shuffle is like drawing names from a hat: pick one of the remaining items at random, put it next in line, and remove it from the hat. Done with an array and splice, each removal shifts the items after it, so n draws cost O(n²).
  2. The drawing is fine; only the removal is slow. Instead of cutting the chosen item out, swap it with the last item still in the hat, and make the hat one slot shorter. A swap takes constant time.
  3. Running this from the back, positions after i are final and positions 0 to i are the hat. Pick j from 0 to i, including i itself, because the item already at i must have the same chance to stay there as any other item has to move there.
  4. Each step draws one random number and makes one swap, and the hat shrinks by one. When one item is left, it's already in place. That loop is the Fisher-Yates shuffle.

How it works

  1. Copy items into result so the input isn't changed.
  2. Start i at the last index and count down to 1.
  3. Pick j = Math.floor(random() * (i + 1)), a whole number from 0 to i.
  4. Swap result[i] and result[j]. j may equal i, leaving the item where it is.
  5. Position i is now final; move to i - 1.
  6. Return result.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function shuffle(items, random = Math.random) {
  2. const result = [...items];
  3. for (let i = result.length - 1; i > 0; i--) {
  4. const j = Math.floor(random() * (i + 1));
  5. const temp = result[i];
  6. result[i] = result[j];
  7. result[j] = temp;
  8. }
  9. return result;
  10. }

How fast it is

TimeO(n)
Extra memoryO(n) for the copy

One pass with one random number and one swap per position. Shuffling the input in place instead would need only O(1) extra space.

  • Best caseO(n)

    Every input takes n - 1 steps. Draws that keep items in place save no work.

  • Average caseO(n)

    One random number and one swap per position.

  • Worst caseO(n)

    No input is slower. Long arrays just take proportionally longer.

Common mistakes

  • Using Math.floor(random() * i), which never lets an item stay put. That gives a different algorithm (Sattolo's), not a fair shuffle.
  • Picking j from the whole array at every step. It looks random but some orders come up more often.
  • Shuffling with sort(() => Math.random() - 0.5), which is biased and can differ between browsers.
  • Using Math.random for anything secret, like tokens. Use crypto.getRandomValues for security.

When to use it

Look for these clues in a problem:

  • The problem asks for a random order, a random permutation, or to shuffle.
  • Every order must be equally likely (fair shuffling).
  • You need to pick k random distinct items (run only k steps).
  • Tests need a repeatable shuffle, so the random numbers are given as input.

Check yourself

Answer each one in your head first, then open it.

How many different sequences of j values can a 5-item shuffle produce, and how many orders are there?

5 × 4 × 3 × 2 = 120 sequences, and 5! = 120 orders. Each order comes from exactly one sequence.

Why random() * (i + 1) and not random() * i?

random() * i never picks i, so the item at i can never stay put. That is Sattolo's algorithm, which only makes single-cycle orders.

Why can the loop stop at i = 1?

After placing position 1, the hat holds one item at index 0, and it can only go in one place.

In the trace, which item ends at position 4, and at which step was that decided?

S, at the first step, when j was 3. Position 4 is never touched after that.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: before the step for i, positions i + 1 to the end are final, and positions 0 to i hold the remaining items, the hat. The step picks each hat item with the same chance, 1 / (i + 1), puts it at i, and shrinks the hat. The rule holds for the next step.

Count the possible runs. The first step has n equally likely choices of j, the next has n - 1, and so on down to 2. That makes n × (n - 1) × ... × 2 = n! equally likely runs. Each run gives a different order, and every order can be made by exactly one run, so each of the n! orders has the same chance, 1 / n!.

The loop ends at i = 0, when the hat has one item. Fairness also depends on random(): it must return values in [0, 1) spread evenly, so that Math.floor(random() * (i + 1)) hits each of 0 to i equally often. Math.random is fine for games and layouts, but its limited internal state can't reach every order of a 52-card deck, since 52! is far larger.

Going deeper

3 more ideas

Why every order is equally likely

The last position gets each of the n items with chance 1 / n. The next position gets each of the remaining n - 1 items with chance 1 / (n - 1), and so on. So any particular order happens with chance 1 / n times 1 / (n - 1) times ... times 1 / 1, which is 1 / n!: the same for every one of the n! possible orders.

Common unfair shuffles

items.sort(() => Math.random() - 0.5) is not fair: sorting assumes the comparison is consistent, and the result favors some orders, differently in each browser. Picking j from the whole array (0 to n - 1) at every step is also unfair, because it makes n^n equally likely paths, and n^n can't be split evenly among n! orders.

Partial shuffles and repeatable tests

To pick k random items, run only k steps (or run it from the front, swapping i with a random index from i to n - 1) and take those k positions. For tests and replays, pass in a list of fixed random numbers or a seeded generator, so the same input always gives the same shuffle.

Work it by hand

Every step in a table, with why

Shuffle five letters using four given random numbers, so the result can be checked by hand.

items = ["P", "Q", "R", "S", "T"], random numbers 0.7, 0.2, 0.6, 0.45

Stepirandom()jSwapresult afterWhy
140.7floor(0.7 * 5) = 3T and S[P, Q, R, T, S]All five items are in the hat. S lands at position 4, which is now final.
230.2floor(0.2 * 4) = 0P and T[T, Q, R, P, S]The hat is indexes 0 to 3. P moves to position 3 for good.
320.6floor(0.6 * 3) = 1Q and R[T, R, Q, P, S]The hat is indexes 0 to 2. Q is placed at position 2.
410.45floor(0.45 * 2) = 0T and R[R, T, Q, P, S]Two items are left, and the draw picks index 0, so they trade places.
50---[R, T, Q, P, S]i > 0 is false, so the loop stops. The one item left, R, is already in place.

The shuffle is [R, T, Q, P, S], from 4 random numbers and 4 swaps. The same four numbers always give the same order, which is why the code takes random as a parameter.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Fisher-Yates shuffleO(n)O(n)The standard fair shuffle: one pass, one swap per item.
Sort by random keysO(n log n)O(n)You're sorting anyway, as in a database query. Give each item a random number once, then sort by it.
Draw from a hat with spliceO(n²)O(n)Rarely: it's fair but slow, because each removal shifts the items after it.
Sort with a random comparatorO(n log n)O(1)Never: sort(() => Math.random() - 0.5) is biased, differently in each browser.

Extra memory: O(n) for the copy that the code returns. Shuffling items itself instead needs only O(1) extra space.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Fisher-Yates shuffle and the other approaches, on a scale where each line up is 10 times more steps.
  • Fisher-Yates shuffle O(n)
  • Sort by random keys, Sort with a random comparator O(n log n)
  • Draw from a hat with splice O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Fisher-Yates shuffle101,0001 million
Sort by random keys339,96620 million
Draw from a hat with splice1001 million1 trillion
Sort with a random comparator339,96620 million

Inputs that need care

5 tricky inputs
An empty list: items = []
i starts at -1, the loop never runs, and it returns [].
One item: items = ["x"]
i starts at 0, so i > 0 is false at once. It returns ["x"] without using any random numbers.
Repeated items: ["A", "A", "B"]
Positions are still shuffled fairly. Some of the 6 runs give orders that look the same, so B lands in each position with chance 1 in 3.
A random function that can return exactly 1
j would be i + 1, outside the hat, and the swap would undo a final position. A custom random must return values below 1.
Many items with a weak random source
If the generator has fewer internal states than there are orders, some orders can never appear. For shuffles that must be unpredictable, use crypto.getRandomValues.

Variations and follow-ups

Twists interviewers add

Inside-out shuffle

Build the shuffled copy while reading the input from the front: for each i, pick j from 0 to i, copy result[j] to result[i], and put items[i] at result[j]. It gives the same fair result and works when items arrive one by one.

Sattolo's algorithm

Picking j from 0 to i - 1, never i, produces only orders that form a single cycle. No item stays in place, which suits a gift-exchange draw where nobody may get their own name. It is not a fair shuffle of all orders.

Unbiased secure numbers

With crypto.getRandomValues, you get whole numbers, not fractions. Taking value % (i + 1) favors small results slightly, so redraw when value falls in the last incomplete block of i + 1 values.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "shuffle", "random permutation", "every order equally likely", or "random playlist".
  • Explain the hat: "positions after i are final; I pick a random item from the part that's left and swap it into position i."
  • Show a test with fixed random numbers passed as random, so the expected output is known. Then argue fairness with the n! count.
  • The usual follow-up is "why not pick j from the whole array every time?". Answer: that makes n^n equally likely runs, and n^n can't be split evenly among n! orders, so some orders come up more often.

Where frontend code uses it

The same idea in real UI code
  • Shuffling quiz questions, flashcards, or a music playlist in the browser.
  • Randomizing the order of answer options so the correct answer isn't always in the same spot.
  • Writing repeatable UI tests and Storybook stories by passing a fixed list of random numbers or a seeded generator.

Related algorithms