Creating a bubble sort animation

One course that I teach is data structures and algorithms in C++ (dsa555).  It is pretty much like any other algorithms course with a survey on how some very common algorithms work.  As I was wrapping up the course this semester with a discussion on red-black trees, I went to look for a good visual animation of a red-black tree and found that many of these were done in Java.  They took a while to load and felt …well clunky.  With all the work our students have put into implementing processing.js I figured that it would be fun to try to make my own versions of these animations using processing.js sketches.
The first one I decided to tackle was a the simple bubble sort algorithm.  Just about every student has seen this algorithm at one point or another.  It is not hard to code and the visualization should be easy enough to do so I set out to put one together.

Incremental development

I decided to do this by just slowly piecing together the visuals for the sort and making decisions about how it should look.  Here is a first stab at animating it… not very exciting but it does work

Things I’ve learned:

1) anti-aliasing: If you draw over something exactly it may not work as you expect.  Initially my animation had arrows that were white and I would move them along under the array to indicate the pair of numbers I was interested in.  Originally my code to erase the white arrows was to draw blue arrows of the same size/shape over them.  However, this turns out to be a bad idea due to the way canvas draws.  The ticket (and details of why it didn’t work are here)… In any case I switched to simply redrawing the background and array and that worked just fine (easier too… I was just worried about “flickering” but it turns out it doesn’t do that so it worked out fine).  In the end I decided to scrap the arrows because they didn’t add much to the animation anyways.

2) developing incrementally was a nice idea… you can fiddle with it a bit at a time and add to it

3) random…pjs automatically seeds your random number generator.  Great for when you are done not so good when you’re testing.  Make sure you seed your random number generator with a constant so you can get same set of data when you are testing… just take it out at the end 🙂

To Do

the bubble sort animation basically works but there is still much I would like to add.  Here is a short list:

  • structure the actual bubble sort/array better.  Currently my code is sort of all over the place and it makes me cringe to look at how badly structured it is. My animation code is controlling the sort and that just seems wrong. I think I need to come up with a better way to my data so it is easier to develop other animations.
  • Add controls – the speed of this animation is really slow. I’d like to add some controls to change the speed as I go
  • Add more visuals – pjs is so visual and all I have are colored numbers… I think something that is more graphical would be nice.  I’ve seen other sorting algorithms use bars to indicate values.. this should be quite easy to add
  • Add code… show the code as the algorithm runs (like a step through) and highlight the code along with the animation
Advertisements

2 responses to “Creating a bubble sort animation

  1. Hi Cathy, im very interested with your elaboration of bubble sorting. Can i have a look your animation and the code? anyway what kind of programming language that you used for this?

    Cheers!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s