r/programming • • 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=AVt0lAklAtM
1.9k Upvotes

154 comments sorted by

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.

43

u/compilerstuck Sep 21 '20 edited Sep 22 '20

Just heard about it today. love it ^^

14

u/robbak Sep 22 '20

Don't forget quantum bogosort. Permutate the array using a source of quantum randomness, and if the array isn't sorted, destroy the universe.

4

u/compilerstuck Sep 22 '20

Good idea for the next video lol

4

u/robbak Sep 22 '20

Good way to end the video, I guess. Do "Quantum Bogosort (surviving universe)", then "Quantum Bogosort (other)."

1

u/ScientificBeastMode Sep 22 '20

It kinda seems like pattern matching on the universe itself.

14

u/Chii Sep 22 '20

And then spend minutes clapping at the sorted list.

4

u/[deleted] Sep 22 '20

in O(n)

0

u/[deleted] Sep 21 '20

[deleted]

12

u/compilerstuck Sep 22 '20

That would be a nearly endless video with ~2000 Elements to be sorted. lol

26

u/BlueAdmir Sep 22 '20

Be the change you want to see

1

u/klujer Sep 23 '20

Here's some pseudo code for some good ones, though existential sort may take a while to run.

36

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

u/[deleted] Sep 22 '20
//calculate insertion sort time
start_clock();
bogo_sort();
return stop_clock();

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

u/ThisIsMyCouchAccount Sep 21 '20

C'mon!

(╯°□°)╯︵ ┻━┻

I'm dropping comedy gold over here.

73

u/TheTomato2 Sep 21 '20

Hey!

  ┬─┬ノ( º _ ºノ)

Don't do that.

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

u/compilerstuck Sep 21 '20 edited Sep 21 '20

It is not public yet

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

u/AlaskaTuner Sep 22 '20

Upvote for answers, I was wondering exactly the same thing.

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.

23

u/BFG_9000 Sep 21 '20

It's really really good, but it's not Hungarian folk dance good...

6

u/compilerstuck Sep 21 '20

Haha! No one can beat them! <3

2

u/BesottedScot Sep 22 '20

My right ear loved this.

22

u/Karlomagno Sep 21 '20

No bogosort? *sad inefficient noises*

13

u/ScholarZero Sep 21 '20

Sorting algorithms go brrr

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

u/compilerstuck Sep 21 '20

Nice idea, might look into that :)

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

u/[deleted] 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

u/[deleted] 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:

  1. Double Selection Sort

  2. Quick Sort (Pivot Middle)

  3. American Flag Sort (never heard of this?)

  4. Selection Sort

  5. 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

u/1newworldorder Sep 22 '20

I half expected to see a rick astley sort at the end ngl

1

u/compilerstuck Sep 22 '20

Next time lol

2

u/AdultishRaktajino Sep 22 '20

Tim sort was cool. Reminded me of playing Missle Command on the Atari when I was a kid.

2

u/Liutvis Sep 22 '20

What if our entire universe is just someone's fancy visualization of a sorting algorithm?

1

u/compilerstuck Sep 22 '20

Always has been

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

u/compilerstuck Sep 22 '20

Haha, that's interesting! Thank you, had fun watching it ^

2

u/unc4l1n Sep 22 '20

And now I have a new interest. Thanks.

1

u/compilerstuck Sep 22 '20

you're welcome

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

u/compilerstuck Sep 22 '20

I'll try it next lol

2

u/1LJA Sep 22 '20

Can't wait to see the visualization of that.

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

u/compilerstuck Sep 22 '20

Thank you! <3

2

u/Planebagels1 Sep 22 '20

lyrics: bwebwbebwbebwebububuwbewbewubebwueuwue bweeeeeeeeeeeeeeeeeeeeeeeeeeeeeuuuuuuuuuuuuuuuuuuuuuuuuuub bebwbebwbebwebwbewbewbebwbbewbeb.........

2

u/compilerstuck Sep 22 '20

Uvuvwevwevwe Onyetenyevwe Ugwemuhwem Osas

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

u/compilerstuck Sep 22 '20

Yes i did. It is worth own videos for different shuffling methods

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

u/i_am_a_n00b Sep 21 '20

It works? Deployment set for Friday

2

u/waitwhat1200 Sep 22 '20

But like end of month Friday...

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

u/echoAwooo Sep 22 '20

Also serves to test multiverse theory. For science!

1

u/cowardlydragon Sep 22 '20

Um, that's RickNMortySort

11

u/techtreedev Sep 21 '20

Bogo sort is better O((n+1)!)

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 arr

Though 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

u/Bchung1999 Sep 21 '20

GNOME SORT FTW

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

u/[deleted] 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

u/[deleted] Sep 21 '20

Radix sort is always my favourite one to watch in these things.

1

u/dnew Sep 22 '20

You should go watch a punched card sorting machine. :-)

4

u/taste_fart Sep 22 '20

Dat double selection sort though 👌

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

u/ggchappell Sep 21 '20

Bubble Sort (2:20) and Heap Sort (5:22) both look pretty cool.

3

u/StylusScratchatorius Sep 22 '20

This would make an amazing screensaver.

1

u/fukmyelyfe Sep 21 '20

There is no rational reason for why I love this as much as I do..

2

u/BackmarkerLife Sep 22 '20

I like to think all of these are Megaman levels. Especially Quick and Bubble sort.

2

u/4rch_N3m3515 Sep 22 '20

Gravity sort was cool. You can visually see the analogy

2

u/sigsegv7 Sep 22 '20

bubble sort reminded me battle of bastards 😂

2

u/SlyRacoon22 Sep 22 '20

How did you get the sounds?

2

u/Boux Sep 22 '20

TIL sorting algorithms are just oldschool German techno in disguise https://youtu.be/_sbIzaO5JhE?t=382

2

u/JjMarkets Sep 22 '20

Amazing!

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

u/[deleted] 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

u/capsluke00 Sep 22 '20

Actually this got recommended me yesterday on yt. That's addicting

2

u/muntoo Sep 22 '20

Forget the visualizations. The real juice is in all those weird semi-randomized arpeggios.

2

u/VkrajaP Sep 22 '20

quick and gravity sort

2

u/IlIllIIIIIIlIII Sep 22 '20

I want to see parallelization on this next :o

2

u/[deleted] 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

u/elronnoco Sep 22 '20

Love the reverb!

2

u/All_the_lonely_ppl Sep 22 '20

Odd even is dope

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

u/redb2112 Sep 22 '20

My top 3 in order just from visuals:
Cocktail Shaker sort
Tim sort
Comb sort

2

u/Rocky87109 Sep 22 '20

That was pretty sweet. What made the different tones for the beeps?

2

u/NiteLite Sep 22 '20

I generally just call .sorted() on my stream and hope for the best :P

2

u/Manguana Sep 22 '20

I like the sound effects really gives you a sense of the progress

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

u/wtfismyjob Sep 21 '20

I recommend having these sound effects cut to an LP for real.

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

u/[deleted] Sep 21 '20

I love the sound effects! So retro!

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

u/DoNotMakeEmpty Sep 22 '20

Doesn't the edges Odd Even Sort look very surreal?

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

u/addamsson Sep 22 '20

This gnome sort was hellishly slow.

1

u/[deleted] Sep 21 '20

Nice one!

But isn't the video boring to watch? :\

3

u/unc4l1n Sep 22 '20

Depends on what sort of person is watching it.

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

u/Rocky87109 Sep 22 '20

I love it.

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

u/[deleted] 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

u/PM_ME_A_NUMBER_1TO10 Sep 23 '20

I didn't either lol. Its practical uses are basically 0.

9

u/[deleted] 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

u/[deleted] Sep 21 '20

[deleted]

3

u/myropnous Sep 21 '20

YOU DONT SKIP SORTING ALGORITHMS DansGame

0

u/[deleted] 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.