r/programming • u/compilerstuck • Sep 21 '20
I Created a Visualization of 20 Sorting Algorithms with Java. Which one do you like most?
https://www.youtube.com/watch?v=AVt0lAklAtM36
u/General_Urist Sep 21 '20
I know insertion sort is supposed to be slow, but 2.9 x 107 milliseconds (8 HOURS!) real time to sort a 1920 element list when almost everything else does it in less than 100? You sure that's right?
33
u/compilerstuck Sep 21 '20
Yes, I've had a bug while calculating the real time for insertion sort. good catch
31
69
u/Fredrickjonjones Sep 21 '20
This is super satisfying and cool as hell -- How did you create the visualization? I've been interested in graphics to accompany algs of mine for a while but have yet to find anything substantial.
55
u/compilerstuck Sep 21 '20
I did it with Processing. It is super easy to understand. :)
44
u/ThisIsMyCouchAccount Sep 21 '20
Computer processing?
28
u/compilerstuck Sep 21 '20
Click on the link. It is a library for java to visualize stuff http://processing.org
72
25
u/compilerstuck Sep 21 '20
Hey yall!
This is my Try on writing a Visualizer for Sorting Algorithms. I am currently doing a series of this, trying to find new ways to Visualize these. My last one was a 3D Spinning Cube.
This series will continue on my YT Channel.
Let me know what i could improve below :)
6
u/JackandFred Sep 21 '20
Do you post the code anywhere? (Or is it in the videos, I can’t watch right now)
2
0
16
u/rabid_briefcase Sep 21 '20 edited Sep 21 '20
Animations interesting to watch. You might consider color or something rather than the uniform red, but that's stylistic.
For the analysis, I find the "real time" number quite odd. Timing is always a problem on demos like this. Big-O notation is useful when the number of items dwarfs all other concerns, but for 1920 elements the CPU cache effects will be overwhelming. If anybody's code took 45ms to sort 1920 integers, or 141ms for shell sort, 49ms for heap sort, etc., I'd call that strongly into question.
Video games can process the entire world and display millions of triangles every graphics frame of 16ms or less, but this code can't even sort 2000 integers in so many graphics frames? What's up with your real time numbers? I imagine them hitting microseconds for some of the slow sorts, but milliseconds is odd unless you're using computers from many decades ago.
5
u/hexanerax Sep 22 '20
Probably includes the visualization code inside the sort algorithm.
1
u/compilerstuck Sep 27 '20
You are right. The Sorting is running in another process.
The algorithms might take longer because i am visualizing the stuff at the same time. But it's fine for me, cause you can clearly see the differences between the algorithms
4
2
u/JohnWangDoe Sep 22 '20
amazing work
1
u/compilerstuck Sep 22 '20
Thanks :)
1
u/JohnWangDoe Sep 22 '20
do you think its possible to visualize neural networks with your method?
1
u/compilerstuck Sep 22 '20
What exactly do you want to visualize?
2
u/JohnWangDoe Sep 23 '20
Not quite sure. Can I get back to you on this, I will be swinging around to Deep learning stuff next month.
1
23
22
13
7
u/sephirothbahamut Sep 21 '20
I love radix, but i suggest you add bitonic, that's a really crazy one to look at
2
14
u/IIDaFuQII Sep 21 '20
Can someone explain to me why insertion sort absolutely wipes the floor with any other algorithm here?
37
u/omgnowai Sep 21 '20
Pay attention to the real-time. It's one of the worst even though the visualization runs quickly.
0
Sep 21 '20
[deleted]
18
u/compilerstuck Sep 21 '20
Yes, i've apparently got a bug measuring the real-time. I'll fix it in the next one
0
Sep 21 '20
[deleted]
8
u/VerumCH Sep 21 '20
The video shows the actual compute times for each algorithm with the given dataset. Under the constraints, Counting Sort was the 5th fastest:
Double Selection Sort
Quick Sort (Pivot Middle)
American Flag Sort (never heard of this?)
Selection Sort
Counting Sort
Don't remember the O notation for these off the top of my head, so these rankings may change drastically with different inputs.
2
2
u/AdultishRaktajino Sep 22 '20
Tim sort was cool. Reminded me of playing Missle Command on the Atari when I was a kid.
1
2
u/Liutvis Sep 22 '20
What if our entire universe is just someone's fancy visualization of a sorting algorithm?
1
2
u/Gremis Sep 22 '20
I love these kind of videos. Thanks for sharing. :-)
One of my favorites in this caterory is the one by Creel where he held a sorting Olympics and raced 7 different algorithms.
1
2
2
u/1LJA Sep 22 '20
Quantum Suicide Sort. Randomize your list. It your list is not in order, kill yourself. You will be left in the universe where your list is in order.
2
2
u/Funduval Sep 22 '20
lol to all the comments that are like "but can you do this instead?" and not telling you how great this is first. Thanks for this. I found it mesmerizing.
1
2
u/Planebagels1 Sep 22 '20
lyrics: bwebwbebwbebwebububuwbewbewubebwueuwue bweeeeeeeeeeeeeeeeeeeeeeeeeeeeeuuuuuuuuuuuuuuuuuuuuuuuuuub bebwbebwbebwebwbewbewbebwbbewbeb.........
2
2
u/_sadme_ Sep 22 '20
Did you experiment with non-random sets? Those algorithms may be less effective in the following scenarios:
Only even or only odd numbers
Data already sorted, but in reverse order
Only low and high numbers (no values close to the mean value of the set)
Sorted values, but with some "noise"
Unevenly distributed values in set (90 percent of values is between the lowest one and 1/10th of the maximum value)
1
3
u/keepitreelin Sep 21 '20
Similar videos by Timo Bingmann https://www.youtube.com/c/TimoBingmann/videos
1
64
u/jtooker Sep 21 '20
Gnome sort is the best sort!
Gnome sort is the simplest sort to implement. It is O(n^2), so obviously not useful in production.
55
120
u/RockyRaccoon26 Sep 21 '20
My preference is Quantum bogosort. randomize the data set, check if sorted, if it isn’t, destroy the universe. In some parallel universe it was sorted instantly and that’s good enough for me
33
u/MMPride Sep 22 '20
Wow, you solved O(0), impressive!!
25
u/ProgramTheWorld Sep 22 '20
It’s O(n) because you need to check whether it’s sorted.
16
u/timeshifter_ Sep 22 '20
Assume it's sorted, and if the process that requires it to be sorted fails because it wasn't sorted, you're in the wrong universe.
With that thought, why even bother sorting? O(null)!
2
u/RockyRaccoon26 Sep 22 '20
We are at least assuming the data needs to be sorted
2
u/timeshifter_ Sep 22 '20
And my algorithm assumes that it already is.
The real question is, are you in the right universe for that assumption to be true?
4
1
11
u/techtreedev Sep 21 '20
Bogo sort is better O((n+1)!)
5
10
u/GreenCloakGuy Sep 22 '20 edited Sep 22 '20
Gnome sort is the simplest sort to implement
I defy this. A rudimentary selection sort is even easier.
def selection_sort(arr): for i in range(arr): for j in range(i+1, arr): if arr[i] > arr[j]: arr[i], arr[j] = arr[j], arr[i] return arrThough Gnome Sort is a favorite of mine.
9
u/the_real_zaphod_b Sep 22 '20
I disagree, Intelligent Design Sort is even easier. And it's
O(1), which makes it very production ready.2
14
u/tobiastros Sep 21 '20
That was satisfying. I like the visuals for some of the sorts mimic their namesake. Like comb and bubble. Great work!!
5
u/iphony65 Sep 22 '20
Tim sort did it for me...
2
u/AdultishRaktajino Sep 22 '20
Me too. Said it in a different reply, but reminds me of an old Atari game.
0
Sep 22 '20
[deleted]
1
u/iphony65 Sep 22 '20
Is there some divide and conquer going on there? Has a bit of similarities to merge
4
4
6
u/Isvara Sep 21 '20
For me, most of these don't really seem to show what's going on. You don't so much see points moving, more like some points disappearing and other points appearing elsewhere. It all happens too quickly for the best sorts.
-1
u/caltheon Sep 21 '20
Without knowing how the sort algorithms work beforehand, these are terrible visualizations for most of them to deduce how they work. They compliment but do not explain. Not sure why so many people are praising this as I've seen far far better videos of the exact same thing.
11
u/njtrafficsignshopper Sep 22 '20
Because it's not the point. This is about seeing the effect on the data in aggregate over time, so you can observe the patterns. It's not for explaining how each one works step by step. Explainer videos use much smaller data sets and walk you through each step, and you don't see the big effects. This video is obviously not for the same purpose.
1
u/Rocky87109 Sep 22 '20
Assuming they are accurate/consistent in some way I think it's just cool aesthetically. Makes me want to go learn them all. I need to anyway.
3
3
1
2
u/BackmarkerLife Sep 22 '20
I like to think all of these are Megaman levels. Especially Quick and Bubble sort.
2
2
2
2
u/Boux Sep 22 '20
TIL sorting algorithms are just oldschool German techno in disguise https://youtu.be/_sbIzaO5JhE?t=382
2
2
u/Flacrazymama Sep 22 '20
Okay, I have no fricken idea what I just watched but here's my unqualified feedback of my reactions. Most pleasant-Tim. Least pleasant-Shaker Cocktail. Hurt my eyes-Radix. Most annoying-Comb. Space Invaders(ish)-Gnome. Flashback of Peter Gabriel's Sledgehammer video-Odd/Even.
2
Sep 22 '20
Merge sort. Because it was created by John von Neumann in 1945, and if he was alive today, with today’s computers, he’d create a new sort that was better than anything the rest of us could come up with.
2
2
u/muntoo Sep 22 '20
Forget the visualizations. The real juice is in all those weird semi-randomized arpeggios.
2
2
2
Sep 22 '20
A-. Amazing effort and great execution. You lost points because you're from one of those backwards countries where comma is the decimal.
2
2
2
u/EricIO Sep 22 '20
My and my friends did an experiment on how long it would take to ShuffleSort (1. Shuffle 2. See if sorted 3. If not sorted goto 1) arrays of increasing length.
After 4 days of shuffling a length 6/7 (can't remember exactly) array my VPS provider rebooted the VPS since they thought something was wrong and it was "endangering other nodes"...
2
2
2
2
2
u/KillerKingTR Sep 22 '20
I am disappointed there is no bogo sort. I was looking forward to it
Ps:does anyone have a video of a successful bogo sort?
2
u/greyfade Sep 22 '20
Two algorithms that I love but rarely see (except recently in musicombo's videos) are Smoothsort and Poplar Sort.
Those two, Shaker sort, Circle sort, and Comb sort are the only algorithms that give me any sense of satisfaction, and Quicksort is the only other one that gives me any sense of reasonableness (for lack of a better word).
2
2
u/ilolus Sep 21 '20
That bucket sort blew my mind
2
u/Ksevio Sep 22 '20
Does take quite a bit of memory which makes it unreasonable for sorting many numbers
2
2
u/metriczulu Sep 21 '20 edited Sep 21 '20
What's going on here? What does the two dimensional nature of the points represent?
2
u/hungrynax Sep 22 '20
Y is size, X is position in an array. When it is sorted it goes from small to large in both size and placement, so it is a straight line. Is that not obvious?
1
1
u/Uberhipster Sep 22 '20
sound is creepy tech noir
cant wait to hear someone incorporate that into a scifi movie about teenage mutant replicant androids
it can be the matrix mainframe's hive-mind language
1
u/tias Sep 22 '20
I would love it if somebody could think up a good way to visualize cache usage while the sorting algorithm is running.
I know how the algorithms work by now but don't have a really good intuitive feel for how the different access patterns affect memory latency. Same goes for branch prediction I guess though that seems even harder.
1
u/Uberhipster Sep 22 '20
what is the purpose of so many sorting algorithms besides the highest performing two/three?
let's say selection, counting and bucket should cover all possible 'time v resource' drawback circumstances
but then why a dozen others? purely educational or are there actual use cases where you would want to use eg Gnome sort or Cocktail Shaker sort because it's legit better to use those instead of any of the top 3?
also - the end summary comparison table is displayed unsorted
ಠ_ಠ
1
u/jambonilton Sep 22 '20
I'd be interested in seeing the same thing with multi-threading to see some of the divide-and-conquer ones shine.
1
1
1
u/superhighcompression Sep 21 '20
Didn’t watch the video but bubble sort all day! Fuck yo ho ass nlogn Bull shit
1
u/dnabre Sep 22 '20
Is there a standard set of sound effects for these things. I've seen scores, if not hundreds, of them over the years, and so many seem to all have the same sounds, or at least very similar sounds .
-3
u/realnzall Sep 21 '20
Why does every single visualization sound so obnoxiously bad. Is it something with the sound selection algorithm?
3
u/evincarofautumn Sep 22 '20
Yeah, it’s nontrivial to select pitches that sound good, so these videos typically just use a linear mapping from value to pitch, and a simple waveform (sine/square/sawtooth/triangle) that’s easy to generate
In order to produce something that sounds better, you’d need to consider many things with complicated tradeoffs, including:
Intonation—making values correspond to the pitches of standard notes
Harmonies—selecting a scale that sounds reasonably harmonious for any two numbers that will be compared
Range—mapping a wide range of numbers onto a range of notes that are neither too low nor too high (i.e. it’s easy if you only have a few values, but then the visualisation isn’t interesting)
Timbre—accounting for overtones and waveforms to produce a pleasing texture
I think the programmers making visualisations of sorting algorithms are just not usually the same people as the music and sound experts who can design good “audiations” like this
1
0
u/myfunnies420 Sep 22 '20
It's a bit odd that the sort time doesn't match the animation time at all.
-1
u/redhat-- Sep 22 '20
Please suggest me a way to get internships in IT companies during my college time
0
Sep 21 '20
[deleted]
29
u/compilerstuck Sep 21 '20
exactly
17
u/Isvara Sep 21 '20
I thought it was the other way around. Why do the dots move upwards in, say, Gravity sort? Surely their value (X axis) stays the same, but their position (Y axis) is changing as the sort moves them around.
8
u/yakoudbz Sep 22 '20
I was thinking the same thing. The visualization does not seem to be consistent
1
u/PM_ME_A_NUMBER_1TO10 Sep 23 '20
Having reviewed gravity sort, this visualisation is fine. I think you just don't understand what gravity sort is.
Each position in gravity sort corresponds to a value, any excess is carried over to the adjacent position. The array values are modified and hence the y value changes but the x position stays.
It is a useless sort for anything but integers.
1
u/Isvara Sep 23 '20
I think you just don't understand what gravity sort is.
I can do better than not understanding it: I've never even heard of it.
1
9
Sep 21 '20
Thanks for asking. The resolution is so fine that I was getting confused thinking more than one value existed per position
0
0
Sep 21 '20
[deleted]
6
u/sylvanelite Sep 22 '20
Also is the visuals for BucketSort correct?
Bucket sort works by assigning a big auxiliary array and just slotting the elements into the array at the right index based on their value. It doesn't look like the animation shows the auxiliary array, so most of the work is hidden. Same goes for counting sort.
Also bucket sort is helped immensely given the type of data being sorted - a contiguous chunk of values makes bucket sort run in O(N) time, which is not the case for arbitrary data.
257
u/LegitGandalf Sep 21 '20
Do you have StalinSort in there? That's the one that just removes any elements that are out of order.