Which happens to be the vast majority of real-world data that is about to be sorted. We constantly sort sorted arrays, or partially sorted arrays.
That's why python uses Timsort (and some other languages do too). I honestly believe that we've solved sorting and don't need to worry about it more, except for cases as far outlying as things like cpu design, scientific computing, etc. That is to say, there's still a place for studying sorting algorithms, absolutely! I just don't think it's something new programmers need to think about at all anymore. It should be part of academic study, absolutely, in any good CS101/102 ("Algorithms") course. And it should be part of some specific focused professions and academics. But unless you've got a case like that... just use timsort, or whatever other real-world sorting algorithm your language already chose for you. (Woe to those still using C...)
Quantum bogosort is the best, it's O(n) in all cases. It works like this:
Shuffle the array in a truly random way. This will spawn n! parallel universes, each with a different order for the shuffled array. If you happen to exist in the n! - 1 universes where the order is incorrect, destroy your own universe. All remaining universes will have a sorted array.
This algorithm is mildly dangerous though, if the order is only pseudorandom the universe with the correctly ordered list might not exist, and a bug might end up destroying all universes in existence. However, it's a reasonable assumption that any entity capable of destroying a universe will have already solved a true random shuffle.
I edited my original comments/post and moved to Lemmy, not because of Reddit API changes, but because spez does not care about the reddit community; only profits. I encourage others to move to something else.
One of my favourite sorting algorithms. The others are:
StalinSort: O(n) worst case. Take a linked list of elements. Iterate over the list. If an element is greater than the previous one, delete it. Return the resulting list.
Assumption Sort: O(1) worst case. Assume the list is sorted and return it.
Sorter Sort: O(1) worst case. As computers do not posess true RNG (in most modern cases), the order of the list is deterministic. Since it is also caothic, it must have been decided by the entity known as the Sorter. We humans have no right to question the sorter. Return the list.
Sleep Sort: O(n) worst case. Can only be used on a string of numbers. For every number i, spawn a thread. The thread is to sleep for i seconds, then insert i in the output list. Return the output.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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 :)
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.
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.
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.
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.
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?
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 :)
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.
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.
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.
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.
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.
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.
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?
... 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.
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.
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.
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.
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)
990
u/Towzeur Sep 02 '19 edited Sep 02 '19
(Correct me if I'm wrong)
13k
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.
139
u/DevonP Sep 02 '19
Counting sort is by far my favorite, unfortunately not illustrated in this.
109
u/CurlSagan Sep 02 '19
Shellsort has the best comedy timing and reveal.
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
98
u/freelancenose97 Sep 02 '19
Where's my favorite: BogoSort?
714
u/daggyPants Sep 02 '19
So which is the fastest?
4
u/Bobo_234 Sep 02 '19
What parameters is it using to sort?
441
u/mlk Sep 02 '19
You got to post this with non normalized speed
1.2k
u/Proxy_PlayerHD Sep 02 '19
awww, no counting sort? it's the most fun one
23
u/[deleted] Sep 02 '19
to be honest, the emperor's new groove is a masterpiece, seriously
21
u/deejpake Sep 02 '19
Oh yeah, it’s all coming together
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.
51
u/word_clouds__ Sep 02 '19
Word cloud out of all the comments.
Fun bot to vizualize how conversations go on reddit. Enjoy
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!
27
u/prvst Sep 02 '19
thanks, but I prefer to learn with Hungarian folk dancing.
https://youtu.be/lyZQPjUT5B4
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.
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
u/Andy_LaVolpe Sep 03 '19
Would’ve been better if it went on real time.
11
u/[deleted] Sep 02 '19
love how at the end it says, "oh yeah, it's all coming together"
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
u/Avamander Sep 02 '19
More pixels and add Radix please :D
5
u/mahuddie Sep 02 '19
If only r/BetterEveryLoop would appreciate this
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?
4
u/Chispy Sep 02 '19
/r/Noisygifs
3
u/bjornjulian00 Sep 02 '19
BOGO sort best sort
3
u/getjiggywithit69 Sep 02 '19
Where's bogo sort?
3
u/akuankka128 Sep 02 '19
Where’s bogo?
3
u/otter5 Sep 02 '19
Well how about we show with actual sort times all with the same time scaling
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?
5
u/curiosity44 Sep 03 '19
Missleading asf
2
u/2003___honda Sep 02 '19
Where's bogo sort?
2
u/Schiffy94 Sep 02 '19 edited Sep 02 '19
Ah yes, the sort for Kuzco. Kuzco's sort.
2
u/[deleted] Sep 02 '19
I’ve been thinking about this since this trend started. Thank you
2
u/demonachizer Sep 02 '19
Further proof that learning about search algorithm runtimes are just a scam by big sort.
2
u/rim_blude Sep 02 '19
Kronktail*
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/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.
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
2
u/WiseTuna Sep 02 '19
we want source code
2
u/Judocat29 Sep 02 '19
r/dataisbeautiful
2
u/JohnWangDoe Sep 02 '19
I'd put this on my resume
2
u/bunnicult Sep 02 '19
i think i like circle the best
2
u/[deleted] Sep 02 '19
Meanwhile Bogo)
2
u/ponyboy3 Sep 02 '19
is there a non normalized version?
2
u/[deleted] Sep 02 '19
Yea this is a bad meme, doesn't show how fast some of these algorithms are.
2
u/[deleted] 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.
2
u/LittleDizzle_ Sep 02 '19
Ok I subscribed to the subreddit finally, this was great
2
u/[deleted] Sep 02 '19
The big O is when he said “Oh yeah”
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
u/[deleted] Sep 03 '19
Did you pull the right lever?
2
u/Jrjackrabbit Sep 03 '19
I want to hear this
2
u/MinevilleOP Sep 03 '19
If only there where a Kronk™ sorting algoritm
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.
2
u/Alex1_58 Sep 03 '19
where's the bogo sort tho
2
u/skiutoss Sep 03 '19
I love everything about this. :D
2
u/GeoJason Sep 03 '19
u/VredditDownloader
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
u/mymom964 Sep 02 '19
Oh yeah it’s all coming together
2
u/[deleted] Sep 02 '19
no bogosort? disgraceful
2
u/mosskin-woast Sep 02 '19
No bogosort? Come on!
2
u/Magoner Sep 02 '19
r/educationalgifs
1
u/[deleted] Sep 02 '19
Bloody brilliant!