Visualization of Quick sort

This video was created for http://www.zutopedia.com

It demonstrates two comparison sorting algorithms: Bubble sort and Quick sort.
Comparison sorting algorithms are only allowed to ‘see’ the data through a sequence of pair-wise comparisons, therefore they are applicable to any type of comparable objects: numbers, strings, colored balls, etc

Bubble sort is very simple but has poor performance. A comparison sorting algorithm’s performance is usually measured by the number of comparisons it makes. Bubble sort performs on the order of n^2 comparisons to sort n elements.

Quick sort is only slightly more complicated but usually performs much better (as demonstrated in the video). It performs on average an order of n log(n) comparisons to sort n elements. This is much lower than n^2 for large values of n. However, if the algorithm makes some ‘unlucky’ choices it might require n^2 comparisons after all.

Other algorithms exist that guarantee the number of comparisons will not exceed n log(n), however, in practice Quick sort usually out-performs all other comparison sorting algorithms due to its simplicity.

If other operations other than pair-wise comparisons are allowed, then a broader range of algorithms can be used. Some of them can perform much faster than Quick sort, but they are limited to a particular type of elements, e.g., numbers is a certain range.

Duration : 0:2:56


[youtube vxENKlcs2Tw]

Other Data visualization Resources

25 thoughts on “Visualization of Quick sort
  1. Ok, but I would at …
    Ok, but I would at least advise to choose greater colour difference between the balls or/and less balls cause some of the colour differences are hardly distinguishable to my eye & still I’m not a colour blind person :) That can also be intensified by the video compression

    Cheers,

  2. Two reasons:
    a) …

    Two reasons:
    a) To demonstrate that comparison based sorting algorithms can work on any comparable objects
    b) In my opinion it makes it clearer to see at a glance if the balls are sorted or not.
    Anyway, thanks for the comment. I’m sure other videos stress other aspects of quick sort.

  3. Animation is great …
    Animation is great but… I found other (much simpler videos) more helpful.
    Still I consider this one OK.
    Just one thing: I don’t get is why you’ve chosen different tints of red rather that putting either numbers or letters on the balls to be sorted? (That would be more transparent to grasp)

  4. i kinda wanted to …
    i kinda wanted to see how long it took the other one, ohh well, still a great animation

  5. never seen such a …
    never seen such a great sorting-algortihms animation… was really funny to watch this one!

  6. awesome :D i …
    awesome :D i wondered how quicksort works, cos ive only been able to return the highest number. Now i realize u need to perform multiple runthroughs :D

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>