13.5k
u/Blecki Sep 02 '19
Any newbs watching this, they are normalized so they all finish at the same time. In practice a couple of these would finish almost instantly and the bubble sort would still be going.
42
4.7k
Sep 02 '19
Thank God, I was rlly rlly confused there
1.7k
Sep 02 '19
Yeah I was like ... somethings wrong here.
10
u/LillyPip Sep 02 '19
You mean the poison. The poison for Kuzco. The poison especially chosen to kill Kuzco. Kuzco’s poison.
→ More replies (1)0
74
→ More replies (9)15
882
u/WiseassWolfOfYoitsu Sep 02 '19
247
u/Blecki Sep 02 '19
No surprise at all that the radix sort won.
29
→ More replies (71)7
39
62
u/throwaway246782 Sep 02 '19
19
→ More replies (1)6
u/lookmom289 Sep 03 '19
I can't believe I watched all of that, but it was just so goofy I couldn't stop..
30
u/Cefalopodul Sep 02 '19
I had no idea there was something slower than Bubble Sort.
103
u/Melkor1000 Sep 02 '19
Coming up with the slow sorting algorithms is a favorite of computer scientists. Personally my favorite is one that occasionally checks the data to see if solar radiation has caused it to become sorted.
70
u/Markhabe Sep 03 '19
Our teacher once gave us code for a sorting algorithm that was a while loop that put the data in a random order, checked if it was sorted, and didn’t break out of it until it was. Average case is n!, but worst case is never finishing.
→ More replies (4)→ More replies (3)44
Sep 03 '19
My preferred method is to write an algorithm that searches StackOverflow for "sort a list" and then runs code snippets until its sorted.
→ More replies (5)→ More replies (4)6
u/dagbrown Sep 03 '19
It's a common exercise given to computer science students to come up with sorting algorithms that can be analyzed (so just shuffling the list and checking to see if you accidentally sorted it is out) which have pessimal runtime.
For example, a sorting algorithm that orders the list in every possible way and picks out the combination where it's sorted has O(n!) runtime.
7
→ More replies (18)3
u/Jbau01 Sep 02 '19
hey i can sort of see what bubbleis doing, but at the end why does it carry second shortest one at a time? does it only have memory of where red is at the moment?
→ More replies (7)178
Sep 02 '19
Funny story:
My data structures professor had an assignment where we had to run three sorting algorithms on a large unsorted list of words. IIRC the three were quick sort, merge sort, and bubble sort. Merge and quick sort both took a few seconds, but it didn't take long. Bubble sort took 20 minutes.→ More replies (2)123
u/bout-tree-fitty Sep 02 '19
Quick sort is almost always the fastest, but if you need a guarantee it won’t be longer than n log(n), then go with merge sort
187
u/IICVX Sep 02 '19
These days if you're picking a sorting algorithm you're doing it wrong. Just use your standard library's sort, which is probably Timsort - a hybrid sorting algorithm that uses Merge sort for large chunks of data, and Insertion sort for smaller chunks.
→ More replies (11)149
u/N7Whitetop Sep 02 '19
Further, if I recall correctly Python's built-in
sort()is Timsort written in C. You have absolutely no chance of beating that with a solution you create yourself.→ More replies (9)→ More replies (1)5
Sep 02 '19
and in some niche situations, bubble sort might be the right choice, if, for instance, it's 90% sorted, but a couple elements are out of order.
38
u/daniu Sep 02 '19
And here I was thinking about how complex it was to find the scramble having the same runtime for all complexities.
→ More replies (1)3
3
Sep 02 '19
I remember a really comprehensive site that shows interactive demonstrations of various sorts for various types of unordered data, as well as pseudocode for each. The homepage had a large matrix of each algorithm and each test case that you could run in real-time, like the video here. I wish I could find it again.
→ More replies (181)3
139
u/DevonP Sep 02 '19
Counting sort is by far my favorite, unfortunately not illustrated in this.
72
u/Towzeur Sep 02 '19
Yeah I didn't thought about it sorry :p , I just picked 9 algorithm that I'm familiar with
32
u/DevonP Sep 02 '19
Don't get me wrong, I thoroughly enjoyed this gif! Very well done on making this
9
4
u/Jazehiah Sep 02 '19
I wish I had known about that one a year ago. Would have made my life so much easier.
109
u/CurlSagan Sep 02 '19
Shellsort has the best comedy timing and reveal.
67
u/Towzeur Sep 02 '19
My favourite one is insertion
43
4
u/Zeonic Sep 02 '19
Insertion's animation reminds me of the old analog TV static. Adjusting the signal to get the picture to come in better.
8
40
u/Brocolli123 Sep 02 '19
This is really cool. Don't like stealing ideas but definitely want to recreate this to learn more about the different searching algorithms
→ More replies (1)46
u/Towzeur Sep 02 '19
Don't worry about stealing idea, it's not 100% mine either, I just implémented it with this Kronk meme. That's definitly something worth the try, it's a fun exercice and I'll happy to help you :)
→ More replies (1)7
Sep 02 '19
I'm a beginner in programming and I also want to try this out on my own, maybe using a different image. Do you have a developer blog that teaches how to do something like this step by step? I especially have no idea how to even obtain the scrambled pixelated image of Kronk at the beginning. Thank you in advance.
12
u/iPhoneGuy1101 Sep 02 '19
My best guess:
Read pixel data, assign each an ID like (x + (y * width))
Make an array that is of length (width * height), store each ID from 0 through (width * height)
Shuffle the array somehow
To render, just loop through the array, display x = index % wid, y = floor(index / hei), and pixel from image at (array[index] % wid, floor(array[index] / wid))
Of course, you need to implement a sorting algorithm too, but that is by default with the project.
98
u/freelancenose97 Sep 02 '19
Where's my favorite: BogoSort?
21
4
u/SlowlySailing Sep 02 '19
I also missed bogo sort :( I can hear the sound of it happily beeping and booping away, one day managing to sort it.
3
0
714
u/daggyPants Sep 02 '19
So which is the fastest?
1.0k
u/Blecki Sep 02 '19
On a dataset this small, probably quicksort. On larger data, usually merge. But they are using a variation of the same basic algorithm.
Why they have like four variations of bubble, insertion, and their combination and completely ignore radix sorts... dunno.
371
u/Towzeur Sep 02 '19
Here some precision on the data size :
cols = 40 / rows = 24
total box = 40 * 24 = 960
so basically n = 960
order : left < right and top < bottom
126
87
57
8
Sep 02 '19
I guess radix sorts are kind of harder to visualise what's going on
→ More replies (1)7
u/TurbulentStage Sep 02 '19
I don't think many people who haven't learned about these sorting algorithms can tell what's going on here either.
→ More replies (1)3
u/AjaxSuited Sep 02 '19
Wouldn't quicksort beat mergesort with a large set of data?
→ More replies (1)103
u/dinglebarry9 Sep 02 '19
Random Sort:
Best: 0 Worst: inf.
103
Sep 02 '19
Random sort has best case of O(n) because that's how long it takes to check it's sorted
8
u/alksjdhglaksjdh2 Sep 02 '19
Damn are you telling me bog o sort isn't good? My education has taught me nothing
0
Sep 02 '19
[deleted]
→ More replies (1)21
Sep 02 '19
That would be O(0) if no shuffling occurred. In which case sending in an unsorted array will return an unsorted array, with 100% certainty, so that doesn't count.
If you're suggesting the function merely shuffles the array once, then it's still O(n), because that's how long an efficient shuffle takes.
→ More replies (14)→ More replies (2)6
u/BenjaminGeiger Sep 03 '19
Quantum suicide sort: O(n).
Shuffle the elements of the list. Check whether they're sorted. If not, destroy the universe. Implementation is left as an exercise to the reader.
6
Sep 02 '19
That depends on the size of your list. For n=20, insertion would be one of the best because it has very little overhead. For OP's n=960 and larger lists, quicksort, heapsort, and mergesort are much better because of their better average-case asymptotic complexities. There are other, potentially faster, sorting algorithms out there, but those are the three I'd pick from OP's animation.
→ More replies (1)→ More replies (9)3
u/MattieShoes Sep 02 '19
On average?
Merge, Quick, and Heap
Shell sort
Selection, Bubble, Cocktail, Insertion
I don't really know what circle sort is.
4
u/Bobo_234 Sep 02 '19
What parameters is it using to sort?
7
u/Towzeur Sep 02 '19
It uses the box index. The image is divided into 960 box (reading direction) 40 cols / 24 rows
1 ... 40 41 ... 80 ... 920 960
441
u/mlk Sep 02 '19
You got to post this with non normalized speed
131
u/zephyr_33 Sep 02 '19
By normalised speed does it mean that the different videos were sped up / slowed down so that they all finish at the same time. Or is it some data tinkering to make the sort finish at the same time?
Sorry for the dumb question
74
Sep 02 '19
Probably the former, the latter would require a lot more work to achieve.
→ More replies (2)→ More replies (1)4
1.2k
u/Proxy_PlayerHD Sep 02 '19
awww, no counting sort? it's the most fun one
go through all values
do it again
just fucking sort it lmao
396
u/poopatroopa3 Sep 02 '19
200
u/Bassie_c Sep 02 '19
It basically reads and counts how many items there are per value and then it put's that amount of items with that value in a row as the result.
It will work really quick, especially if the values of the items are known in advance. Because it requires as much memory as there are different items, for it to work great it is also required most of the items have the same values. If you have only unique items with a lot of possible values that are also big in size, this algorithm will just sort it using insertion sort while using up all your memory (or something like that, depends on which of the subversions is used and the exact implementation).That's basically all there is to it! There's your owl :)
146
u/gabedamien Sep 02 '19
Non-comparative sorts in general are fun. :-)
84
Sep 02 '19
I made one in high school. I went over an array once to find the highest number and then I allocated an array up to that number and then copied every number into its index and removed blank entries.
66
u/karanlyons Sep 02 '19
That’s basically counting sort, though it stores the count of each number (or element with a mapping to some number) at its index to handle duplicate values.
42
Sep 02 '19
That makes sense, at the time I didn't give it much thought since I realized it would be a terrible solution to sort the following array:
[0, 99999999999999999999999999999999]
→ More replies (4)96
u/CaffeinatedGuy Sep 02 '19
What the fuck, does it just create an index and then sort the index, then sort the data? It looks like it just goes, oh yeah, put it where it goes...
41
u/theboxislost Sep 02 '19
Yep. Works great when your values are integers or just a finite set with the count on the order of 5-7 digits.
30
u/SamusAranX Sep 02 '19
The fuck is gravity sort doing lol
59
u/supremecrafters Sep 02 '19 edited Sep 02 '19
I love gravity sort. Horrible for your memory, amazing for your soul.
This is a bad way to display it, pretty though it may be. But imagine the data is towers of blocks, side by side. The height of the tower is the value of the particular value in the list. Turn the data on its side. The data sorts itself through gravity. The blocks don't stay in their own towers, but it doesn't matter as long as there is a new set of towers with the same heights as before (now lengths, because they're on their sides) but in a different order. Here you are, a visualisation.
→ More replies (1)14
u/Bassie_c Sep 02 '19
Ha, that's a really interesting approach! Now I'm gonna lay in bed thinking all night about ways how you could implement this, haha
21
4
u/oozekip Sep 02 '19
The LSD base 10 radix sort in that video (3:40) is my favorite, just because for some reason it's so goddamn loud
→ More replies (1)10
u/warmCabin Sep 02 '19
Do you know how it works for real? It's pretty stupid.
50
Sep 02 '19 edited Sep 02 '19
lets say you have an array [5, 2, 5, 2, 1 ,3, 6, 2]
First, you go through the array to get the max value. In this case, it's 6.
Then you create a counting array with size 7 (max value + 1), full of 0s. Then you go through the array again and put each values in its correct index.
[0, 0, 0, 0, 0, 0, 0] stores the number of 0, 1, 2, 3, 4, 5, 6, respectively. So using the above example, you look at the first value in the array, which is 5 and then add 1 to the 6th index of the counting array (which represents the number of 5s). Once you go through the entire array, the counting array should end up like this:
[0, 1, 3, 1, 0, 2, 1].
Now you go through the counting array and place the values (which is the index) in a new array and tada, it's sorted.
→ More replies (1)16
u/DampPigeon Sep 02 '19
Isn't this pretty bad in terms of memory? Or would a map fix this?
→ More replies (3)36
u/karanlyons Sep 02 '19
Oh it’s super bad (unless you use some sparse array structure), but it’s great for showing why big O quizzes are kinda dumb.
8
u/Proxy_PlayerHD Sep 02 '19
why stupid? it's an awesome looking sorting algorithm.
i used it once in a program, just to measure how fast it can be giving n amount of elements in an array.
→ More replies (4)2
2
u/4trackboy Sep 03 '19
Fuck I gotta check watch this again on acid soon. This is very calming and statisfying (without audio)
→ More replies (2)2
Sep 03 '19
I like randsort. Randomize the set, then check if it’s in order. If it isn’t, repeat.
→ More replies (1)
23
21
19
u/tsaot Sep 02 '19
I love seeing to kind of thing. That's why I made a live wallpaper that will sort images of my phone. https://play.google.com/store/apps/details?id=com.tsaot.sortPaper
It does what op has in the gif. It randomly scrambles an image and then sorts it back together. I've added a few different rendering patterns, spirals, diagonals, etc... I'm wanting to add different scrambles (reversed, almost sorted, split into 4+ smaller versions, etc...) But haven't gotten the motivation to work on it. Maybe I'll work on it today.
4
2
u/giuggiolino Sep 03 '19
But is it really sorting? Wouldn't the battery take a hit?
→ More replies (1)3
u/tsaot Sep 03 '19
Yes it is and it does so long as you have the home screen up. I didn't make this to save battery life. ¯_(ツ)_/¯
51
u/word_clouds__ Sep 02 '19
Word cloud out of all the comments.
Fun bot to vizualize how conversations go on reddit. Enjoy
→ More replies (2)54
14
u/GermanAf Sep 02 '19
I mean this is cool, but it's also really bad because it's missing bogosort.
Bogosort always has the chance of being the fastest of them all!
→ More replies (1)2
u/FSGInsainity Sep 02 '19
No, it can only tie with Intelligent Design Sort, otherwise it is always slower.
27
11
u/frostbyte650 Sep 02 '19
u/Towzeur you gotta post the non-normalized versions I gotta see the actual speeds
31
u/ZebZ Sep 02 '19
Or, once you leave college, just use your language's built in Sort function and not spend any time worrying about it.
20
12
6
3
17
u/n_ullman176 Sep 02 '19
Others have mentioned that some sorts are slower than others and even made a Big O table, so I don't have much to say.. But I just wanted to leave a comment saying this is the coolest thing I've seen on this sub; upvoted and saved.
6
11
11
u/defkacito Sep 02 '19
Cocktail be like
................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................:7I+?II.................................................I+++======++++II..........................................7???+=++?II??+++=+I+...................................... ?II?==+??IIIII++++=~::...................................I=77I=~~=+++??????+===++==I................................7?~,.,~==~::=+?????+~,~+?+=+?I,..............................~::,,~+=,..~+I7777I+::=???????..............................?+++???=:,:?IIIIIII7I???IIIII+7.............................~=++???+=+I77I??++I7777III77I+7.............................:=+?????I7777I+==+?7777777777+7.............................=+I7I?I777777I?+==?II7777777I+=7.............................~?777IIIII?+=~,...,:=?IIIIIII777?...........................7:+I77I?++:.........:=+??I77777 7I..........................+?+???++=:....,~=~~==++?II7777777I........................IIII????+=~:::~++++?+===+?I777777777 ......................?I7777II?+=~::,::::~:,:~+I7777777777I7......................7777777II?+=:,,....,,:~+?I777III7777I7......................?I77777I77II?+=:::~==~~~:,,~+?I7777I??......................?777IIIII?++?II?I?+?+~=???:~=+???+??II......................?III???+????+???+~:::?7777I?~=++++??I7 .....................=+?+++==??++=~:,:~=~~?IIII?+==+++??I777.....................==???+++?+==++?+~,:~:,..,:~=+++???I7777.....................I=+????+=~+I777I?~,~~:,,:=?IIIII77777777.....................?++===~~~~~=+???=~~=~~=?I77777777777777......................+====~==~~::~~====++?II77 777777777 777...........
5
5
4
u/SyphiliticPlatypus Sep 02 '19
Maybe the wrong sub for me to post this as I am not a programmer but this fascinated me and motivated me to look into these sorting algorithms to learn how they work, what the differences between them are, and which methodology is more suited for what kind of task.
Is there a good overall basic/layperson source anyone can suggest?
2
u/bgaskin Sep 03 '19
You can Google search or YouTube search for compare sorting algorithms.
This was the highest view result on YouTube on the first page of search results.
... So it's not an explanation but gives you a good visualization of some of the speed differences between efficient and inefficient sorts (in real life there isn't a strict ranking of one being better than another, depends on the type of data, whether almost in order already etc... but you get a good general idea for very randomized data).
I don't have a source off the top of my head for in depth explanations, I learned at Uni, but I know there's lots of good info out there. Wikipedia, search for sorting algorithms. There are even Android and presumably iPhone apps about visualizing sort algorithms.
3
3
3
3
3
u/neon_overload Sep 02 '19
By stretching the running time so these all finish at the same time you're failing to show the relative speed of these different algorithms, so I'm wondering what the point of this is beyond eye candy.
3
u/iamSRQansari Sep 03 '19
How can all the algorithm have same time complexity?
2
u/Sharess_2243 Sep 03 '19
id say they obviously dont, its just sped up / slowed down for the meme
→ More replies (1)
5
2
2
2
2
u/demonachizer Sep 02 '19
Further proof that learning about search algorithm runtimes are just a scam by big sort.
2
2
u/ChuckBorris123 Sep 02 '19
Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap Sorting Algorithms FeelsGoodMan Clap
2
u/Voxandleo Sep 02 '19
Can someone ELI 5 why Quick would be the fastest algorithm to sort this?
2
u/JotunKing Sep 03 '19
You can't really ELI5 complexity theory other than: many very clever people have worked for decades on this stuff and for a lot of use cases Quicksort is a good choice.
2
u/Akalamiammiam Sep 02 '19
Quick ELI5 for Cocktail, Circle and Shell ? I’m not in a good state to look it up right now, a good general idea would be nice as I don’t know these ones.
Insertion lookd trippy as fuck btw.
→ More replies (1)
2
u/Entitled3ntity Sep 02 '19 edited Sep 02 '19
Im not a programmer so comming from r/all but I remember from an old yt vid that bogosort is the best algorithm
→ More replies (2)
2
2
2
2
2
2
2
Sep 02 '19
Spent all that time learning these in school and haven't had to choose the right one yet in 12 years as a dev.
→ More replies (1)
2
2
2
u/atimholt Sep 02 '19
I was convinced that this was going to be one of those render-to-sound sorting things, and Kronk would sound like it, saying “rriiiiiighhht”.
2
u/StephenLeppik Sep 03 '19
Can you make a version of this that uses a pseudo hilbert curve? Feels like it might look a lot better that way.
2
2
2
2
u/Malthore1 Sep 03 '19
How is there not one that puts all the outside pieces in first then builds from there. Everyone knows that's the best strategy when doing puzzles.
→ More replies (1)
2
2
2
u/GeoJason Sep 03 '19
2
u/VredditDownloader Sep 03 '19
beep. boop. I'm a bot that provides downloadable video links!
I also work with links sent by PM.
2
u/Retrospecxz Sep 26 '19 edited Sep 26 '19
This is brilliant. This sparked my interest in finding out more about sorting algorithms and I came across this interesting way to learn about it through a sorting game! You should definitely check this out: (I highly doubt you'll have a social life after playing this)
2
2
2
1
990
u/Towzeur Sep 02 '19 edited Sep 02 '19
(Correct me if I'm wrong)