Randomization in Algorithms

A shuffling algorithm aims to put the elements of an array into a random order, with the typical case being shuffling a deck of cards.

Programming

A Deck of Cards as the Model

Most of this chapter has been about putting the elements of an array into a particular order, such as smallest to largest. This section turns that goal around. Instead of asking for a specific order, the question is how to put the elements into a random order. This problem is much less common than sorting, but it is a useful companion to it, and it is worth studying because it reuses a familiar structure.

The standard picture for this problem is shuffling a deck of cards. A shuffled deck is one in which no card's position can be predicted from the order it started in. Keep that picture in mind: the array plays the role of the deck, and the algorithm's job is to rearrange it so that the final order is unpredictable.

Changing the Goal from Order to Randomness

A sorting algorithm and a shuffling algorithm both rearrange the items of an array, so it is easy to confuse them. The difference lies in what the final arrangement is supposed to satisfy. A sort is judged by whether the items end up in a specified order. A shuffle is judged by whether the final order is unpredictable, so there is no single correct output to aim for.

Aspect	Sorting algorithm	Shuffling algorithm
Goal	Place items in a specific order, such as smallest to largest	Place items in a random order
What decides each choice	The values in the array, such as the largest remaining item	Chance; the value of the item plays no role
Target of the result	A particular fixed arrangement	An arrangement no card's position can be predicted from
Same input run twice	Gives the same ordered result every time	Usually gives different orders on different runs
Testing approach	Check the one expected output	Check properties, such as that the items are unchanged as a set

Sorting and shuffling use similar machinery but aim for opposite kinds of final arrangement.

Selection Sort's Skeleton

A good shuffling algorithm is built on the same skeleton as selection sort. Selection sort repeatedly looks over the part of the array that is not yet finished, chooses one item by a deliberate rule, and moves it into place at the end of that part. The shuffle keeps this skeleton but changes the rule used to choose the item. Instead of picking the largest remaining item, it picks a position by chance and moves whatever sits there to the end of the unfinished part.

Before reading the algorithm closely, try a thought experiment. Suppose you keep the selection-sort structure but, every time, you deliberately pick the item at the last unfinished position instead of a random one. The randomness has been removed from the rule. Each item then stays exactly where it started, so the array is not rearranged in any unpredictable way. Removing the random pick turns the shuffle into a fixed rearrangement, which is the central idea of this section.

After one round of the shuffle, which position is finished, and which item was swapped into it? Here the random pick was index 1, which held B, and it was swapped with the last unfinished position, index 3.

The diagram shows the boundary at work. The finished positions are the ones at the right end of the array, and each round extends them by one. Index 3 is now finished and holds B. The unfinished part is now indices 0 through 2, and the next round will work only inside that range. The item that was at index 3 moved to index 1, which is the swap that places the chosen item into its final position.

Following the Control Flow of a Shuffle

The algorithm works in rounds. At the start, the whole array is unfinished. In each round, one item is chosen at random from the unfinished part and moved to the end of that part. Then the unfinished part is treated as one element shorter, and the process repeats on what remains. The loop stops when no unfinished part is left to process.

On each pass through the loop, which range is checked, where does the random pick happen, and when does the unfinished part get smaller?

Follow the control flow from top to bottom. The decision happens at the top of the loop, where the algorithm asks whether any unfinished part remains. If so, the random pick happens next. This is the only step that introduces randomness. The swap that follows, and the shrinking of the unfinished part, are the same bookkeeping that selection sort uses. Once you can point to the single random step, you can see how a deterministic skeleton becomes a shuffle.

An Illustrative Shuffle Function

The source introduces a subroutine that shuffles an array of ints, but the code itself is not reproduced in the material this article draws on. The following version is an illustration written to match the description above. It works from the end of the array toward the front, picks a random position from the unfinished part, and swaps that item into place. Read it as a faithful rendering of the idea rather than as the textbook's exact code.

Code walkthrough

import random

def shuffle(arr):
    for end in range(len(arr) - 1, 0, -1):
        pick = random.randint(0, end)
        arr[end], arr[pick] = arr[pick], arr[end]

deck = ['A', 'B', 'C', 'D']
shuffle(deck)
print(deck)

1
The loop variable end marks the last position of the unfinished part on this round.
2
The pick is drawn from 0 through end, so it never lands on a position already finished.
3
The swap places the picked item at end and moves the item previously at end into the pick position.
4
The loop then treats the array as one element shorter, which happens automatically as end decreases.

range(len(arr) - 1, 0, -1) walks the unfinished-round index from the last position down to 1
random.randint(0, end) chooses the only random position, drawn from the unfinished part
The tuple swap moves the chosen item to the end of the unfinished part

Output

The printed order changes from run to run, for example ['C', 'A', 'D', 'B'] on one run and ['B', 'D', 'A', 'C'] on another.

Because the choice is random, two runs of this function on the same array will usually produce different orders. That difference is the point of the exercise, and it is also why this function cannot be tested by checking one fixed output. A test would instead check properties, such as that the result contains exactly the same items as the input.

Predicting What a Shuffle Preserves

What do you think happens?

After shuffle(deck) runs on ['A', 'B', 'C', 'D'], will the deck still contain exactly the letters A, B, C, and D?

Yes, the same items in a different order
No, some letters may be lost
Only if the random pick happens to be 0

Reveal answer

Answer:

Yes, the same items in a different order

Each round only swaps two positions inside the array, so no item is created or removed. The order is random, but the set of items is preserved. This is the property a test should check.

Mistakes That Stop a Shuffle from Working

A correct shuffle has two requirements that are easy to break. It must choose only from unfinished positions, and it must actually perform the swap for each chosen item. The following mistakes each violate one of these requirements.

Common mistake
Choosing the random position from the whole array instead of the unfinished part
What it looks like
```
pick = random.randint(0, len(arr) - 1) inside the loop, even when end is smaller than that
```
Why it fails
Positions that are already finished can be chosen again, so an item that was placed can be moved out of its settled position.
Do this instead
Draw the pick only from 0 through end, the unfinished range for the current round.
Common mistake
Choosing a random index but never performing the swap
What it looks like
```
pick = random.randint(0, end) with no line that exchanges arr[end] and arr[pick]
```
Why it fails
The source requires that the swap is performed for each chosen item. Without it, the random number is computed and then discarded, and the array is never rearranged.
Do this instead
After choosing the pick, exchange the item at the pick position with the item at the end of the unfinished part.
Common mistake
Treating the random choice as a sort rule
What it looks like
Picking the largest remaining item, as selection sort does
Why it fails
In a sort, values decide the choice. In a shuffle, the value of the item plays no role, so the result is a sorted order rather than a random one.
Do this instead
Let chance pick the position, and ignore the values when choosing.

How does picking the random swap target from the whole array, instead of only the unfinished range, change which positions can be disturbed?

The before-and-after comparison shows the first mistake. When the pick can land on a finished slot, the arrangement is no longer built one settled position at a time, so the shuffle loses the clean structure that selection sort gives it. The source's requirement that a correct shuffle only chooses from unfinished positions is exactly what keeps each finished position safe.

Key Takeaways

A shuffling algorithm aims to put the elements of an array into a random order, while a sorting algorithm aims for a specific order.
A shuffle reuses selection sort's skeleton: it works through the unfinished part of the array and moves one item into place each round.
Randomness enters at a single point, the random pick, so removing that pick turns the shuffle into a fixed rearrangement.
A correct shuffle chooses only from unfinished positions and performs the swap for each chosen item.
Because outputs vary, a shuffle is tested by checking properties, such as that the result contains the same items as the input.