An animation of the Quicksort algorithm

Posted on October 17, 2010. Filed under: Uncategorized | Tags: , , , , , , , |

Here is a (preliminary) animation of the Quicksort algorithm. At the same time, this is a small project to try out the Trident java animation library.

Running the example requires Java Webstart (and is at your own risk, the author does not take any responsibility for any negative effects caused by running this example). To start the demo, click here.

A few explanations:

  • The example is modeled after the Quicksort implementation as given in “The Algorithm Design Manual” by Steven Skiena (Section 4.6)
  • Those boxes which are already at the final position are drawn in white (instead of gray)
  • The boxes with dark red background are those currently being worked on (between the variables l and h). The variables l and h themselves are shown by the boxes ‘L’ and ‘H’
  • The variable i is displayed by the box I
  • The pivot (against which the element at i is compared) is at position h in this implementation
  • The box F corresponds to the value of the variable ‘firsthigh’ in Skiena’s book

You’ll notice that:

  • after i reached the right end of the range currently being worked on (end of routine ‘partition’), the value originally at h will be put where ‘firsthigh’ is and is at its final position. The elements left of it (in the current range) will have a smaller value, the ones on the right a larger value.

Comments and suggestions are welcome !

Advertisements

Make a Comment

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

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: