Recommendation

Recommended

Link

http://dbs.mathematik.uni-marburg.de/research/projects/dsn/

Delivery Method

Java Application

License

Unavailable

Language

English

Author

Jens-Peter Dittrich; Jochen van den Bercken; Tobias Schäfer; Marcus Klein

Institution

Phillips-University of Marburg

Project

Data Structure Navigator

RelationshipToProject

PartOfProject

Works

Yes

Description

This java application visualizes quick sort amongst several other sorting algorithms. It does not permit user input, instead has a canned data set. It sorts letters and not numbers. The active elements (elements being compared) are highlighted by blue so as to differentiate from the inactive elements which are cream. It lets the users choose the operations to visualize namely, Divide, sort, swap, unsort and reverse. It provides the option of viewing as a continuous animation or a step wise animation controlled by the user. At any point of time, the user can prefer to move on to the end of the visualization by clicking on the complete button. The screen has a right bottom pane displaying the history of operations (not to be confused with the history of states). After each divide, the sub lists are separated and shown as a tree structure. The pivot variable is displayed on the top left corner at every stage to help the user stay in context. The tool uses one of the more complex pivot choosing algorithms (middle of three). It provides a help feature.

Evaluation

The visualization is fairly intuitive. It does a fair job in explaining the working of the algorithm. The visualization shows quick sort in a hierarchical structure that makes explicit the recursion over sub arrays. This hierarchical presentation is what makes this AV "Recommended". The visualization has user interaction. Once started, the visualization is merely an animation (either continuous or step controlled). The visualization replaces the array with a node labeled with the pivot of that stage in the hierarchical structure. This takes away contextual information and makes it hard for the user to look at past states. The tool uses one of the more complex pivot choosing algorithms (middle of three). This would be a reasonable choice if there was any explanation, but there isn’t. - it frequently swaps two values even when they are identical. Another issue with this tool is that it appears to have just two data sets - one integer and one string (though I was not able to enable the integer set). The string can be randomly scrambled or reversed, though for some reason the authors animated these sequences (there is an option to turn this off, but it is on by default). There appears to be a text entry field, but it seems to be disabled. The user can determine the speed of animations. But the option to control the animation speed is hidden somewhere inside the menu, while a large amount of screen real estate is taken up by a little collection of check boxes that control which aspects of the algorithm are animated. Another large portion of the window is taken up with the “history” panel. Unfortunately, this is just a hierarchical list of items that say “sort”, “swap” or “divide”.

ActivityLevel

Step Control; Animation; Canned Data

GoodFor

Lecture Aid; Self Study

Screenshots

Videos

References

HowToUse

First Visited

2006-09-01

Last Visited

2008-07-16

Last Updated

2000-07-31

Topic

QuickSort

Community

Edit

You may edit this entry if you have an account.