Objectives
-
Develop a Java Applet to visualize the animation of Merge Sort Algorithm.
-
Visualize the structure of the sorting array as bars.
-
Contribute this applet for ICS undergraduate classes as an educational
application.
-
Improve advanced programming skill in developing user interfaces in Java.
Audience
-
Computer Science Instructor,e.g. who teach Data Structure
-
Computer Science students
Requirements and Specifications
Visualisation
-
Use colored bars for numbers in the array and the height of each bar stands
for the number. Orange bars are the group of numbers currently being sorted
in the working array and dark blue for those not in the working array.
-
Use colored bars for numbers in the working array and the height of each
bar stands for the number. Yellow bars are the first half group in the
working array and orange bars are the second half group while the moved
bars use blue color.
-
Visualize execution of the Merge Sort by displaying the source code of
the Merge Sort algorithm and highlight the currently executed line.
-
Show comments for each line of source code
Animation
-
Show the current array numbers by bars.
-
Show the current working array numbers by bars.
-
Show the bar movement from working array to the sorting array.
-
Show the recursive level and the range of the working array.
-
Show the excuting steps of the algorithm on the code panel.
User Interface
-
Use a textfield for user to input unsorted array.
-
Implement some buttons such as "Reset", "Sort", "Step", "Accept" and other
components.
Design
I design the outlook and functionality of my applet as the following parts(see
figure).
-
On the left side of the applet, I would put an animation of Bar movements
which stands for the sorting procedure. I would use different colors to
show the sorted array part and the currently being sorted part and unsorted
part of the array.
-
On the right side of the applet, I would put a Code Panel which will show
the execution steps of the merge sort algorithm. I will highlight the currently
executed line. I will also support comments for each line by mouse click
event.
-
On the top of the applet, I put a textfield for the user to input the array
he wants to be sorted.
-
On the bottom of the layout, I add some buttons to support the execution
functions such as Reset, Sort and Step. I also want to support the granuality
of the execution and change of the execution speed.
____________________________________________________________________________
------------------------------ ---------
| Text field for input array | |Accept |
------------------------------ ---------
____________________________________________________________________________
------------------------------------ |
| | |
| Sorting array | |
| of | | The
| | |
| Colored Bars | |
| | | Source
------------------------------------ |
------------------------------------ |
| | |
| Temporary working array | | Code
| | |
| of | |
| Colored Bars | | Panel
| | |
------------------------------------ |
------------------------------------ |
| | |
| Woring Range at levels | |
| of | |
| Recursion | |
| | |
------------------------------------ |
------------------------------------ |
| Comparison Counter | |
| Assignment counter | |
------------------------------------ |
---------------------------------------------------------------------------
--------- -------- -------- ---------------- -----------
|Reset | | Sort | | Step | | Granualarity | | Speed |
--------- -------- -------- ---------------- -----------
____________________________________________________________________________
Implementation
Applet Layout
-
I use BoarderLayout to implement the layout of the applet itself.
-
The animation of bar movement is in the center of the applet's BorderLayout.
It is implemented by a class inherited from Canvas and I will introduce
later.
-
The user input array is on the north of the applet's BorderLayout and it
is implemented by a textfield.
-
The buttons for "Reset", "Sort", "Step" and the drop-down list box for
Granualarity Choice and the scroll bar for Speed are on the south of the
applet's BorderLayout.
-
The source code panel is on the east of the applet's BorderLayout and obviously
it is inherited from a Panel class.
MergeSort Algorithm
(Source Code : MergeSort.java)
-
Merge sort procedure is implemented as a thread, so that it can pause or
continue when needed.
-
All the bar animation and codepanel synchronization are invoked from mergesort
procedure.
-
It also handles all the component events in the action function.
-
The parsing of the input array in the text field is done in the reset function.
Animation Canvas
(Source Code : AnimationCanvas.java)
-
As the naming shows, the AnimationCanvas class inherits from Canvas class.
-
I implement the most of the animations in the paint function.
-
I implement the bar movement from working array to sorting array in the
move function.
-
I use double buffering to eliminate the flicker phenomena.
Code Panel
(Source Code : CodePanel.java)
-
CodePanel class is inherited from Panel class.
-
It supports synchronical highlighting with the execution of mergesort algorithm.
-
It shows explanation comments for each line when mouse is clicked on each
line.