Uploaded February 2009 | Updated September 2026, 2 weeks ago
See a new version of this video: youtube.com/watch?v=aXXWXz5rF64 (HD + narration)
A demonstration of the Quick Sort sorting algorithm.
Visit my homepage, udiprod.com/, or read about my latest book 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.
See a new version of this video: youtube.com/watch?v=aXXWXz5rF64 (HD + narration)
A demonstration of the Quick Sort sorting algorithm.
Visit my homepage, udiprod.com/, or read about my latest book 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.
![[Laser] Firing squad synchronization problem](https://i.ytimg.com/vi/xV1aKUdlljU/mqdefault.jpg "[Laser] Firing squad synchronization problem
The video shows a theoretical problem in computer science and a solution for it. It is presented as a riddle, but note its not easy to solve.
The shown solution is based on the first solution proposed for this problem. It requires ~3n steps, and 17 states.
See list of states and some additional information here: https://www.udiprod.com/firing-squad-synchronization/")
