The QuickSort Algorithm

Imagine wanting to watch a sorting algorithm work instead of just reading its output. A list of colors arrives in a random order, and over several seconds you see the colors move into place one step at a time. Each change on screen corresponds to a real step inside the algorithm. This article is about building that kind of animation for a recursive algorithm, using the QuickSort algorithm as the example.

The source gives a concrete program, QuicksortThreadDemo.java, that does exactly this. It animates a recursive QuickSort that sorts randomized colors into a standard spectrum running from red to violet, in slow motion. The Start button becomes a Finish button while the sort runs, which lets the user abort the sort before it finishes on its own.

A recursive algorithm solves a problem by having a method call itself on smaller pieces of the problem. The call stack grows and shrinks as the work proceeds, and the ordering of steps is determined by those nested calls. Each call that is still in progress is waiting for the calls it started to finish before it can complete.

This shape matters for animation. The algorithm is not organized as a list of separate, equally sized steps waiting to be taken one at a time. Its natural structure is one method that keeps calling itself until the job is done. The diagram below shows a simplified picture of this nesting. Each box is a sort call, and the calls below the top one are the smaller pieces it hands off. The top call is the one that started the work, and it cannot finish until the calls it started have finished.

Read the diagram from the top down. Only the innermost call is actively doing work at this moment. The calls above it are suspended in the middle of their own work, each holding its place in the chain. The diagram is a simplified picture of this control flow and does not show every internal call of QuickSort.

Now suppose you want to animate this algorithm with a timer that fires at regular intervals. The natural plan is that each tick advances the algorithm by one step, and the display is updated after each advance. The source states the difficulty directly: it is difficult to break up a recursive algorithm into a series of method calls driven by a timer.

The reason is the shape of the work. A timer naturally produces a sequence of separate calls, each one doing a small piece and returning. A recursive algorithm does not divide itself neatly that way. Its steps are dictated by nested calls, so the program would have to find a way to stop in the middle of a chain of calls, hand control back to the timer, and later resume at exactly the same place. That is what makes the timer-driven approach awkward.

The source's recommended design is to run a single recursive method call inside a thread. This structure is easy to run in a thread. The thread can carry the entire recursion from start to finish while the rest of the program keeps responding. Once the user starts the sort, the thread takes over and runs the recursive QuickSort, and the rest of the program is free to handle other work, such as responding to the Finish button.

The reason to use a separate thread at all is that the display must be redrawn many times while the recursion is in progress. A thread gives the recursive work its own flow of control. Each time the algorithm reaches a point where something visible has changed, the program can update the display. Because the recursion runs in the thread, these redraws happen as part of the sorting process rather than as a separate schedule that must somehow keep up with it.

Each change in the arrangement of colors is one visible event. The source describes the loop like this: each pass through the recursion can change the arrangement, and the display is refreshed as those changes happen. The loop from the decision back to the recursive call stands for the recursion continuing until nothing remains to sort.

The array of colors is the state that connects the two halves of the program. The sorting thread changes that array, and the drawing code reads the array's current contents to decide what to show. Since both use the same array, the picture on screen reflects the array as the recursion leaves it at that moment.