Arrays and Index Positions

Most of the sorting techniques you have studied start from a jumbled collection and produce an ordered one. This article turns that goal around. Instead of asking how to arrange values from smallest to largest, we ask how to arrange them so that the final order is unpredictable. The everyday picture is a deck of playing cards. Before a game, the cards are mixed so that no one can guess what comes next. That mixing is the problem this article solves, and it is the reverse of the problem sorting solves.

Unsorting is closely related to sorting. Both work on the same data structure, an array, and both rearrange its elements by moving them between index positions. The difference lies in what decides each move. A sorting algorithm uses the values themselves to decide where things belong. An unsorting algorithm uses chance to decide where things go. Keeping that difference in mind will help you understand every later step in this article.

The source material presents unsorting as a related problem that is less common than sorting but interesting to study in its own right. Because it uses the same kind of array and the same kind of step-by-step movement that sorting uses, it is a good way to check whether you understand how those movements work.

A good shuffling algorithm is built on the same skeleton as selection sort. Recall how selection sort works: it repeatedly looks through the part of the array that is not yet finished, finds the biggest item, and moves that item to the end of the unfinished part. Each pass fixes one more position at the end, and the unfinished part shrinks until nothing is left.

The shuffle keeps this skeleton and changes exactly one decision. Where selection sort chooses the biggest item, the shuffle chooses an item at random. The chosen item is then moved to the end of the unfinished part, just as selection sort moves its biggest item. Because the structure is the same, every pass still settles one position and the work still shrinks from one pass to the next. Only the choice of which item to settle has changed.

The best way to see how the shuffle works is to step through a small array. The values below are invented for this walkthrough, and the random choices are chosen by hand to show the mechanics. In a real shuffle, the choice at each pass would come from a random source. Start with the array [4, 1, 3, 2] at index positions 0 through 3. Every position is unfinished at the start.

The index view below shows the state after pass one. Each position is listed with the value it holds, so you can see exactly which values moved. Index 1 changed from 1 to 2, and index 3 changed from 2 to 1. Index 3 is the settled position, because the value there has been moved to the end of the unfinished part.

Notice that the unfinished part gets smaller after each pass, and this is what makes the shuffle terminate. Once a value has been moved to the end of the unfinished part, it is treated as settled and is not chosen again. If the algorithm kept choosing from the whole array, a value could be picked repeatedly, and the work would never clearly finish. Shrinking the range is therefore part of the design, not an optional detail.

The source material identifies two broad sources of error in shuffle design. Mistakes usually come from choosing from settled values or from keeping the sorting rule unchanged. The items below describe each error and how to avoid it.