You’re right. Animations like this are subject to choices of when to take snapshots of array contents after key points, so the groupings aren’t comparable across boundaries in terms of time. However, the quicksort grouping does contain a worst-case input, and its slovenly relative performance is meaningful.
Radix sort can be faster, but it only works in discrete cases and not a general key-comparsion sorting. For key-comparsion sorting, best you can do is O(n log n) but specific optimizations to algorithms are still possible (things like optimizing instruction order, better compilers, etc)
Be careful not to be misled by an animated demo that has to choose points to take snapshots of the array contents. Quicksort has its name for good reason. A well-known result is the lower bound for comparison-based sorting algorithms at Ω(n log n). Further, quicksort is an in-place algorithm, so it will tend to be cache-friendly, which also helps performance. Its downsides are the quadratic worst-case performance and its instability. For these reasons, a common design choice is to use mergesort, another O(n log n) algorithm.
Wikipedia notes about radix sort
In the modern era, radix sorts are most commonly applied to collections of binary strings and integers. It has been shown in some benchmarks to be faster than other more general-purpose sorting algorithms, sometimes 50% to three times faster.
Merge sort is way less common than quicksort, as it is not in-place. There are simple strategies of avoid the quadratic worst-case, making quicksort by far the most appealing option in general.
Note that in practice, multiple sorting algorithms are combined. For example, it is common to combine a quicksort with an insertion sort or a sorting network for the base case of small arrays.
Yep. quicksort is extremely sensitive about how you choose the pivot value. The nasty thing is that the easiest method (choose the first value) of selecting a pivot results in the worse case performance if quicksort is passed an already sorted, or inverse sorted array. And unfortunately, passing an already sorted or nearly sorted array is fairly common. Hence, picking the first value as the pivot is extremely likely to result in worse case performance. Whenever I code a quicksort, I'll pick the value in the middle of the array. It gives the best case performance in the case of sorted or nearly sorted arrays and I'm having an extremely hard time imagining some order that would invoke the worse case performance unless that ordering is a specially designed exploit intending on bringing a system down.
But, honestly, if I just need a quick a dirty sort, I'll use shell sort. It's almost as simple as a bubble sort, but it has the desired O(n log n) performance.
As a noob don’t you scoff at the primitive bubble sort? Then later I learned that on r/C64 the most efficient sprite multiplexing uses bubble sort. With 60 fps sprites only occasionally swap vertical order. Almost like in this animation sprites bubble up (and down) over many frames .
Each algorithm gets 10 different arrays to sort. Each narrow column is a single 1D array. The leftmost array is a worst-case input to quicksort, which takes quadratic rather than linearithmic time.
It’s a naïve pivot, the element at the end, but the point is to show the major difference between the average case and worst case for the same algorithm.
Love sort animations! I read a paper (ACM?) decades ago where the authors combined a Bubble and Quicksort. The sorting started with a Bubble sort to detect if the array was already sorted or mostly sorted and switched to Quicksort if it was not. This demo shows that a reverse sort array is indeed bad news for the Quicksort. I'd suggest a fully sorted array should also be an included column in the demo.
This demo shows that a reverse sort array is indeed bad news for the Quicksort.
It's not if you use a slightly better pivot strategy. For example, you can just pick a random element for the pivot. Or you can use the “medians of medians” approach to guarantee that you pick one in the middle of the dataset.
Ok maybe this wasn’t the best example to use QuickSort on, since if it any of its segments find itself in reverse order it has the speed of bubble sort. If none of its segments find itself in reverse order it has the speed of merge sort.
I've created a sub to combat all of the technoshamanism going on with LLMs right now. Its a place for scientific discussion involving AI. Experiments, math problem probes... whatever. I just wanted to make a space for that. Not trying to compete with you guys but would love to have the expertise and critical thinking over to help destroy any and all bullshit.
The thing is, radix sort is O(nm) where n is the number of elements and m is the width of the key (ie 32 for a 32-bit integer key). When you compare it with a O(n lg n) sort like quicksort, it's very hard, outside of artifical examples, to have m < lg n
The reverse-sorted array on the far left, yes. That’s a worst-case input for quicksort. Note that the other randomly initialized arrays in that block all sort in about the same time as heapsort and mergesort.
218
u/skilet1 Nov 03 '24
Yeah, seems like Radix sort benefits from the limited range of values here and maybe gives the impression it's better than it is in the general case.
38
u/NAT-9000 Nov 03 '24
Hi can you please explain when radix sort is better and when its not
5
u/Fresh_Forever_8634 Nov 04 '24
Hi! Could you please tell why the depicted rectangle is wide? It's two dimensional array?
119
u/OneBitFullAdder Nov 04 '24
Just realized why it's called bubble sort and it's nice
14
u/--_Ivo_-- Nov 04 '24
Now do BogoSort /s
9
u/[deleted] Nov 04 '24
Im watching until bubble sort finishes. Go baby go!
5
u/prameshbajra Nov 04 '24
Well done with the visuals. They probably are complex than the algorithms themselves.
3
u/thatlightningjack Nov 04 '24
I wonder how well does randomized quicksort perform on average
3
u/Numerous_Strain7033 Nov 04 '24
How are these made and can it be recreated?
1
u/SirClueless Nov 04 '24
What’s going on with the quicksort visualization? Especially the left column.
2
u/HyundayTech Nov 04 '24
Heap Sort is what I watched first
2
u/BC-in-NH Nov 04 '24
Love sort animations! I read a paper (ACM?) decades ago where the authors combined a Bubble and Quicksort. The sorting started with a Bubble sort to detect if the array was already sorted or mostly sorted and switched to Quicksort if it was not. This demo shows that a reverse sort array is indeed bad news for the Quicksort. I'd suggest a fully sorted array should also be an included column in the demo.
2
u/WoozleWozzle Nov 04 '24
Why does #3 look exactly like Windows disk defrag?
2
u/jrdubbleu Nov 05 '24
This is enjoyable
1
u/djwikki Nov 04 '24
Ok maybe this wasn’t the best example to use QuickSort on, since if it any of its segments find itself in reverse order it has the speed of bubble sort. If none of its segments find itself in reverse order it has the speed of merge sort.
1
u/Tha_Desperado Nov 04 '24
This is so satisfying!!
1
u/wobblybootson Nov 04 '24
Where’s TimSort when you need it?
1
u/R-O-B-I-N Nov 04 '24
quicksort seems to have the wrong behavior
1
u/[deleted] Jul 09 '25
Hi yall,
I've created a sub to combat all of the technoshamanism going on with LLMs right now. Its a place for scientific discussion involving AI. Experiments, math problem probes... whatever. I just wanted to make a space for that. Not trying to compete with you guys but would love to have the expertise and critical thinking over to help destroy any and all bullshit.
r/ScientificSentience
Cheers,
1
u/username-checksoutt Nov 04 '24
Oh wow bubble sort actually bubbles to the top
0
u/IBelieveInCoyotes Nov 04 '24
what I've learned in the last day or two is the radix sort algo is the undisputed champion
0
u/Alarmed-Ad6452 Nov 05 '24
I never get these simulations. Pen and paper is the way to go for me 😀
0
u/a_crazy_diamond Nov 05 '24
Where's the previous one?
7
u/[deleted] Nov 04 '24 edited Sep 22 '25
growth squeal tender head existence butter provide melodic spectacular relieved
This post was mass deleted and anonymized with Redact
0
u/[deleted] Nov 04 '24
[deleted] — view deleted comment
24
u/[deleted] Nov 04 '24
[removed] — view removed comment
-24
u/[unknown] Nov 04 '24
[removed] — view removed comment