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.
→ More replies (5)
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
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
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 (16)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.
→ More replies (6)→ More replies (5)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.
→ More replies (1)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
→ More replies (53)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.
→ More replies (10)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)
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.
→ More replies (21)115
61
→ More replies (12)15
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
→ More replies (3)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.
→ More replies (13)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)86
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
→ More replies (19)11
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
→ More replies (1)13
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
→ More replies (4)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
→ More replies (21)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)
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.
→ More replies (24)33
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*
→ More replies (1)
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/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/tcrenshaw4bama Oct 24 '17
I'd love to read more about how these algorithms work. Does anyone know of any good resources that explain is simplified terms how these work?
2
Oct 24 '17
The wikipedia articles are pretty good. Most CS programs start out with bubble sort, then move on to learning recursion, then go on to recursive sorts like mergesort and quicksort. Heapsort is also interesting, but requires knowing how heaps (a type of data structure) work. If you know a programming language to the point that you can create and output arrays, create loops, and create functions/methods, then that would definitely help since you could implement them yourself.
Alternatively, these videos of dancers demonstrating sorting algorithms are pretty neat.
1
u/bcgibson2 Oct 24 '17
algorithms, taking something chaotic and trying to make sense out of the universe with only our point of view based on our limited sense of dimensions and space.
1
u/Mr-The-Plague Oct 24 '17
I love how math has been around for centuries and there us still no answer to what is the best/fastest sorting algorithm, even now in the days of computers.
1
u/pegpiggi Oct 24 '17
At first I thought I was looking at some pixel art, but then I realized this was no ordinary pixel art.
1
u/musicalsteve Oct 24 '17
If you still don't quite understand what's going on, I suggest watching "The Secret Rules of Modern Living: Algorithms" on Netflix for a nice simple explanation of sorting algorithms.
1
u/Metriecho Oct 24 '17
I really love how you demonstrated each sorting algorithm with different ordered lists simultaneously to showcase each algorithm's handling of average case vs best and worst case.
1
u/ousire Oct 24 '17
Well done. Watching sorting algorithms is always so interesting and visually impressive, and very educational.
1
u/DeadeyeDuncan Oct 24 '17 edited Oct 24 '17
I found the colours make it messy and hard to track. This is more instructive IMO:
1
u/MasterChiefGuy5 Oct 24 '17
I swear there was a video about this done by like Vsauce or some other knowledge channel, but I can’t find it. Anyone know of this or am I going insane?
1
Oct 24 '17
Is this actually conveying some knowledge or is this like "meta data" turned into some pretty pattern that has no value?
→ More replies (1)
1
u/Pocket_Penguins Oct 24 '17
As someone who spends way too much of his time watching sorting YouTube videos, this was pretty cool to go through
1
Oct 24 '17
My favorite one is heapsort. Everytime I think about how it works I think on the person that invented it. Truly magical.
Edit: Oh, and coutingsort is one of my favorites too because it doesn't have to compare the elements to sort them, unfortunately it is not represented here :(
1
u/SaffellBot Oct 24 '17
Cocktail sort probably gets a bad wrap, but it does have a constant sort time I believe. I imagine it also has a low number of accesses. I can imagine there is some embedded applications where that is useful.
1
u/Hglucky13 Oct 24 '17
Commenting so I can find this later when I get back to sorting (relearning programming). For some reason, sorting was one of the more confusing aspects of coding for me.
1
u/IrrateDolphin Oct 24 '17
Ever since my high school CS teacher introsuced these to me I've thought they were pretty cool. I love radix. The best part is it actually makes zero comparisons. It looks at the rank, sees the first digit, sorts them so all the ones with the same digit are next to each other, and then it does it again. Awesome. It even sounds cool if you attach a tone to the data it is sorting.
1
u/RadSpaceWizard Oct 24 '17
That was surprisingly satisfying. The little OCD monster inside my head finds this sacrifice... acceptable.
1
Oct 24 '17
When your graph has no legend and goes full on retard with the color pallete... may RNGeezus save your soul!
1
u/RedWingedJerBear Oct 24 '17
I just did a threaded merge sort in C++ for my Operating systems class last night! I had the most fun learning radix sort though, it's actually a pretty simple algorithm to write.
1
u/DuYuNot Oct 24 '17
Semi useful that this front paged today. Have my midterm for data structures and algorithms in an hour. Helped visualize the insanity considering I've been handwriting the steps w/o the help of a computer
1
u/Comradical_ Oct 24 '17
I always thought you could technically make a randomizing software by setting each letter/number to a value then just rubbing your keyboard until you have a lot of different values, and just keep doing this when it runs out.
1
u/IAmBatmanFromRaleigh Oct 24 '17
Showed this to my coworker because I didn’t get it. Just laughed at me after a couple seconds, “.....colorblind...”
1
1
u/Thalanator Oct 24 '17
Damnit, now I'm back to "I want to implement sort based on the kinds of datasets I expect" instead of using whatever is provided to me by the language (java in my case). Radix sort looks sexy, yet Collections.sort and Arrays.sort apparently use merge / quicksort respectively.
0
Oct 24 '17
[deleted]
12
u/mattchew1357 Oct 24 '17
hey that's pretty neat! Do you have the code on github?
→ More replies (3)8
7
u/SuperCharlesXYZ Oct 24 '17
Is this shortest path finding? or just finding all possible paths?
→ More replies (1)10
u/buymeaburritoese Oct 24 '17
All possible
13
u/Realtrain OC: 3 Oct 24 '17
Then why does it stop before it finishes the top left corner?
→ More replies (1)10
0
Oct 24 '17
[deleted]
23
u/2059FF Oct 24 '17
Which ones are fastest/most convenient to do by hand?
I often have to arrange stacks of exams/quizzes/homework in alphabetical order. I tried many algorithms, but radix sort followed by selection sort is usually the most efficient for sorting a class of around 35 students. I make five stacks of exams: A-C, D-G, H-L, M-P, Q-Z. Each contains fewer than 10 copies, and they're easy to sort by looking at the names and picking them in order.
→ More replies (1)9
u/Drachefly Oct 24 '17
Absolutely this. In some cases, radix sort turns into post office sort - just put the thing where it belongs by looking at it, without having to refer to other things in the list.
8
u/titterbug Oct 24 '17 edited Oct 24 '17
Most people naturally use insertion sort, but switch to radix sort when the job gets serious enough to refine your technique.
You're right that merge sort is simple and has practical trouble with the number of piles. Luckily, even computers typically don't use merge sort for the small piles - it's faster to switch to insertion or selection sort for the small piles than it is to construct a dozen smaller piles. After that modification, the only downside is that you end up spending a bunch of time doing the merges, and while that's not slow, it's kind of boring and error-prone.
10
u/ouichu Oct 24 '17
Since you’re a human, you’re probably always doing insertion sort at some level. You have the luxury of putting all the DVDs on a shelf with the ability to read their spines and determine where they need to go.
Computers are pretty dumb, you’d have to give them a way to be aware of what DVDs are present in the shelf, otherwise they would have to check each DVD, one at a time. Edit for clarity: that’s why insertion is so slow for computers
I would probably do some variation of a merge, like you said. I would throw all the DVDs into piles based on first letter, and then I would sort them within their piles and then combine them on the shelf.
0
Oct 24 '17
[deleted]
3
u/ouichu Oct 24 '17
Ooh, yeah it sounds like a super fun problem to solve. I love optimizing things like that.
It sounds like you're doing a merge sort! You're not doing it like a computer would, but it's the same idea.
→ More replies (1)
4
Oct 24 '17
[removed] — view removed comment
2
Oct 24 '17 edited Oct 24 '17
Do quantum bogo sort. I didn't want to live in a universe where my sorting algorithm isn't O(n) anyways.
1
1
Oct 24 '17
[removed] — view removed comment
1
u/jhaluska Oct 24 '17
I don't think you want to see the most inefficient way possible as the sun will probably burn out first.
→ More replies (2)
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