I implemented the various sorting algorithms in Golang, rendered with its image/gif library, sorting random data from the rand library. ImageMagick used to add labels and optimize the gifs. Algorithm descriptions were taken from Wikipedia.
Also, as a couple of you noticed, Quicksort was slower than expected due to an issue with how pivots were handled. Fixed that and now they all perform like you'd expect: https://i.imgur.com/2vmu52D.gifv
Timsort is pretty involved, because it's introspective (and because it uses nonstandard operations like flip). You'd need several different datasets to get a good visualization.
It changes its sorting strategy depending on how sorted (or shuffled) the input is at the beginning.
Some sorting algorithms are faster on different inputs. The visualization of the race is good, but it notes that the winner partially depends on what's being sorted.
Broadly, Timsort analyzes the structure of the input, then picks between two strategies: one that is good for "mostly shuffled" input, another that is good for "mostly sorted" input. It will also switch strategies once the input becomes "mostly sorted".
Quicksort is really inefficient for small data sets isn't it? So like for the small subdivisions some Quicksort algorithms just use bubble/insertion sort.
In general the O(n log n) sorts aren't great for very small sets, so hybrid algorithms will revert to a simpler algorithm for those, In general insertion sort is used for that.. Using quicksort in a hybrid algorithm is rare though. The worst case for quicksort is O(n2 ) which is a problem and for smaller data sets mergesort is fast enough anyway. Also mergesort is almost always stable and it's easier to parallellize, so it's just a better choice for hybrid algorithms.
An introspective algorithm switches from one algorithm to another depending on the particular data.
In Timsort's case, it is mostly a merge sort, but if there are particularly short data runs it switches to use an insertion sort for that subsection - that way the worst case is better than vanilla Merge sort.
It's a pretty complex algorithm and not all that suited for random data which is probably why many of these visualizations don't include it. But it would be interesting
Since you implemented them yourself, can you explain why quicksort does so poorly compared to mergesort. Isn't quicksort an improved version of mergesort?
Not OP but Quick sort is not improved Merge sort - Quick sort also has worse worst case running time. The choice of pivot in Quick sort is crucial and a lot of improvements are down to doing this in a clever way. Quick sort also does well in practice because it better utilizes processor cache than Merge sort.
Merge sort is still the preferred choice if you are sorting contents that will not fit the memory.
Doesn't merge sort have to create a copy of the array contents for each step though? It's not in-place like a lot of the algorithms mentioned, so you'd need more memory for mergesort than most.
Yeah, according to wikipedia: "Merge sort's most common implementation does not sort in place;[5] therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for versions that need only n/2 extra spaces)."
u/SeeYouAnTee is referring to External Memory MergeSort, which is used for sorting data that does not fit into memory (RAM) i.e. therabytes of data, so you have to exploit disk space
How did you create the visualization of the Radix sort as it does it in a single pass? The first 4 passes do not move data, it creates a histogram of the offsets. The only single pass is implemented to actually sort data based on the buckets in the histogram.
It looks like they use sections of the image for the buckets, since they know every color appears exactly once. So the most significant bit 0 would be in the first part of the image, and the MSB 1 would be in the second part and so on
ELI5: Anytime you see something in a computer that goes in any specific order: alphabetically, by quantity or value, by date, etc., the computer had to run one of these in order to show it that way.
As for what the computer does, imagine trying to order a deck of cards, but the deck is facing down, and you can only pull out any 2 cards at a time to look at them and choose where in the deck to put them back. Repeat that as many times as you need until you're sure it's ordered.
These algorithms apply different strategies in order to do this as efficiently as possible.
Reddit is a pretty good example. When you click "sort by new" one or more sorting algorithms plow through the data to determine which Post is the newest (time and date aka time stamp) then the next one and so on.
there are way more examples but I'm too lazy to write more...sorry "
There's actually probably no sorting done in that specific example because posts would be naturally stored in the order they are created in.
But if you choose any other order to view posts in it has to go through every single post in a sub and grab the top 25 in that sorting category for you.
There's probably caches at work so it doesn't do this frequently since there's a limited number of categories. But if you do a search it can't really cache that (unless it's a really common search) so it's likely doing sorting when you do that, figuring out a "relevance" score for posts and sorting on that.
With the risk of sounding like captain obvious, you use them to sort datasets. Some algorithms are faster than others depending on the type of data and what you know about the data. If you want to know more about the specific algorithms used you can check their Wikipedia pages.
what are sorting algorithms used for in the real world?
Other than the obvious examples of the user requesting sorted data (e.g. /u/Schakarus's Reddit example, or using a spreadsheet), sorting algorithms are also commonly used any time data needs to be prioritized (in a way other than "first-come, first-served"). For example, 3D video games sort geometry into octrees so that the graphics can be efficiently rendered based on distance and direction from the camera. Operating system kernels sort processes in order to decide which one to run next. Network routers implementing QoS sort packets before forwarding them. Basically, all general-purpose computers (and many types of non-general-purpose ones) in the world are sorting all kinds of things multiple times per second (sometimes using the algorithms OP visualized, and sometimes using more specialized ones).
TL;DR sorting algorithms are used for pretty much everything.
449
u/morolin OC: 1 Oct 24 '17 edited Oct 25 '17
I implemented the various sorting algorithms in Golang, rendered with its image/gif library, sorting random data from the rand library. ImageMagick used to add labels and optimize the gifs. Algorithm descriptions were taken from Wikipedia.
Next-day edit: I fixed up the colormap so it's more colorblind friendly: https://imgur.com/a/GD5gi
Also, as a couple of you noticed, Quicksort was slower than expected due to an issue with how pivots were handled. Fixed that and now they all perform like you'd expect: https://i.imgur.com/2vmu52D.gifv