Visualizer CodeViz · Algorithms, visualized

Part I · Elementary sorts · week 2

Knuth shuffle

Swap each item with a random earlier one. The range you draw from is the whole algorithm: get it wrong and the shuffle is subtly biased.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(n)
randomnessuniform over all n! orders
in placeyes
used byquicksort's guarantee

Reference: Sedgewick & Wayne, §2.5; Fisher–Yates 1938.

Knuth shuffle in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import random

def knuth_shuffle(a):
    # INVARIANT: after iteration i, a[0..i] is a uniformly random
    # permutation of the items that started in a[0..i].
    for i in range(1, len(a)):
        r = random.randint(0, i)          # in [0, i] -- NOT [0, n-1]
        a[i], a[r] = a[r], a[i]
    return a

Why it works

Why [0, i] and not [0, n−1]

Drawing r from [0, i] gives exactly n! equally likely outcomes: i + 1 choices at step i, and 2·3·4⋯n = n!. Drawing from the whole array instead gives nn−1 outcomes, which is not divisible by n! — so some permutations are strictly more likely than others. The code is one character different and the distribution is wrong.

This bug shipped: an online poker site once shuffled this way, and players could deduce the deck. Uniformity is a correctness property, not a nicety.

The invariant

After iteration i, the prefix a[0..i] is a uniformly random permutation of the items that started there. Each step extends that guarantee by one position, so when the loop ends the whole array is uniformly shuffled. Note the swap is with an earlier or equal index — the algorithm never disturbs the part it has not reached.

Where the course needs it

Quicksort's n log n guarantee is probabilistic and depends on this shuffle: it converts an adversary's worst-case input into a random one, making the quadratic case astronomically unlikely. Skip the shuffle and quicksort is quadratic on sorted input — which is exactly the input real data most often arrives in.

Testing randomness

You cannot eyeball uniformity. Shuffle a 3-element array a million times and count each of the 6 orders — all six should be within noise of one sixth. That test catches the [0, n-1] bug immediately; reading the code often does not.

What to try in the animation

The seed makes the shuffle reproducible so you can step through it. Change it for a different permutation.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Knuth shuffle in the player →

The rest of Elementary sorts