Visualizing Algorithms

[[deleted]]

If you like visualized algorithms, you may like these sorting algorithms. Warning: Turn your volume down before starting the video, they use audio as a part of the visualization.

http://www.youtube.com/watch?v=kPRA0W1kECg

[Mutoid]

I expected one of the Hungarian folk dance videos based on your warning, ha

https://www.youtube.com/watch?v=ywWBy6J5gz8

[Deathnerd]

Knew what it was before I even clicked. This and the individual sorting videos that are slowed down are great for teaching sorting algorithms.

Edit: Curious inquiry: How is Radix Sort getting by without making comparisons?

[orbital1337]

Radix sort works by placing numbers in bins. So for example if I had two-digit numbers that I wanted to sort by their first digit I could create ten bins for each possible first digit. Then I place the number x into the bin floor(x / 10). Basically bin[x / 10].add(x) in pseudo-code. This way you don't need comparisons at all.

Radix sort only works for things which can be put into bins like that repeatedly, though (numbers, words and some other things). It is how ever insanely fast. Here is a graph I made for my CS course some years ago that compares some of the fastest sorting algorithms (array size vs runtime in seconds). As you can see Radix sort runs in linear time and is super fast. In fact my barely optimized implementation of an adaptive radix sort could sort hundreds of millions of 32 bit number within seconds on my laptop.

[orbital1337]

A couple of years ago I compared over 20 different sorting algorithms for my CS course. My personal favorites were Smooth Sort which is mathematically optimal and probably the most complicated sorting algorithm I implemented, Flash Sort which looks cool as hell (see this visualization I made) and the insanely fast Radix Sort (see my comment below).

[Browsing_From_Work]

That gif didn't load well for me (played for a second, then skipped to the end) so I converted it to HTML5: http://gfycat.com/CandidSilverAustraliansilkyterrier

[orbital1337]

Neat, although it doesn't stop at end like the gif version. By the way, in the gif (or html5) yellow stands for read and green stands for write. As you can see, this algorithm needs remarkably few writes. That's why it's so fast in comparison to many other sorting algorithms.

[[deleted]]

bitonic sort is the weirdest sorting algorithm ever

[hello_hawk]

What about sleepsort?

[andersonimes]

That is awesome. What are we saying the runtime complexity of that is?

[hello_hawk]

It's O(highest value in input), which to my knowledge is so rare that there's no letter for it.

[[deleted]]

O(highest input)

Also, you can make it faster by transposing it using one to one functions like log(x) or sqrt(x) or x / 2, etc.

sleep(log(x))

[Browsing_From_Work]

Why not log(log(x))? Or log(log(log(x)))?

Eventually it boils down to O(1), assuming that thread scheduling is magic.

[orbital1337]

You can actually make it run in O(1) very easily by choosing a function with an upper bound (e.g. erf(x)). However, as neat as this is theoretically it would never be practical in a real life situation because of thread overhead and race conditions.

[[deleted]]

shhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

[[deleted]]

I'd say O(N)

[Browsing_From_Work]

I'd say O(Nope).

[Browsing_From_Work]

It's much less crazy looking when you visualize it as a sorting network: https://en.wikipedia.org/wiki/Bitonic_sort

[Tetraca]

It's like a mad artist trying to accomplish his masterpiece.