Ever since I saw the first demonstration of Processing.js I have wanted to do something with it. I teach a data structures and algorithms course and one of the annoying things I have found is that many of the animations for showing how these structures work were written in Java and put on a web page as an applet. Many of these animations are also just broken. Thus as a response I thought it would be a good idea to put together a set of algorithms animations that didn’t need any plugins.
I started putting together a small bubble sort animation about a year ago. I liked the way the way the final animation looked but I didn’t like the way the code looked and felt. It was really hacky and not very good. Definitely not extendible for other algorithms. About a week ago I decided to restart that effort. I thought about what would actually be necessary to do general algorithms and data structure animations. I rewrote the code (you can get it here: https://github.com/cathyatseneca/DSAnim ). Currently the code animations are pure Processing sketches (I didn’t stick any bits of JS in my sketch this time :P). However that might change later when I try to add in controls. You can check it out live here:
When I was putting these animations together, one of the things that I had trouble with was translating the algorithms into animations. Processing works by repeatedly calling a draw() function in which you tell it what to draw in the next frame. In other words there is a sort of built in loop. While it is possible to call a function for some algorithm (a sort for example) within the draw loop, you can’t really animate it just by calling it as it will be called each frame and what you want is to animate steps within the function.
I admit that I’m very new to Processing. Thus, this may not be the best way to do this (if anyone has suggestions please let me know!) The design I settled on in the end was to create a general array animation. The array has a single draw function that the main draw loop will call. Depending on the state of the array, the array’s draw() function will animate one frame of what is going on (one frame of a swap for example).
The array has states which determines what to draw. Currently the array has these functionalities:
- moves (move number from one element to another)
- swaps (swaps two values in array)
- stable (nothing is happening)
- move to temp (move number to a temporary location out of array)
- move from temp (move number from temporary location to array)
The object also has indicators and a splitter bar that you can add to your animation. You can also change the colour of the text in the array.
So far I have completed the bubble and insertion sorts. I think I will need to add more functionality to properly show merge sort. I have not yet really thought too much about a quick sort. After the sorts I will probably start looking to add trees and lists. I am hoping to also add animations for other data structures as well. The code is far from perfect but it looks neat and for now that will have to do :).