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.

Category:

Science & Technology

Tags:

• science
• visualization
• computer
• algorithm
• animation

[coffeeteamix]

cute overload XP

the quick sort one was slightly confusing when shown like this though, for 2 reasons. #1 The robot needs to walk around a lot more, making it slower. Is this true in the actual algorithm? and #2 The placing of the first "lighter colour" ball on the rack, then suddenly moving on to search the other end of the list. Is that really how it's done?

[udiprod]

@coffeeteamix Re #1: Indeed Quick sort moves around a lot. When you need to sort a large file on disk, every large move causes loading a different chunk of the file to memory. In this case other algorithms are better (not Bubble sort, though). Re #2: The real Quick sort simply makes a note of the location of 'the first lighter ball' and then moves to search the other end. However when the time come to swap elements - usually this requires putting one of them in a temporary location

[pash080]

why can't the robot get the glance of every ball and memorize their brightness then sort them at once?

[udiprod]

@pash080 This would just transfer the problem to the robot's memory. Computers must have an algorithm for sorting, even in their memory. You, being human, can 'sort them all at once' using your intuition. Imagine that you need to sort 1,000,000 balls. Since this is too much for human intuition, you would have to resort to an algorithm, just like a computer.

[heatmourning33]

@udiprod

"You, being human, can 'sort them all at once' using your intuition."

I don't know about that, don't you think were really using an algorithm ourselves, though me may not know we are doing this. The only difference is computers dont "know" they are sorting something. and we do.

[udiprod]

@heatmourning33 I agree that when someone solves a problem intuitively, there is some algorithm underlying this intuition. What I meant to say was that sometimes it's so simple to solve a problem intuitively, e.g., sorting small lists, that one may mistakingly believe there's no need for an algorithm at all. Then when you want teach a computer how to do it, you suddenly realize you don't even know how you do it :)

[riocardw]

This is such a good video, missed a lecture and this helped me out man!! kudos to you :)

[bebeheuy]

I am very happy to see the vidoe after you give this It demonstrates two comparison sorting algorithms: Bubble sort and Quick sort.

[AntoMelta]

I Really Like The Video From Your Visualization of Quick sort

[willamricard]

Your Video Is Very Useful Sharing It demonstrates two comparison sorting algorithms: Bubble sort and Quick sort.

[imegatrone]

after i watched this video, my insight is very open because the video is very good to give information It demonstrates two comparison sorting algorithms: Bubble sort and Quick sort.

[CuriousGuy95]

@the0th not funny, color blinds can still differenciate gray shades

[Ashingda]

Ya know instead of quicksort robot holding the pivot ball in one hand maybe it can place it on top of it's head so both hands are free. I've alway visuallized it as Left-hand && Right-hand, but then again the pivot ball wasn't supose to be picked up like that in the first place.

[winneluo]

so cute! lol helps alot!

[the0th]

this would be useful if i wasn't colour blind.

[purefatdude2]

this looks like selection sort