-A A +A

Algorithms In Action - Heapsort

Primary tabs

Collection:   AlgoViz
Source: http://algoviz.org/node/493
Format:   Java Applet

Recommendation: Recommended.
Description: The application works well and shows nice, intuitive visualizations. The application launches four different windows that can be a positive or negative thing. It may make it easy to handle each window separately or alternatively it can cause difficulties for overall attention. There are Explanation window, Algorithm window (showing program code), 'AIA: Quicksort window' (for showing animation) and Help window. The general impression about user interface is good. In the Algorithm window the user can see the program code either in real program code mode or in natural language mode. It is beneficial to have lot of comments available for observing the process. By clicking parts of the program code it is possible to get some explanation in natural language to Explanation window. Parts of pseudocode can be opened or closed, which changes the stepsize of the visualization. The Help window offers advice about what the user can do with each clickable item in Algorithm window or 'AIA: Heapsort window'. The 'AIA: Heapsort window' shows a set of randomized numbers and right above them vertical bars with varying length that corresponds to the size of each number. In the windows there are also buttons with names Step, Back, Run, Pause and Reset, as well as set of menu controls for fine-tuning. The basic functionality is based on seeing first the vertical bars in a randomized order and step by step the algorithm will arrange the bars into ascending or descending order. Both the tree view and the array view are shown.
Evaluation: Colors are used to show the status of elements. They clearly show the pivot and the partition boundaries and the top and bottom values (unfortunately, these are labeled with the uninformative i and j). It also builds a hierarchy in a second sub-visualization that shows each sub array as it is being sorted, giving a nice picture of how the array is being divided up. For animation control, there is a speed control as well as pause, step and back buttons. There are a number of options for data ' random, sorted, reverse sorted, all equal and user entered. A very nice feature is the ability to pick different pivot choosing algorithms (right, random, middle of three random and middle of three). Unfortunately, the overview doesn't explain this as well as it could. The source code display shows fully commented source code for the algorithm. Unfortunately, this proves less useful when the visualization is actually running. A nice feature is that the code is instrumented to be foldable - replacing a collection of steps (like a swap) with a high level piece of pseudocode. Even better, this affects to visualization - when steps have been abstracted away they happen atomically in the visualization. The quiz is less useful. It can't be used in conjunction with the visualization and mostly asks questions that can be answered (or perhaps even have to be answered) as the result of memorizing some of the overview explanation rather than as a result of working with the visualization. Also, while it provides feedback after each question, it doesn't give any sort of final assessment of the overall score. There are some inconveniences with the way that the interface is broken into separate window, which may stem from the lack of Java tools available when this applet was originally written. Rather than using panes, each part of the tool ends up in its own window. This is cluttered and hard to manage. Things like the explanation window are easy to lose or overlook. The code folding is implemented with what looks like an abused file browser as each abstract line is decorated with a folder icon. The tool for changing the highlight color consists of three tiny custom RGBsliders and the custom data entry pane has to been seen to be believed. In addition, there seems to be a bug in the quiz code. There are actually three 'modes': the normal one, one called 'self test' and the quiz. When I tried 'self test' the only thing that seemed to happen is that the overview window was hidden. Even odder, when I went to the quiz mode, the overview came back (particularly startling as the answers to most of the questions were in that window).

Creator: Linda Stern  Harald Sondergaard  
Publisher: University of Melbourne  
Subject:   heapsort  N log N sorts  
Language: english  
Audience:   Educator  Learner  Professional/Practitioner  Researcher  
Education Level:   Higher Education  
Education Material Type:   Instructional Material  Tool  
Relation: Algorithms In Action  
ACM CCS 2012:
Theory of computation Design and analysis of algorithms Data structures design and analysis Sorting and searching