This tutorial illustrates the various sorting algorithms with a fun GUI animation. We'll also give you a quick overview of the mechanisms used to implement this animation.
Run the animation, e.g.,
% cd ~comp212/public_html/01-spring/labs/10/sort_animation
% java SortCtrl
Play around with each algorithm, to make sure you understand
its behavior.
You are not expected to understand all the details of this program. It combines lots of ideas which you've seen before, with a few that you haven't. Even the latter should be fairly straightforward. But, in any case, some of the details will be explained more thoroughly later in the course.
Since it is a GUI application, it uses the MVC pattern, as shown in the following diagram:
The model consists of an array of OCInteger objects
(i.e., ordered, colored integers),
together with a concrete ACompareSorter object
embodying a particular sorting algorithm.
The user can pick among the available algorithms at runtime.
The view is SortGUI. It has a GraphCanvas
where the data array is plotted and animated.
The design of GraphCanvas
is identical to that of BodyPartsCanvas in the hangman
project with the IDrawable object replaced by an
ILambda object to draw on its graphics context.
In this case, the ILambda object is an inner object of
SortCtrl.GraphBarsCmnd within the control.
ILambda is an example of the Command Pattern.
As just mentioned, SortCtrl is the control.
It makes uses of ArrayMapCar to plot each element in the
data array on the GraphCanvas.
It is SortCtrl.GraphCmnd that does all the plotting of the array
elements. SortCtrl holds a Timer
object that periodically tells the GraphCanvas to repaint.
I.e., SortCtrl.GraphCmnd defines what to draw, while
the Timer object dictates when to draw.
Modify the code for
HeapSort and
Heapifier
to sort IOrdered instead of int.
(There is no need to write the code for
Heapifier.siftUp.)
Copy the animation code into your own directory and modify it to add a Heap Sort radio button that runs heap sort.
Doing these modifications shouldn't be too difficult, even though you haven't seen all this code before. Modifying the heap sort is basically just a syntactic change with type casts and such, while modifying the GUI is essentially just duplicating code already there.
The following are some pieces of the implementation that haven't been explained before. This is just a quick overview. The patterns will be explained in more detail in the future.
(Labbies: Cover whatever you have time for.)
We want to plot an array of integers on a JPanel as
rectangular bars with appropriate heights and widths.
The method needed is
Graphics.fillRect(int x, int y, int width, int height)
So, what should x and y be?
It is important to first understand the orientation of the
x-y coordinate system in Java graphics. As in most graphics systems,
the x-coordinate of the graphics context of
the JPanel extends form left to right, while the
y-coordinate extends from top to bottom.
The origin of the coordinate system is at
the upper left corner of the bounding rectangle.
To plot each number A[i] on a JPanel,
we use the simple transformation
y = slope * A[i] + offset to map A[i] to the plane
of the JPanel.
When designing the GUI, we figure out where to place the bars and
how big they should be, and thus can figure out what the slope
and offset should be.
The ILambda interface has one method:
Object apply(Object arg)
It represents the abstraction of a command that is capable of
performing a task given an input and returning an output object.
As hinted by the name ILambda, any object
implementing this interface is the equivalent of an anonymous
function in Scheme.
In this case, GraphCanvas
delegates the task of drawing to its ILambda object.
Similarly, SortCtrl delegates the task for updating the
text area to print the data array to another ILambda inner
object called _appendCmd. SortCntrl.GraphBarsCmnd
and _appendCmd define what to display on the view
SortGUI. But they only appear to
SortCtrl as ILambda objects.
SortCtrl asks these objects to carry out their tasks
(by calling apply) without knowing what the tasks are.
The abstract sorting algorithm, ACompareSorter,
and its concrete variants have no notion of displaying the data array.
After all, the model should not be concerned with the view.
To add new displaying capablity without
modifying any existing code, we apply what is called the Decorator Pattern to
ACompareSorter:
GraphicSorter is called a decorator for
ACompareSorter.
It wraps a concrete ACompareSorter,
the decoree, intercepts all requests to the decoree, and performs
additional work (decoration) before and/or after delegating the
requests to the decoree.
This provides additional functionalities to the decoree
without changing any of its code.