Sorting Algorithms Overview

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.

The source material presents this 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.

Unsorting is closely related to sorting. Both work on the same data structure and both rearrange its elements. 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.

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 the mechanism is to run it on paper. Work with a four-value array: 7, 2, 5, 9 at indexes 0 through 3. At the start, the whole array is the unfinished part. Each pass does three things: pick one index in the unfinished part at random, exchange that value with the value at the last index of the unfinished part, and then treat that last index as settled so the unfinished part shrinks by one. The random picks below are chosen by hand for illustration, since the source does not fix any particular sequence.

Read the diagram as a snapshot. Index 3 is now settled because it sits at the end of the unfinished part and will not be chosen again. Indexes 1 and 3 changed in this pass, and the values at indexes 0 and 2 stayed where they were. The next pass will draw only from indexes 0 to 2, so the value 2 can never be picked again.

The one decision that matters most at each step is the range the random pick is drawn from. The correct range is the unfinished part, and that range must shrink after every pass. In the trace above, pass one drew from indexes 0 to 3, pass two from indexes 0 to 2, and pass three from indexes 0 to 1. The settled positions at the end of the array were never part of any later choice.

The range has to be right for two reasons. First, the shuffle must place each value exactly once, which only happens if each settled position is fixed and left alone. Second, the number of passes must be finite, which only happens if the unfinished part gets smaller each time. A range that is too wide breaks the first reason, and a range that never shrinks breaks the second.

The source identifies two main sources of error when building a shuffle. Both come from changing too little, or from changing the wrong thing.