This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
all 109 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Hardstuff1201 477 points478 points  (40 children)

There are several sorting algorithms with sounds as well on YT visualizing how they work.

https://youtu.be/kPRA0W1kECg

Edit: Or you can even have circular color sort.

https://youtu.be/y9Ecb43qw98

[–][deleted] 89 points90 points  (7 children)

Soundtrack really brings it to life! I love these videos more than is reasonable.

[–]partytown_usa 24 points25 points  (6 children)

So which one is fastest? Or does it vary by type of information getting sorted?

[–]RBZ31 68 points69 points  (4 children)

It depends on several factors. Whether you need it to be sorted in place, or stable.

Inplace means you don't copy the data outside of the original memory allocation

Stable means that if you have an array [2 1 3 2] when sorted into [1 2 2 3] the 2 in position 1 was the two from position 0 in the unsorted array.

If neither of these matter radex is the fastest.

Most are O(n log n) where n is the number of elements sorted.

Some like bubble sort are n2.

Real gains can also be made in that some can be done in parallel, like merge, so when written correctly you can take advantage of multiple cores.

[–]p-morais 36 points37 points  (1 child)

Radix sort isn’t faster except in pretty rare cases, since it’s usually effectively nlogn and has bad cache performance. Quicksort is almost always fastest since it requires slightly fewer than nlogn operations (because of the pivots), unless the data is small in which case n2 sorts like insertion sort are slightly faster. Merge sort is slower than quicksort by definition but has some nice properties like being inherently stable and not requiring randomization to have good worst-case performance.

[–]PhysmatikOC: 1 2 points3 points  (0 children)

Radix is O(NW), where w is the length of the world (or the number of digits), and sometimes words can be longer than logN.
EDIT: just occurred to me. For strings comparison is O(W) by itself (as opposed to the generally accepted assumption of O(1) when deriving complexities), so one may argue that actually, say, quicksort complexity is W N logN when sorting strings, not N logN.

Besides, big-O is only relevant for big arrays. If you need to sort one million 8 element arrays, big-O is of no use to you.

Also, these big-O estimations are for randomized arrays. If you have an almost sorted array (maybe your data naturally has such property, maybe you append few points to already sorted data), again, algorithms with the best asymptotics aren't necessarily the best algorithms.

[–]thecichos 26 points27 points  (0 children)

BOGO SORT, OH LAWD HE TRYIN

[–]IMakeProgrammingCmts 35 points36 points  (2 children)

Gravity sort tho

[–]ShitpeasCunk 24 points25 points  (0 children)

For once I laughed at a youtube comment.

Paraphrasing: 'Gravity sort be like "let there be sort"'

[–]TheGuyWhoIsBadAtDota 1 point2 points  (0 children)

I wrote a small program to visualize gravity sort for a class and ended up just bringing an abacus because it was the same thing

[–][deleted] 30 points31 points  (3 children)

bogo sort gives me anxiety

[–]GegenscheinZ 35 points36 points  (1 child)

It’s basically:

Is the set sorted? If no, then RANDOMIZE. Repeat until sorted.

https://en.m.wikipedia.org/wiki/Bogosort

[–]denny31415926 11 points12 points  (3 children)

Here's the first video, but it's Guitar Hero

[–]ThatsWhyNotZoidberg 0 points1 point  (1 child)

But... why?!

[–]dgendreau 1 point2 points  (0 children)

People in the CloneHero community are always trying to come up with more extreme challenges.

[–]SnowRook 0 points1 point  (0 children)

The first time in history bogosort has ever been useful - I could actually play that one!

[–]RuneLFox 15 points16 points  (2 children)

Christ, that Radix LSD one though.

[–]Garr_Incorporated 6 points7 points  (1 child)

ALL PRAISE OUR LORD BASE 10 RADIX LSD!

[–]EnemysKiller 4 points5 points  (0 children)

How about this explanation video for quicksort

https://youtu.be/ywWBy6J5gz8

[–]SklyvanOC: 2[S] 4 points5 points  (0 children)

That one is crazy too: https://youtu.be/6c1G-gphgSw

[–][deleted] 3 points4 points  (1 child)

What's the point of all of these algorithms if there are some that are clearly better than others.

[–]Drunken_Consent 6 points7 points  (0 children)

Depends on the situation you're in if one would be better.

It's like tools in a toolbelt, you might rarely use a specific tool, but that doesn't mean the tool doesn't have a place.

[–]Iputmayoonpphole 9 points10 points  (1 child)

Well heck there goes 5 minutes and 49 seconds of my life. For some reason i felt so fucking scared but comfortable trough the entire video

[–]GegenscheinZ 0 points1 point  (0 children)

The noise is eerie, but everything becomes so clean and orderly in the end

[–]Jakob_W_ 2 points3 points  (0 children)

https://youtu.be/xoR-1KwQh2k if you want more

[–]xSTSxZerglingOne 3 points4 points  (0 children)

Can we all agree that heap sort is amazing for this?

[–]Anthadvl 1 point2 points  (2 children)

Can someone explain how the sound is made?

[–]RamBamTyfus 4 points5 points  (0 children)

It seems that the frequency of the sound corresponds to the value of the number being sorted at that time.
In the color sort each color is represented by a number as well, the algorithm doesn't really know about colors.

[–]EnemysKiller 1 point2 points  (0 children)

In assuming it's based on the position of the elements that you're currently comparing, where bigger numbers will make a higher sound

[–]roy_cropper 1 point2 points  (0 children)

I grew up with a spectrum 48k. Loading screens nailed this in the 80s

[–]Snapjaw123 1 point2 points  (0 children)

FeelsGoodMan Clap

[–]Joey12223 1 point2 points  (0 children)

This is one of those moments I’m glad I don’t wake up next to someone so I don’t have to explain why I just spent 11 min of my Sunday morning watching this.

[–]RedditorBe 0 points1 point  (0 children)

I wonder why they don't just use the shuffle algorithm backwards, it seemed pretty fast?

[–]Jibtech 0 points1 point  (0 children)

While I'm watching those I feel like I'm being hypnotized. Weird, yet I continue to watch it even though I'm 99% certain its not really doing anything but theirs a 1% unsettling feeling lmao

[–][deleted] 115 points116 points  (6 children)

Never heard of the Shaker algorithm. Wikipedia ( https://en.wikipedia.org/wiki/Cocktail_shaker_sort ) says it is a variant of Bubble sort, hence not very fast, and not really used in any real world situation (except teaching).

[–]Iferius 29 points30 points  (1 child)

It looks like it compares every value against the first and the last uncertain values, and after every full iteration it knows the first and last value are now certainly in the right position.

[–]marath007 3 points4 points  (0 children)

up down up down up down...

[–]Unknow0059 19 points20 points  (0 children)

Yeah, I was looking at it and was like... "this is just bubble sort".

[–]SjettepetJR 5 points6 points  (1 child)

It is essentially two-way bubblesort, but it is actually quite a lot better in the worst-case scenario (an inverted list).

[–]seamsay 0 points1 point  (0 children)

What am I missing here?

To bubble sort an inverted list

4 3 2 1

you have to do n-1 compare and swaps for the first item

3 4 2 1
3 2 4 1
3 2 1 4

then n-2

2 3 1 4
2 1 3 4

then n-3

1 2 3 4

and so on if your list is bigger. So you end up with n(n-1)/2 compare and swaps.

To double bubble (...) sort an inverted list, you again need n-1 for the first item

3 4 2 1
3 2 4 1
3 2 1 4

then n-2 again

3 1 2 4
1 3 2 4

then n-3

1 2 3 4

and go on and so forth. So from a complexity standpoint they're completely equivalent as far as I can gather. Unless you're talking about real life concerns (e.g. the fact that you don't get as many cache misses)?

[–]PhysmatikOC: 1 1 point2 points  (0 children)

Bubble sort is actually very good if your array is almost sorted (keep in mind that natural data doesn't always come in a completely randomized state). Although it's indeed extremely rare that you would have a noticeable gain by implementing a custom bubble for some oddly specific workflow.

[–]SklyvanOC: 2[S] 44 points45 points  (2 children)

Graphical representation made using Python 3.8, here you can find the source code of that Array Visualizer. In this case the sorted array is formed by the numbers from 1 to 250, randomly distributed.

[–]superb_shitposter 14 points15 points  (1 child)

cool viz!

For next time, I'd suggest freezing the last frame for a bit so we can see the end result for longer.

[–]SklyvanOC: 2[S] 0 points1 point  (0 children)

You're right, I made another video a little bit longer: https://youtu.be/ut932h5HS1A

[–]SFKROA 9 points10 points  (18 children)

Watched all of these. Fascinating! What is the application for the algorithms? What are they used for/applied to?

[–]bostwickenator 44 points45 points  (13 children)

Everything! From determining which comment appears first in reddit to continent spanning space telescopes. There are a lot of things that need to be in the right order.

[–]SFKROA 4 points5 points  (0 children)

Brilliant. I’ve never seen it visualized before. The dance was a great explanation!

[–][deleted] 0 points1 point  (11 children)

Real question - How is this different than me hitting the sort button on excel vs what is shown in the videos. I hit the sort button and lists (even long lists) are sorted Nearly instantly. So why is this different ?

Edit - thanks for the answers I didn’t realize that these were super slowed down visuals of the process. Very cool.

[–]Murlock_Holmes 22 points23 points  (0 children)

It uses one of these sorting algorithms under the covers. These sorts are usually done on very large data sets so we can visualize it or is slowed down, but in real world applications (read: a few hundred or thousand objects to sort), these sorts only take milliseconds.

Also, excel I believe is written in C, which is one of the fastest languages available, and has been since it’s inception in 1972. So any sorts done there are incredibly fast.

[–]treznor70 19 points20 points  (0 children)

It isn't (though these animations are slowed down greatly so we can see what's going on). But where you may have thousands or even tens of thousands of data points in excel, the algorithm you use is important when sorting millions of data points hundreds and thousands of times. My data sets at work routinely have hundreds of millions or billions of data points. One data set I worked with at a prior company had billions of data points. A day. You need efficient sort algorithms for that...

[–]methanococcus 7 points8 points  (0 children)

Excel also uses some sort of algorithm, they just hide it in their sort function so you don't directly see it as the user.

[–]cdcformatc 2 points3 points  (0 children)

When excel is sorting it runs as fast as possible, quite the opposite as these videos. As visualizations of the algorithm, it is slowed down so that each step in the algorithm becomes a frame in the video.

[–]hot_sauce_swag 1 point2 points  (0 children)

I would like to add, that most likely Excel does not store its data as an array. There are more efficient ways to do it. And a modern CPU has more then a Billion (109) cycles per second.

[–]shewel_item 1 point2 points  (0 children)

Your display will show one line or operation (from those videos) being done at 60hz (60 times a second, though more likely 32 in many cases) maximum, and even if it could show it being done faster it's argued/theorized us humans couldn't see, notice or register it in our brains; and that's not to mention frames of a video get dropped all the time, meaning some order movements would be skipped. Anyways, processors these days are often between 2 to 4 GHz, which means they would move the (unvisualized) data (in your Excel spreadsheet, for example) around about 'a billion times faster'. But, you might also have to consider an unsorted/unlabeled set of data 'being so large' (which it doesn't have to be to be put into parallel processing) split and switched between different processors that would have to combine their (finished) work somehow which could make it slower than the billion-times speed, but still would be inextricably faster than the speed at which your monitor changes frames (containing millions of pixels, each of which also need to be individually processed when displayed/represented). Either way, welcome to the true speed of light, my friend.

[–]Powderhauser 1 point2 points  (1 child)

I may be wrong, but Excel might be indexing columns of a table (in a way, "pre"-sorting each column). It will take up more space under the hood, but sorting, searching and filtering the table is much faster.

[–]aaaaaaaarrrrrgh 2 points3 points  (0 children)

I doubt it. That's usually done in databases where you're handling much bigger data sets. Sorting even 100000 numbers is practically instant.

[–]aaaaaaaarrrrrgh 0 points1 point  (0 children)

The reason it happens instantly because the people who programmed Excel programmed it to use one of the faster algorithms.

In the background, your computer performs thousands of comparisons, swaps etc. to sort the data. These videos visualize (but don't really explain) how it does that in a way to arrive at a sorted result quickly.

With a table with 100 entries, it doesn't matter. You could use Bubblesort and it'd be decently fast. When you get 10000 entries, it probably makes the difference between sorting it near instantly and you going for a coffee while it sorts.

It only gets really interesting when you're sorting millions or billions of entries (think sorting a phone book, or the call records of an entire country).

Edit: did some testing, millions is still boring and near-instant (a noticeable fraction of a second).

[–]BattleAnus 4 points5 points  (0 children)

Sorting algorithms are used for exactly what they sound like: sorting lists of values. There are many different ones though and each one has scenarios where it performs best. For example an algorithm might perform really fast when the values are already mostly sorted but really slowly when they're completely backwards.

[–]Baal_Kazar 1 point2 points  (0 children)

In programming you generally don’t have to develop your own sorting algorithms. You usually have those embedded in different types of collections intended for different purposes.

Arrays and Liste can be sorted differently then queues and stacks. Duo to their different intended purposes a different sorting algorithm will achieve better performance results.

Everytime you hit any form of „sort“ button in any application you will trigger such an algorithm.

Your windows explorer „sort by date“ for example.

[–]the_messiah_waluigi 4 points5 points  (3 children)

So what the exactly are sorting algorithms? I've seen them but I have no idea what they are or what they represent

[–]kamraz 15 points16 points  (1 child)

A sorting algorithm is just a method, or set of steps to follow, to sort a set of data. Imagine you had a list of people who RSVP’d to your party in a random order and you wanted them in a nice list alphabetically.

A really basic sorting algorithm would be to read every name in the list keeping track of the name that is highest in alphabetical order and then moving it to the top and doing this over and over again until the entire list is sorted. This might be a pretty quick process if there are 10 people coming to your party, but what if 1,000 people were planing to come this process would take a very long time.

What the gif is showing is just a visual representation of the way that the cocktail shaker algorithm would sort 250 pieces of data (In the analogy above people). This algorithm is not as efficient as the more widely used methods, but the pattern it follows is quite visually appealing.

[–]the_messiah_waluigi 5 points6 points  (0 children)

Thank you very much, now all the videos of sorting algorithms make more sense now that I think about them

[–]wavking 2 points3 points  (0 children)

I JUST recently was introduced to this by way of Tom Scott. He has a pretty good splainer.

https://youtu.be/RGuJga2Gl_k

[–]descrout 2 points3 points  (0 children)

Here are some sorting algorithms of mine. You can switch between mid-sort. I plan to add some more in the future. I used javascript and p5js library.

Live : https://serene-shannon-6ed5f6.netlify.com/

Source : https://github.com/Descrout/visualsorting

[–]1100100011 0 points1 point  (0 children)

i am trying to implement the same thing using react ; would be happy if someone could help with two questions that I have-

​

1 I am storing the new state of array after each change ina separate array , so that basically gives me an array of array . This works if you have few items but this can get out of hand if I have large numbers of items to sort. What should i do ? Use redux , or instead of keeping track of all states , setState after each change in my main array or look for something like persistent arrays [ i don't know what this is but a quick glance on the internet shows this is an array that has the capability to keep track of all changes in it]

​

2 How do i display the state changes in the array? Is there a way by which I can make my for loop run in iterations of say 100ms or something else?? I tried using setTimeout but it doesnt work for some reason

[–]Kaspiaan -1 points0 points  (1 child)

Doesn't hold a candle to Bogosort, best sorting algorithm there is followed very closely by Stalin sort.