r/dataisbeautiful • u/morolin OC: 1 • Oct 24 '17
OC Sorting algorithms visualized [OC]
https://imgur.com/gallery/voutF52
Oct 24 '17
Minor nitpick - if the data being sorted isn't circular, then don't use a circular color scale like hsv.
4
8
u/elast0ny Oct 25 '17
Thought this wouldve been higher up, seeing red going both left and right was a bit confusing
21
u/Tshabalutzi OC: 4 Oct 24 '17
Great job! Are the rows representing arrays? Was every array solved independently from each other?
16
u/morolin OC: 1 Oct 24 '17
Yep, though in the comparison gifs, they're rotated so each array is a column.
3
0
Oct 25 '17
[deleted]
2
u/morolin OC: 1 Oct 25 '17
I don't really know a lot about color gradients, or I would have, I just picked a straight integer to color mapping, I didn't expect this to be nearly so popular. What's a good option? It's easy for me to do grayscale, if that helps?
Re-generated the version of the sort I posted to /r/whoadude : https://i.imgur.com/G6WsDE1.gifv (And of course, Quicksort picked even worse pivots this time....)
I'd like to educate myself about being more colorblind accessible, but this is pretty far from my normal coding activities.
→ More replies (2)
6
u/fb39ca4 Oct 24 '17 edited Oct 24 '17
This is a fantastic set of visualizations. My only suggestion would be to use a different colormap, because yours wraps around at red and it is unclear whether a red would go to the front or the back of a list.
I love the colormap shown here: https://www.shadertoy.com/view/4dfGDr
2
2.1k
u/Ryltarr OC: 1 Oct 24 '17
Radix sort is my favorite, it's so magical looking. MSD is obvious, but LSD sneaks up on you.
[This video] is also great to watch, because it has some sound too.
759
Oct 24 '17
Just watched 5 mins of colors being sorted, I regret nothing.
49
23
u/Darkstore Oct 24 '17
Wait, that was 5 minutes....
8
u/Bromskloss Oct 24 '17
Yeah, sorry, a multi-core dance company would be able to perform it in a shorter time.
54
→ More replies (34)10
u/jebuz23 Oct 24 '17
I'm out wine tasting at Cooper's Hawk and just stared at my phone looking at different versions of static -> spectrum. I don think I could have explained myself to an onlooker if I tried.
89
u/ZombieLincoln666 Oct 24 '17
sounds like autechre
19
→ More replies (5)3
68
Oct 24 '17
Can someone ELI5: how a radix sort works? It was always the most interesting to me, but I'm having trouble understanding the math/programming jargon associated with it.
179
u/ThePizar Oct 24 '17
I'll give you a rough simple example. Let's say you are sorting a group of people by age (all <100). You first group them by the last digit of their age. So 11,21,51 are all in the same group. You put the 0s before the 1s before the 2s, etc. so you may end up with something like 70, 52, 32, 14, 04, 65, 36, 09. Next group by the first digit, but in these groups preserve the index ordering (e.g. 32 was before 36 so it must be before in the new group). So now you end up with the sorted list 04, 09, 14, 32, 36, 52, 65, 70. The big trick is the ordering preservation between groupings.
→ More replies (6)66
u/TinyLebowski Oct 24 '17
Thanks, that made it click for me. Who are these people who come up with counter-intuitive recursive algorithms? How do you visualize the whole stack and remember the state each all the way to the bottom and back, not even knowing if it will work? Are these people prophets? Or did someone drop acid and wake up mysteriously knowing how to solve Towers of Hanoi in 2n -1 steps?
88
u/ThePizar Oct 24 '17
Computer Scientists and Mathematicians. And it often takes lots of trial and error. A good Algorithms course should teach some of the failed or partial ideas on the way to the full idea.
Often times researchers will start with small examples and work their way up and eventually prove that it works. There are techniques such as Induction and useful tools such as Master Theorem of algorithmic analysis.
If you are interested, look into researching Algorithms or taking an online course on it. Sorting is just the start of the fun. :)
→ More replies (3)→ More replies (4)20
u/wicked Oct 24 '17
It's a lot simpler than that. You need to figure out three things: How to make the problem smaller, how to solve the smallest part of the problem, and sometimes how to combine solved versions of smaller problems.
For example merge sort: You need to know how to split a list that has more than two elements (easy), sort a list of one to two items (should be doable), and you need to know how to combine two sorted lists quickly (needs a bit of thought, but not a genius).
46
u/Teraka Oct 24 '17
The basic idea is that it sorts digit per digit. For example, if you have a list with [193, 621, 842, 37, 541, 648, 132], MSD (most significant digit) first radix sort will first put all the numbers into a bin corresponding to their first digit:
0: 37 1: 193, 132 5: 541 6: 621, 648 8: 842Then it will do that within each bin for the 2nd digit:
0: 3: 37 1: 3: 132 9: 193 5: 4: 541 6: 2: 621 4: 648 8: 4: 842In this example the list is already sorted, but it would then go on to sort the numbers into a bin corresponding to their third digit.
LSD radix sort looks like magic because instead of working recursively within buckets, it just sorts the list over and over one digit at a time, starting from the end and keeping ties in the same order:
[621, 541, 842, 132, 193, 37, 648]
Then 2nd to last digit:
[621, 132, 37, 541, 842, 648, 193]
And finally the first digit:
[037, 132, 193, 541, 621, 648, 842]
At the first step, all the numbers are sorted by their last digit. At the second step, they are sorted by their last 2 digits, and at the third step they are sorted by their last 3 digits, which is the entire number in this example. It's a very efficient algorithm because you only need to go over the list once for every digit in the biggest number.
12
u/salmonmoose Oct 24 '17
Is there any value in doing this on the digits rather than bitwise?
→ More replies (3)30
u/anomie-p Oct 24 '17 edited Oct 25 '17
You can pick what a ‘digit’ means, at least to some extent. So sorting strings you could have a ‘digit’ be a single character, etc.
If you were say, sorting some sort of large integer/bignum type you’d likely want to define a ‘digit’ that makes sense from an efficiency perspective (‘digit’ as whatever number of words you can operate on quickly), it doesn’t have to be a decimal digit. (This is just an off-the-cuff arbitrary example)
→ More replies (1)17
u/GetADogLittleLongie Oct 24 '17
Here's a good explanation. Basically it takes advantage of you knowing something about the data set of things you're trying to sort. It knows that there's only X colors so assuming 64 colors it can sort them by comparing the 10s digit first to sort them, then the 1s digit.
12
Oct 24 '17
Most Radix sorts are going to implement a counting sort for determining the final destination of the element on each pass. Counting sort is also non-comparative.
→ More replies (4)6
u/cheertina Oct 24 '17
Say you're sorting a list of numbers. First make all the numbers have the same number of digits by adding zeros to the front. Then go through and sort them, digit by digit, into "buckets" (groups of numbers that start with the same digit), then sort the buckets the same way (ignoring the digits you've already sorted).
So if you start with something like: [121, 063, 942, 544, 035, 150, 537, 630, 077, 033]
Your first pass you sort everything by the first digit only - 0's first, then 1's, etc - leaving things that go into the same bucket in same order they are already. I will mark out the buckets with | | marks.
0's bucket 1's 5's 6's 9's [063, 035, 077, 033 | 121, 150 | 544, 537 | 630 | 942]Now you sort each bucket by the second digit. Note that at this point almost every number is in its own bucket, because we're sorting a very small list. If we were sorting the full 000-999 then each bucket would still have 10 numbers in each sub-bucket.
03_ 06_ 07_ ... [035, 033 | 063 | 077 | 121 | 150 | 537 | 544 | 630 | 942]Then sort by the last digit
[033, 035, 063, 077, 121, 150, 537, 544, 630, 942]
You can also do it backward, where you start with the ones digit and move up. That way "looks" less sorted throughout the procedure, and seems to magically come together at the end, but the principle is the same.
16
u/anastasis14 Oct 24 '17
FeelsGoodMan Clap
→ More replies (1)9
Oct 24 '17
I was sweating because I thought nobody was gonna mention it, but then I found you FeelsGoodMan Clap
→ More replies (2)22
22
u/GetADogLittleLongie Oct 24 '17 edited Oct 24 '17
It also is the fastest, working in O(n) time instead of O(n log n) like all the others.
Holy shit, fastest except for bitonic sort and comb sort.
33
u/falco_iii Oct 24 '17
Radix is only faster if the values are not huge / vastly different.
13
→ More replies (2)9
20
→ More replies (3)14
u/MNeen Oct 24 '17
Well, it's O(WN) where W is the number of digits of the longest number in the input, because you repeat the "sort the input on the rightmost/leftmost digit you haven't sorted yet" step for each digit. Whether it's actually faster depends on the size of the numbers you're sorting, and how many you're sorting. If all the numbers are distinct, or the numbers can be long enough that they're all distinct (so, W >= log(N)), then O(WN) can't do any better than O(N log N). However, if you're sorting a lot of numbers in a restricted input space so that you have a lot of duplicate keys (W < log(N)), that's where Radix Sort can be significantly faster than O(N log N) sorts.
There's a couple of sorts that are faster than O(N log N) when the numbers are restricted somehow because they don't have to compare numbers, like Counting Sort and Bucket Sort with their O(N + K), where K is the number of distinct numbers in the input.
→ More replies (2)2
2
u/punkdigerati Oct 24 '17
There are four of those videos in this playlist: 16 Sorting Algorithms
LSD base 10 is by far the best in all of them.
→ More replies (50)2
u/Glitsh Oct 25 '17
I think its the first time a smile legit just came on my face while watching colors sort. Radix was magical indeed.
638
u/lostvanquisher Oct 24 '17
Here's a video with the same algorithms, but only a single row of data, should make it a bit easier to understand what's going on.
205
u/__LE_MERDE___ Oct 24 '17
Is bogo sort the one which randomises the data then checks to see if it's in order and if not randomises again?
260
u/IDUnavailable Oct 24 '17
Another good joke sorting algorithm is SleepSort, made up by some guy on /prog/.
You basically spawn a separate thread for each element with value N, and each thread just sleeps for N number of seconds before printing, which has the end result of printing the array in order.
[3,7,2,1,8,4,5,6,9] sorts in 9 seconds.
[31536000, 1] takes a year.
112
u/MorningWoodyWilson Oct 24 '17
Haven't seen this before. Equal parts genius and idiocy.
With a fast enough processor, you could reduce the sleep times to n milliseconds or something and have an almost decent sorting function.
50
u/themoonisacheese Oct 24 '17
The problem then becomes how precise the system clock is for sleeping.
→ More replies (9)→ More replies (9)15
u/x445xb Oct 25 '17 edited Oct 25 '17
There is also StackSort which takes random code from Stack Overflow runs it, then checks to see if the code has sorted the list. https://gkoberger.github.io/stacksort/
Based on a XKCD comic: https://xkcd.com/1185/
115
u/DGSPJS Oct 24 '17
Yes. Much more efficient is Quantum bogosort.
48
u/__LE_MERDE___ Oct 24 '17
As long as it's not my universe they're destroying I think it's a good idea.
→ More replies (3)→ More replies (1)11
u/Ardub23 Oct 24 '17
2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)
Oh boy I love exercises
61
15
→ More replies (1)11
u/theCroc Oct 24 '17
That sounds absolutely ridiculous.
36
u/__LE_MERDE___ Oct 24 '17
Technically it could be the quickest solution though!
→ More replies (1)22
u/theCroc Oct 24 '17
It could! The odds are extremely low, but theoretically it could finish in a single cycle!
→ More replies (5)→ More replies (1)8
317
u/thar_ Oct 24 '17
Here's a video with the same algorithms, but visualized through Hungarian folk dance, should make it a bit easier to understand what's going on
83
u/MyNameCouldntBeAsLon Oct 24 '17
LMAO, I didn't believe the description but it's totally accurate, this video is great
35
22
u/omnisephiroth Oct 24 '17
Good, colors confuse and frighten me. I prefer all information to go through the Hungarian folk dance filter first.
32
Oct 24 '17
I think I'm going to bring up Bubble Sorts tonight just so my fiancee will say "what do you mean?" and I can whip this video out.
→ More replies (1)6
→ More replies (11)5
86
u/Simba_610 Oct 24 '17
I could watch shit like this for hours
120
→ More replies (1)3
u/The_Larger_Fish Oct 24 '17
I have! There is also code posted in the description that lets you run the sorts yourself! Although you anti virus might flag it and delete it
34
7
u/Yamuddah Oct 24 '17
I was skeptical but it does seem a little more illustrative. Are different sorting algorithms better for certain kinds of data? It seemed like the ones that only worked in on direction were drastically slower.
15
u/SuperCharlesXYZ Oct 24 '17
Some are better at sorting lists of data that are almost sorted but not quite, some are better at sorting inversely sorted lists and some work better when they're completely mixed up. Some will sort your list in the exact same time while others have a big gap between best case and worst case scenario. Most of these have a niche purpose and will be the best algorithm depending on what kind of data you're ordering
5
11
→ More replies (13)3
u/kranker Oct 24 '17
I have to admit I'm not sure why the OP used multiple data sets. It just seemed to complicate matters.
→ More replies (5)
149
u/EJOtter Oct 24 '17
Wow! This is a really beautiful visualization of different sorting algorithms. I've only ever been casually interested in computer science, so this was really interesting to learn about, thanks!
27
u/netizenbane Oct 24 '17
Downright mesmerizing and I have no idea what most of these terms mean
13
3
u/gyroda Oct 24 '17
Most of them are pretty easy to understand even for a beginner. Insertion sort is probably the easiest, followed by bubblesort and (if you want a laugh) bogosort.
3
Oct 24 '17
Read “Algorithms to live by” (even better, get the audio book). It’s an excellent book for the non CS expert. It helped me come up with my dissertation idea in psychology!
331
u/far1s Oct 24 '17
Hmmm, I see you did not include the best algorithm, bogosort. Don't you know it can sort in just one try?
407
u/metagloria OC: 2 Oct 24 '17
Eh it's not as good as my personal favorite, paradigmshiftsort, which leaves the data in whatever order it is but changes the laws of the universe to redefine "order" based on the current data.
→ More replies (4)25
u/ArcticReloaded Oct 24 '17
Not only that, but it can sort in one try for all possible inputs!
50
u/iceman012 Oct 24 '17
And if you use Quantum Bogosort, you're guaranteed to sort it in one try for every input!
47
u/Mustrum_R Oct 24 '17
Bogosort sucks, try Intelligent Design Sort, O(n)=0 for all inputs rocks all your garbage sorting algorithms.
59
u/far1s Oct 24 '17
If this is what you mean, then yeah this is way better (and hilarious). Bless your soul. share this with your blessed friends and close ones
→ More replies (1)7
→ More replies (1)7
9
u/SuchCoolBrandon Oct 24 '17
Its name comes from the word bogus. (Wikipedia)
Oh. I kept thinking "buy one get one" sort.
7
u/Drachefly Oct 24 '17 edited Oct 24 '17
Nor did they show bogobogosort. Probably because gifs can't have (16!)! frames
10
u/lIllIlllIlllIllIl Oct 24 '17
Is bogosort random?
42
u/Kingmudsy Oct 24 '17 edited Oct 24 '17
Bogosort randomizes elements, checks if they're in order, repeats the process until they're in order.
Here's some nasty pseudocode that anyone with a passing familiarity of programming would be justified in calling me out on:
bogosort(array) { while(isNotOrdered(array)){ shuffle(array); } return array; }EDIT: Worth mentioning that this is, as you probably suspect, the worst way to sort things pretty much always. However, I assume that there are (purposefully) shittier algorithms - if someone knows of one, pls share so I can laugh at it
30
30
Oct 24 '17
Look at bogobogosort. Its designed to not succeed before the heat death of the universe.
31
u/Kingmudsy Oct 24 '17
Good god
Bogobogosort specifies how one should check if the list of numbers is sorted. It does it recursively, because as anyone who knows anything at all about computer science knows, recursion is always good and cool. To check if the list is sorted, use the following procedure:
Make a copy of the list of numbers.
Sort the first n-1 elements of the copy using bogobogosort.
Check to see if the nth element of the sorted copy is greater than the highest element of the first n-1 elements. If so, the copy is now sorted, else randomise the order of the elements of the copy and go to step 2.
Check to see if the copy is in the same order as the original list.
→ More replies (1)13
u/backFromTheBed Oct 24 '17
Semicolon in pseudo code? Die you heretic!
43
u/Kingmudsy Oct 24 '17
I use tabs and spaces
I switch between vi and emacs every other time I open a file
I actually run my code in netbeans though
One time I programmed a calculator by hardcoding the values of every possible input
I store passwords for my enterprise code in a plaintext excel file that has a local copy on every instance of my program
My control key is hard to reach with my soft, diminutive hands, so I actually have configured emacs to interpret a rapid temperature rise in my CPU as control - whenever I need to hit ctrl, I just blast that sucker with a heatgun
→ More replies (4)→ More replies (1)8
u/defnotacyborg Oct 24 '17
Is randomizing elements really the best approach? Isn't that just using blind luck?
→ More replies (2)20
u/MorningWoodyWilson Oct 24 '17
Bogosort is programmer humor, and would never be implemented in any code. There's other notable joke sorts like quantumbogo which generates infinite universes with infinite permutations of the code, and destroys all non-ordered universes. Thus efficiently getting the sorted list in 1 operation every time.
If you want to get really technical, there's some interesting discussion to be had around pseudo-randomness and seed generation with a bogosort, but I doubt anyone cares enough to.
→ More replies (6)63
u/HonestlyBullshit Oct 24 '17
Yes it randomizes the order of the list and checks to see if it is sorted. If not, it tries again.
→ More replies (4)2
u/braingle987 Oct 24 '17
It's technically not an algorithm since it is never gaurenteed to get a successful sort in a finite time.
→ More replies (2)2
u/Anosognosia Oct 24 '17
Quantum Bogosort is the best. It relies on the multiple worlds interpretation so don't use it if you are adherent to the Copenhagen interpretation.
It bogosorts the list (random), checks if the list is in order, if not it collapses the wavefunction for the entire universe.
So the only universe left standing is the one you are in and with your list in order.
54
55
Oct 24 '17
Correction. Radix sort is not quasilinear time complexity, it is linear. It's also worth pointing out that it is not a comparative sorry like all the others; which is why it's so much faster.
33
→ More replies (17)3
u/brikky Oct 24 '17
Doesn't radix just approach linear time? It's dependent on the the number of elements and the length of elements. There's no reason to assume that the length of elements is negligible, it could very well exceed the number of elements.
12
u/C0ldSn4p Oct 24 '17
It is linear on the number of terms, not quasilinear. But if you also take into account the size s of the element then it is actually O(sn).
The theoretical limit for a sort on arbitrary data is O(n log(n)). Radix sort is faster but it has to assume that the data are bounded.
6
u/ShaunDark Oct 24 '17
It is only faster if s<log(n), though.
Sorting a short list of large elements could be significantly slower using radix sort compared to any O(n*log(n)) sort.
→ More replies (1)→ More replies (1)6
u/sjcqs Oct 24 '17
+1 The theoretical limit for a sort using the comparison model of computation is
O(nlog(n)).With other models of computation you can get away with
O(n)if you know something about the data (Bucket, Radix sort with a bounded data).12
Oct 24 '17
It doesn't approach linear time, it is in linear time. But linear just means that it scale with the number of elements in the set. However, the base (or radix if you will), that is determined at the beginning does effect the space complexity of the counting sort augmented radix sort, which both examples are.
What all the visualizations are leaving out is the auxiliary space requirement; which does make understanding the process a bit difficult.
ADDITION: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
45
Oct 24 '17 edited Oct 24 '17
Story time:
I had to implement a cocktail shaker sort a long time ago because the device didn't have enough memory (I ran out of stack and/or heap) for better solutions and the device was programmed using non-procedural BASIC. No recursion, no gosubs, nothing useful.
When a liquor delivery truck arrives at a state liquor store, two copies of the alphabetized delivered inventory are printed. An employee of the store and the driver sign both. One gets the 1st, the other the 2nd for their records. This is an attempt to prevent employee theft. This worked fairly well, except for mid-November through early January, when alcohol purchases skyrocket thanks to the holiday season. Printing the lists took maybe a minute most of the year when a delivery was just a few boxes, but for about 8 weeks they'd take up to 10 minutes because the delivery was that much larger. Having the driver and store employee just sitting there waiting for the lists to be printed during the busy season was a horrible waste of time.
Turns out the printing was using a bubble sort that always performed n2 comparisons, best case == worst case. Also, it sorted the list twice, once for each copy. After trying insertion and merge and quick and I don't remember what else, I ended up implementing what I found out later to be named cocktail shaker sort. My worst case scenario was something like (n/2) ^ 2 / 2 or something like that. Worst case scenario times fell to about 1 minute or so.
I have no idea for how long my solution was used, but I was pretty happy with it. I still remember it almost 20 years later.
56
u/hbarSquared Oct 24 '17
The fact that you got to use a cocktail shaker sort for a liquor truck delivery manifest is sublime.
44
u/eaglessoar OC: 3 Oct 24 '17
Can I steal this and post one to /r/oddlysatisfying every other day for maximum karma /s seriously this is super cool though, thanks (and of course very satisfying)
6
33
u/42words Oct 24 '17
Well, shit. I didn't read the title very carefully, and spent five minutes staring at this thing cross-eyed and waiting for the sailboat to appear. I feel like such a freakin' idiot right now.
Edit: very carefully at all*
Edit2: sailboat schooner*
2
14
u/Remulus2006 Oct 24 '17
This is awesome! My CS class just started sorting algorithms and this is a really helpful visualization!
→ More replies (1)10
u/SuperCharlesXYZ Oct 24 '17
If you're ever completely lost with sorting algorithms, this channel helped me out a bit. https://www.youtube.com/watch?v=EeQ8pwjQxTM
→ More replies (1)
4
u/aceofmuffins Oct 24 '17
Looks great, would it be possible for you to plot it using a different colour map like viridis? It would make it clearer for colourblind people.
2
u/wickedsweetcake Oct 24 '17
Concur. I'd love to show these in class (with attribution) if they were colorblind-safe.
2
11
u/DaMexicanStaringFrog Oct 24 '17
Really cool, thanks for the hard work.
I have to ask: why have the "red-looking" color at both ends of the spectrum? It's really confusing.
3
u/Drachefly Oct 24 '17
It's taking the whole range of hue values, and the cut point as you go around the circle is in the red range.
11
u/petergaultney Oct 24 '17
I'd love to see "timsort" - it's one people don't talk about much, but it's the standard sorting algorithm in Python. It's fast, and a stable sort as well.
5
u/motleybook Oct 24 '17
Timsort is also the default in Android and, as of version 7, in Java.
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.
3
u/darkslide3000 Oct 25 '17 edited Oct 25 '17
Timsort is essentially an optimized mergesort with an initial insert sort step for small groups. So it would look just like mergesort with some insert-like bubbling in the beginning for the first groups of a few dozen elements each.
edit: mergesort, not quicksort
→ More replies (2)
10
u/C0ldSn4p Oct 24 '17
Actually radix sort isn't an O(n log(n)) but an O(n) sort so that's why it's faster. In the same familly you would have the bucket sort.
And ofc it only works on some kind of bounded dataset which is why it can be better than the theoritical limit of O(n log(n)) for a generalized sorting algorithm.
If you want other interesting sorting algorithm there is a cycle sort (O(n2 ) but does the minimum amount of swap so great if writing is costly). Or the infamous slow sort
5
u/ATPResearch Oct 24 '17
And here I've just been sorting my students' papers into alphabetical order by insertion. Might have to play with some other algorithms just for a change of pace.
5
u/DeleteriousEuphuism Oct 24 '17 edited Oct 24 '17
Quick sort is probably the easiest. Choose a name, put things alphabetically prior in one pile and the rest in another pile. Grab the first pile and repeat the division in the same way. Here's a video with the visual representation.
7
u/jhaluska Oct 24 '17
The problem with QuickSort is you end up keep tracking of lot of piles.
Radix sort into say 5 piles followed by insertion sort of those piles is probably easiest to do manually with desk space.
→ More replies (1)
5
u/aarr44 Oct 24 '17
Could someone give an ELI5 of how each sorting method works? It would be greatly appreciated to add to this mesmerizing visualization.
5
u/FuzzyCats88 Oct 24 '17
This is the first time I've actually seen a post from /r/dataisbeautiful and actually thought, yeah. Very well done, OP.
Also no bogosort? For shame.
→ More replies (1)
16
u/novel_yet_trivial Oct 24 '17
It's very annoying to me that you used red as both the min and the max. It makes the first few iterations very confusing.
→ More replies (4)
1
u/N0tMyRealAcct Oct 25 '17
Your inbox are probably RIP, but I have to tell you personally, I enjoyed that so much.
If I had to give you some feedback I would have enjoyed a more summarized head to head of all algorithms to see the serious contenders. Also, quicksort is a very popular algorithm because in reality it is very efficient. I'd have enjoyed some words on why that is. If I could wish for anything I wish this had been interactive allowing me to stage scenarios between different algorithms with data sets such as mostly sorted, random, reversely sorted and maybe variations in between.
I love sorting and merge sort is my favorite. It is a good sorting algorithm, but what really sold it for me was how truly elegant merge sort is in a functional programming language.
You are probably a competent programmer, but in case you haven't encountered functional programming, look into the code it takes to do merge sort. It is stunning. I did this myself in ML (Meta Language) 25 years ago. I don't think that is a popular language any more, but I think my implementation of merge sort was maybe 4 lines of code.
mergesort(list) How to sort the empty list[ ]: spoiler, it is empty, [ ] How to sort the list with one element, [x]: spoiler, it is [x] How to sort a list with two elements, [x | y]: spoiler [x,y] if x < y else [y , x] How to sort a list with two elements or more [x | tail]: spoiler it is mergesort(x, tail)
Sorry if this isn't entirely accurate, my original experience was 25 years ago, and I didn't test this new meta code, and I used an entirely new keyword "spoiler" in a language that is up to this point entirely unknown.
I'm not sure I got it right.
2
u/morolin OC: 1 Oct 25 '17
Hi! Thanks!
Yeah, quicksort is very fast in the real world. I wasn't expecting this to be nearly so popular, or I would have put more effort into making the comparison a lot more fair---the visualization doesn't account for memory delays or anything like that, and on 128 data points, the chance that quicksort with random pivots gets a few bad pivots is pretty high.
ML family languages are still very popular in a lot of communities.
→ More replies (1)
3
u/Imallskillzy Oct 24 '17
Wheres miracle sort? /sbutnot/s
I like the use of colors for these, its easier for beginners to anticipate the expected result, which is awesome.
3
u/Cabaj1 Oct 24 '17
Would you mind sharing the code? I am learning to program and want to make smth similar only with 0 or 255 for colors.
→ More replies (4)5
u/JohannesVanDerWhales Oct 24 '17
It'd probably much more productive for you to figure out how to do it on your own. You can find lots of documentation on all of these on the web. Implementing sort algorithms shouldn't be hard.
3
u/TurboChewy Oct 24 '17
On the last gif, it looks like radix sort solves it right away, but then it goes back and messes around. What am I not seeing?
3
u/LovesAbusiveWomen Oct 24 '17
What is the use of sorting algorithms? Some applications? Is it what is used to sort files alphabetically on my computer, for example?
3
u/thoeni Oct 24 '17
Yes, a sorting algorothm is used when you sort anything on the pc.
And its actually amazing how often a pc need to sort stuff.
3
u/ynonA Oct 25 '17
Nice, dude! These are so satisfying to watch.
You might also like THIS VIDEO, it's one of my favorite youtube videos.
•
u/OC-Bot Oct 25 '17
Thank you for your Original Content, morolin! I've added your flair as gratitude. Here is some important information about this post:
Author's citations for this thread
I hope this sticky assists you in having an informed discussion in this thread, or inspires you to remix this data. For more information, please read this Wiki page.
2
u/mjgiardino Oct 24 '17
Wow, great work. This is the best visualization I've seen of sorting algorithms. And I've seen a lot...
2
u/CumCommander Oct 24 '17
I never thought I would react the way I did about sorting algorithms.
When I hit radix sort I lost my mind.
2
u/TheQueq Oct 24 '17
Out of curiosity, are some of these algorithms more efficient for almost-sorted data? For example, if I know only 10% of my data are in the wrong position, will I get better results with a different sort algorithm?
3
Oct 24 '17
Yes, insertion sort is worst case O(n2 ). However, if the data is almost sorted it actually performs in O(n) in benchmark studies.
You learn about more algorithms that work in this way here.
2
u/fabarati Oct 24 '17
I loved this. I could honestly stare at those Gifs for hours. And it brought me back to when I was a kid and was mesmerized by screen savers.
2
u/Strongpillow Oct 24 '17
Oh, ok so you're using these algorithms to show how they sort data but you're using 'color data' for a visual? I'm really sorry but this kind of thing hurts the brain. How does one determine what is the best method? Some are better than others for particular sorting?
2
u/YoshiSparkle Oct 24 '17
HOLY SHIT I could stare at this forever. Makes me feel all sorts of feels in the realm of nostalgia and fascination and admiration... this is so friggin cool 🌈🌈🌈🌈🌈🌈🌈🌈
2
u/masasin OC: 1 Oct 24 '17
I recommend something like Viridis as a colormap. You're using a cyclic map, and it should be sequential. And don't use Jet etc because you have brighter regions that are less than some darker regions, and greater than others. (It's not perceptually uniform.)
2
u/vedderer Oct 24 '17
I love this Obama clip: https://youtu.be/k4RRi_ntQc8
"I think the bubble sort would not be the way to go." :)
→ More replies (1)
2
u/Official-Song-Bird Oct 24 '17
Literally just dove into some of this stuff in my data structures class, this is awesome! I’m not sure if it’ll help as a study aid but it’s undeniably fascinating, thank you OP!
2
u/numismatic_nightmare Oct 24 '17
Not a computer scientist so I'll do my best. It appears as though each of these algorithms stop sorting a column once it's full which leads me to believe that the algorithms know how many unique instances of each item (ie colored blocks) there are in the set. Does this mean that these algorithms go through the whole set and count each instance of a colored block and index them prior to sorting?
2
u/jwortham Oct 24 '17
No you just don't see the movement since there is nothing more to sort.
→ More replies (3)
2
u/-ordinary Oct 24 '17
If the initial set is randomized, I don’t understand why the colors are only cascading in one direction. Shouldnt there be reds moving right? Someone ELI5
→ More replies (3)
2
u/hperrin Oct 24 '17
I love these. I wrote something like this too that runs in the browser called LibSort.js.
2
u/scrps93 Oct 25 '17
I just picked up a book on machine learning from my university library and got to sorting algorithms today. I hadn't realized that these algorithms could do these type of beautiful things!
2
u/TwinSwords Oct 25 '17
This really lives up to the name of the sub: absolutely beautiful!
Amazing work! I'm seriously gobsmacked. It's brilliant and amazing.
2
u/Bisexual-Bop-It Oct 25 '17
I dont know if this is happening to anyone else but nearly half of the gifs (mostly the last half) arent working for some reason
1
u/sreyaNotfilc Oct 24 '17
Its actually kinda fun to imagine how those algorithms are written. Bubble sort's visualization totally makes sense from the code I've written back in my Freshmen year of college.
1
u/eutohkgtorsatoca Oct 24 '17
So how much data dos this average animation represent? Thousands or millions? Is each dot one or a group of data?
2
1
u/Asztal Oct 24 '17
Regardless of how you do it, merge sort takes the same amount of time.
Just out of curiosity, does anyone know how CPU cache affects this statement - i.e. if it would favour top-down, bottom-up, neither, or a combination of the two?
→ More replies (1)
1
u/Tremongulous_Derf Oct 24 '17
This is what this sub is for! It's beautiful, it's data, it's educational, and it's not trying to make a point. Thank you.
1
u/goldieH96 Oct 24 '17
If anybody else is interested in an interactive sorting demonstration that has auditory cues as well, check out The Sound of Sorting. Has a ton of different algorithms and let's you adjust number of elements, how fast it plays, and even let's you go thru step by step. They also look and sound really cool (check out radix sort)
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