This applet visually demonstrates the use of quicksort in programming. View the applet in the Applet section below. The usage of the applet is described in the following Usage section. For those interested, the Display and design of the applet are also described.
Usage of the applet follows two stages. The first stage is to populate the array with elements to be sorted, the second is to step through and visualize the actual sorting.
When you first start the demonstration (or after you have reset it), only two options are available, Random and Add Clicking random will generate 12 random values to be sorted. Clicking add will prompt for a single value to be inserted in the next Array position. You can click Add repeatedly to add up to 12 values. Once you have clicked Add once, the random button is still available if you wish to overwrite your selections with random values.
Once you have added two or more values (through Add or Random), the Sort button becomes active. You can sort the array as long as there are values in it. Clicking the Sort button disables the Add and Random buttons, and enables the Step and Autostep buttons. You can now use these buttons to step through each line of the sort algorithm, viewing results as you go.
At any time during the populating or sorting phases, you can click the Reset button to reset the display and begin adding values again.
As with previous applets, the display will be divided into three areas, one for input, one for Pseudocode, and one for visualization. The input area will contain the Step, Autostep, Add, Random, Sort , and Resetbuttons.
The Pseudocode area will contain the Quicksort functions.
The visualization area will display the array indices and values. During the population phase, the array will only be updated for each addition (as the demo is not meant to demonstrate inserting into an array -- a trivial operation). During the sort phase, the array visualization will be much more interesting. The pivot will be shown in red, the portion of the array currently being sorted will be shown in blue, and any indicies that are currently being swapped will be shown in green (swapped indices blink green and yellow before being swapped). Array elements not currently of interest (already sorted, or yet to be sorted) are shown in grey with a black border.
The design is fairly consistent by this time. In this case,
the pseudocode can easily be stored in a single Pseudocode,
eliminating the need for a ProgramPanel.
There will be a single stepper (as in the Recursion
example) that steps through the code by recursively
calling internal methods. These methods will update
the display in a custom ArrayPanel.
Here is the pseudocode:
void qsort(int[] array, int i, int j) {
int pivotindex = (i+j)/2
array.swap(pivotindex, j)
int k = partition(array, i-1, j, array[j])
array.swap(k, j)
if ((k-i) > 1)
qsort(array, i, k-1)
if (j-k) > 1)
qsort(array, k+1, j)
}
int partition(int array, int l, int r, int pivot) {
do {
while (array[++l] < pivot);
while (r != 0 && array[--r] > pivot);
} while (l < r)
array.swap(l, r)
return l
}