An Animation of Quicksort

The applet below can be used to animate the Quicksort algorithm on initially random data. A lot is going on in this animation, so you may want to run it several times and in slow motion.

First, we will explain how to run the demo, and then we will give a bit of explanation of what it is that you are seeing.

When you click on the button labeled "run" a new window will pop-up with a diagram demonstrating one particular run of the algorithm. If you want to terminate an animation which is still in progress, you can click on the "cancel" button. When an animation is finished, the pop-up window remains displayed unless you explicitly close it (there should be an option "close" under the popup menu "File" which appears near the top-left corner of the pop-up window).

When beginning a run of the algorithm, the following parameters can be specified:

  • N - This value specifies the number of items to be sorted

  • Delay - The applet gives you an animation of the algorithm running. A higher "delay" value will cause the animation to proceed more slowly (the exact amount of delay which you will observe depends greatly on the speed of Java as run on your machine).

  • Magnification - The scale of the graphics can be set to any positive integer.

    • Now, as to what you see when the algorithm is animated. The underlying process is to sort N numbers in an array. The numbers are intentionally chosen to be the values from 1 to N, though initially in a random order. The black squares that you see in most of the animation is a representation of the current contents of the array, where the array goes from left to right, and the height of a square represents the magnitude of the current item in that array location.

    Quicksort operates by first picking a 'pivot' value and then partitioning the original list into two groups, those less than the pivot and those greater than the pivot. This particular implementation uses an in-place partitioning scheme. This is demonstrated in two ways. A horizontal, yellow line is used to denote the magnitude of the chosen pivot value. There are also two "bars" underneath the data points which you will see starting near the sides and sliding towards each other. These are indices in the underlying in-place partitioning scheme.

    Finally, the recursive aspect of the algorithm is shown using a bar graph at the bottom of the animation. A recursive call which is currently active or interupted will be shown as a horizontal red bar, with the width equivalent to the portion of the array being sorted by that call. Therefore, the entire recursive stack is the union of the red bars. Recursive calls which were made but have since completed will be colored black. Thus at the end of the entire process, this provides a record of all past recursive calls

    Michael Goldwasser