Thanks everyone again! I wish I could upload more frequently. There are already some new ideas brewing. I hope I'll get to working on it soon. But yes, it will take some time again :)
Hi udiprod... Let me just say, I like your explanations and how simple you make things to understand. I'm curious as to why you're not moving towards expanding your production and making your videos more frequent. _Patreon_ could help a lot and I for one would really look forward to more stuff from you.
Love the content, wish it could happen more often! But time and life and whatnot. Though... I want an explanation on how Radix Sort works... because it doesn't do comparisons (right?).
HOLY SHIT did you just clearly explain the concept of N operations and how they grow as the input grows using graphing based on a clear visual metaphor?!?
The analysis at the end... You just made one of the best videos on sorting on TH-cam. Please make more analyses when you have the time. We'll be patient ❤️
honestly insertion sort, by the looks of is, is just a backwards bubble sort. I still have no clue, since I don't know EXACTLY how bubble sorts work yet. can someone please link the video?
bogosort has eyes to check if he succeeded but it just basically throws the marbles to the ground than vaguely decides their order and than checks if it succeeded
@@no-one-1 hey, bogosort has a very karge brain. By that I mean it uses more to do the same thing because randomly sorting something is actually kinda resources intensive
I love math and sorting and the intellectual part of this...but I also just love watching the little robots pick up those balls and bring them up to analyze them two at a time...all the little competitions are so cute, while at the same time being incredibly educational.
Sorry to butt in. But: You know why nlog(n) is better than n^2, but you don't know why nlog(n) is the most efficient. I could claim that there is an algorithm that can do it in n time, and you would not be able to prove me wrong. __ In the model that is used in the video (compare comparisions done of whole objects), nlog(n) indeed is the shortest possible time (you can prove that by considering all the possible permutations, and mapping them on a decision tree). However, if you consider a different model, the RAM model, you are able to sort integers in near linear time (in just n). This sorting algorithm is called Radix sort. __ Please don't take offense to this, I just want to avoid you from possibly misunderstanding what you think you know.
@@TheShinySnivy Radix sort is non-comparative but achieves linear runtime complexity. It can do so because it has access to the digits of the values being sorted (rather than only a less-than, greater-than, or equal-to). It's essentially a count sort, but performed multiple times to count sort by each digit (base-10) or other radix (like base-256).
O(n log(n)) is the best you can do given comparison sorts, where the sorting algorithm only has information on greater, less than, or equal to. Given most data has some sort of absolute order (not only larger than, but by exactly how much), you can achieve O(n) by using a counting sort. Say you're sorting an array of thousands of elements, but they're all numbers from 0 to 9. The easiest way to sort them is actually to just count how many 0's, 1's, and so on until you've gotten to 9, then put out as many 0's as is counted, then 1's, and so on. Radix sort is just a way to make counting sorts space-efficient: Instead of scaling linearly with the number of possible values (256 for an 8 bit int or char, 65536 for a 16 bit int, and over 4 billion for a 32 bit int), it scales logarithmic-ally which is much better. Even better, radixes require almost no cross-communication (after all, no comparisons) with a very simple way to combine the results of multiple radix sorts (just add all the counts together), making them very easy to scale across potentially thousands of computers (perfect if you were trying to sort trillions of items across an enormous Cassandra or HBase cluster). Basically, if you were doing a 32-bit integer, instead of keeping over 4 billion counts, you keep 4 sets of 256 counts, one for each 8 bits. It's cumbersome to explain, but the core of it is a piecewiise counting sort using prefix sums to make it work.
Can you make a vid about Gravity sort? I kinda wanna see a robot doing magic tricks :) Also please make a video about Langtons Ant? :D Also Counting Sort plz😀
The Tutorials You mean cocktail shaker? I’m pretty sure that’s basically the same as bubble sort, but it scans back and forth across the list of numbers instead of going in the same direction each time.
These are absolutely amazing. I've been watching sorting algorithms for a while now but never really grasped how someone could devise the algorithms, but with the visualization, it's far more simple than what I was making it out to be.
These videos are so awesome, the sorting mechanics are so interesting, plus, the low poly looking models, along with the lesser texture quality really gives it a charm.
You sound like a combination of a caring mother and a patient math teacher. I like it. Especially because of how I'd want a teacher like this. I have ADHD.
I think this video is among the best videos on the internet, and it also shows that it's not only animations that make the video best, it is the mind behind it.. orz
Imagine this with Bogosort. Insertion sort completes sorting the ten balls after just 30 comparisons, and then starts waiting for Bogosort to get done. Eventually, Insertion starts reading the newspaper, and checks his watch to see that it has been 4 hours since Bogo began. Insertion gets bored and leaves, but comes back the next day, to find that Bogo is still no closer to sorting the balls. 50 years later, Insertion comes back with a bushy white beard, with his grand kids carrying 5 trophies that he won in sorting competitions while he was gone, Bogo is still no closer, even after 50M more comparisons. In 2163, Insertion's great-great-grandson comes back to find Bogo has finally finished sorting.
Just got your channel in recommended and I must say one of the most comprehensible visualizations I've ever seen! I noticed you've not uploaded new videos for a long time, I hope this isn't the end. Best wishes!
Can you demonstrate a competition "rigged" in the underdog's favour? ie. Bubble sort vs merge sort on an almost sorted list, heap sort vs quick sort but you get half the balls now and half the balls when you're done with that, etc
This series is the best content about computing I've found all year. I'm curious how these are made. Like, were they hand-animated in something like Blender or are they rigged to a simulation that's actually running the algorithms?
They said in another video that they use Autodesk Maya for their animations. Dunno if they do it by hand or rig it to the actual algorithms, but given the 40 minute bogo sort video I'd guess the latter
If comparisons are costly but swaps are not (or moving multiple items at a time is barely more costly than moving a single item), you can do binary insertion sort to use about O(n*log(n)) comparisons but about O(n^2) swaps. Unlike Quicksort, this doesn't rely on luck since the pivots we are choosing are already in a sorted list.
There are many variants to Bubblesort. This video shows one of the most inefficient variants. You can improve Bubblesort performance by sorting in both directions, and keep track of where the last swap occurred to avoid iterating through parts of the array that you know are sorted. You can even sort in both directions within the same loop.
I think one of the rules of the scenario is that the robots cannot remember any swap they've made. The only thing they can remember is their sorting methodology.
Loved it! however bubble sort is sensitive to the sort direction, imagine a case where the largest element is first, and you sort it in the bottom up direction. then you need'll need *N passes* until the top elements will reach the bottom - on the other hand if you sort it from top to bottom you'll need only *1 pass* to sort it. this is why if you do use bubble sort, you run it iteratively in both directions.
You can also dramatically reduce the number of comparisons insertion sort does by using binary search to figure out where the new item belongs. At least if you're dealing with an array not an LLL. This ends up with O(NlogN) comparisons and easily beats superior sorting algorithms on comparison count. however, it does not end up with O(NlogN) total moves but O(N^2). meaning it's still slow. One potential optimization would be to move the sorted data into a different data structure. LLLs come to mind since reordering an LLL is free but binary searching an LLL without indexing is an O(N) operation which is too slow. One possible solution then is to perform the search on a binary tree, where insertion is not such an inherently costly operation. Of course turns our insertion sort into BST sort but still, now it actually has NlogN performance.
I was subbed to this channel years ago because the bots looked goofy and the videos were interesting but now I have grown and I am here again to learn and pass collage exams.
@@326inminecraft Radix could work if you translate the colors to binary values. So the darkest color would be 0000, then 0001, then 0010, aso. The lightest color would be treated as 9, or 1001. The question then is using MSD or LSD (MSD would be better, since it would show how Radix uses divide and conquer)
This reduces the number of comparisons, but it still requires the algorithm to move elements to make room for the newly added element. The video doesn't count these swap operations, but they play a part in the overall performance. See discussion of this idea along with others here: en.wikipedia.org/wiki/Insertion_sort#Variants
![[Laser] Firing squad synchronization problem](http://i.ytimg.com/vi/xV1aKUdlljU/mqdefault.jpg)
Thanks everyone again! I wish I could upload more frequently. There are already some new ideas brewing. I hope I'll get to working on it soon. But yes, it will take some time again :)
Hi udiprod... Let me just say, I like your explanations and how simple you make things to understand. I'm curious as to why you're not moving towards expanding your production and making your videos more frequent. _Patreon_ could help a lot and I for one would really look forward to more stuff from you.
Love the content, wish it could happen more often! But time and life and whatnot. Though... I want an explanation on how Radix Sort works... because it doesn't do comparisons (right?).
i want to see radix sort, but i don't know if it would fit this format
udiprod how about radix sort and bucket sort and cocktail shaker sort?
COCKTAIL SHAKER SORT
HOLY SHIT did you just clearly explain the concept of N operations and how they grow as the input grows using graphing based on a clear visual metaphor?!?
Wait... that's illegal
“You crazy son of a bitch, you actually did it!”
waytoodank
For free!
The analysis at the end...
You just made one of the best videos on sorting on TH-cam.
Please make more analyses when you have the time. We'll be patient ❤️
Still there are 31 fools who unliked the video
@@meenaljain3828 Ahem, 36 fools.
@@meenaljain3828 disliked*
@@meenaljain3828unliked????? 😭😭💀
honestly insertion sort, by the looks of is, is just a backwards bubble sort. I still have no clue, since I don't know EXACTLY how bubble sorts work yet. can someone please link the video?
Leave Bubble Sort alone, it's trying it's hardest.
At least it has a brain and eyes unlike Bogosort
bogosort has eyes to check if he succeeded but it just basically throws the marbles to the ground than vaguely decides their order and than checks if it succeeded
@@no-one-1 hey, bogosort has a very karge brain. By that I mean it uses more to do the same thing because randomly sorting something is actually kinda resources intensive
Bubble Sort is still useful! As long as you only care about the largest/smallest element in a set, that is
😂😂
This is the best video on sorting I've seen on this channel. The part where you analyzed the speeds of the algorithms was very clear and concise.
Niin
I love math and sorting and the intellectual part of this...but I also just love watching the little robots pick up those balls and bring them up to analyze them two at a time...all the little competitions are so cute, while at the same time being incredibly educational.
I remember in my CS class being told that nlog (n) is the most efficient path for computers to take. Now I know why
Sorry to butt in. But: You know why nlog(n) is better than n^2, but you don't know why nlog(n) is the most efficient. I could claim that there is an algorithm that can do it in n time, and you would not be able to prove me wrong.
__
In the model that is used in the video (compare comparisions done of whole objects), nlog(n) indeed is the shortest possible time (you can prove that by considering all the possible permutations, and mapping them on a decision tree). However, if you consider a different model, the RAM model, you are able to sort integers in near linear time (in just n). This sorting algorithm is called Radix sort.
__
Please don't take offense to this, I just want to avoid you from possibly misunderstanding what you think you know.
But O(n) is the best algorithm?
An average of O(n) isn’t found in sorts though, if I recall correctly.
@@TheShinySnivy Radix sort is non-comparative but achieves linear runtime complexity. It can do so because it has access to the digits of the values being sorted (rather than only a less-than, greater-than, or equal-to). It's essentially a count sort, but performed multiple times to count sort by each digit (base-10) or other radix (like base-256).
stop u make my brain hurt
O(n log(n)) is the best you can do given comparison sorts, where the sorting algorithm only has information on greater, less than, or equal to.
Given most data has some sort of absolute order (not only larger than, but by exactly how much), you can achieve O(n) by using a counting sort.
Say you're sorting an array of thousands of elements, but they're all numbers from 0 to 9. The easiest way to sort them is actually to just count how many 0's, 1's, and so on until you've gotten to 9, then put out as many 0's as is counted, then 1's, and so on.
Radix sort is just a way to make counting sorts space-efficient: Instead of scaling linearly with the number of possible values (256 for an 8 bit int or char, 65536 for a 16 bit int, and over 4 billion for a 32 bit int), it scales logarithmic-ally which is much better. Even better, radixes require almost no cross-communication (after all, no comparisons) with a very simple way to combine the results of multiple radix sorts (just add all the counts together), making them very easy to scale across potentially thousands of computers (perfect if you were trying to sort trillions of items across an enormous Cassandra or HBase cluster).
Basically, if you were doing a 32-bit integer, instead of keeping over 4 billion counts, you keep 4 sets of 256 counts, one for each 8 bits. It's cumbersome to explain, but the core of it is a piecewiise counting sort using prefix sums to make it work.
Analysis part in this video is great....
please add this part in every future videos.
Can you make a vid about Gravity sort?
I kinda wanna see a robot doing magic tricks :)
Also please make a video about Langtons Ant? :D
Also Counting Sort plz😀
Then I guess we just represent the objects with numbers then.
@@metachirality Not really sorting objects here, sorting by darkness. That's a number
Also drinkshaker would be cool
The Tutorials You mean cocktail shaker? I’m pretty sure that’s basically the same as bubble sort, but it scans back and forth across the list of numbers instead of going in the same direction each time.
@@KnakuanaRka Cocktail Shaker Sort is just faster than Bubble Sort
These are absolutely amazing. I've been watching sorting algorithms for a while now but never really grasped how someone could devise the algorithms, but with the visualization, it's far more simple than what I was making it out to be.
These videos are so awesome, the sorting mechanics are so interesting, plus, the low poly looking models, along with the lesser texture quality really gives it a charm.
This explains nicely some reasons behind Timsort, which uses insertion sort for tiny parts and merge sort for bigger parts.
also when merging it can recognize large parts that are in one list but not the other and be adaptive to it
A new udiprod video on sorting! I love these videos.
Thanks for including the "map" of comparisons. Watched the video several times during the years and every time finding something useful.
You sound like a combination of a caring mother and a patient math teacher. I like it. Especially because of how I'd want a teacher like this. I have ADHD.
These sorting videos are by far my favorite videos I've ever seen
I've learnt more from these little sorting videos than I did in about three lessons of Computer Science. Good work!
That graph visualization at the end was ABSOLUTE GENIUS!
I love how these videos could help do every day lives especially for sorting
this was LIFE CHANGING. NEVER have my eyes witnessed such beauty before this glorius day. thank you. for everything. 😘😘
moving.
I just want to thank you for making the best sorting algorithm videos I have ever seen!
Also, the analysis part is brilliant!
following channels you think are dead pays off
Finally udiprod make another video :D
I love how all the comments are so supportive and it makes the content even more wholesome
I think this video is among the best videos on the internet, and it also shows that it's not only animations that make the video best, it is the mind behind it.. orz
I can't wait for Radix Sort (LSD)! That sort is my favorite.
BEST video on algorithms i found yet, LOVE IT
Places:
1. Merge Sort (25, 23)
2. Heap Sort (39)
3. Quick Sort (21, 33)
4. Insertion Sort (30)
5. Bubble Sort (44, 42)
Nah, QuickSort very slightly outperforms both heap and mergesort. The 33 was due to QS picking bad pivots (on purpose)
jesus christ this is amazing! Every cs student SHOULD watch this video series, its so awesome!
Imagine this with Bogosort. Insertion sort completes sorting the ten balls after just 30 comparisons, and then starts waiting for Bogosort to get done. Eventually, Insertion starts reading the newspaper, and checks his watch to see that it has been 4 hours since Bogo began. Insertion gets bored and leaves, but comes back the next day, to find that Bogo is still no closer to sorting the balls. 50 years later, Insertion comes back with a bushy white beard, with his grand kids carrying 5 trophies that he won in sorting competitions while he was gone, Bogo is still no closer, even after 50M more comparisons. In 2163, Insertion's great-great-grandson comes back to find Bogo has finally finished sorting.
well 50 million is a lot for an average of 3.6 million per solve on average.
Just got your channel in recommended and I must say one of the most comprehensible visualizations I've ever seen! I noticed you've not uploaded new videos for a long time, I hope this isn't the end. Best wishes!
Best channel for sorting algo
Thank for turning lesson into cartoon for representing the work. The best explanation.
these videos made the boring sorting techniques interesting hats off.
"You want Radix LSD?"
"I want Base Ten!"
"YOU CAN'T HANDLE BASE TEN!!!"
Base 10: AAAAAAAAAAAAAAAAAAAAAAAHHHHHHHH
All I want is a few good ten
Base 16: let me introduce myself
In-Place base 10: Ahem.
I wish i could give two thumbs up, the explanation of the sorting time was superb
Can you demonstrate a competition "rigged" in the underdog's favour? ie. Bubble sort vs merge sort on an almost sorted list, heap sort vs quick sort but you get half the balls now and half the balls when you're done with that, etc
This series is the best content about computing I've found all year.
I'm curious how these are made. Like, were they hand-animated in something like Blender or are they rigged to a simulation that's actually running the algorithms?
They said in another video that they use Autodesk Maya for their animations. Dunno if they do it by hand or rig it to the actual algorithms, but given the 40 minute bogo sort video I'd guess the latter
If comparisons are costly but swaps are not (or moving multiple items at a time is barely more costly than moving a single item), you can do binary insertion sort to use about O(n*log(n)) comparisons but about O(n^2) swaps. Unlike Quicksort, this doesn't rely on luck since the pivots we are choosing are already in a sorted list.
There are many variants to Bubblesort. This video shows one of the most inefficient variants. You can improve Bubblesort performance by sorting in both directions, and keep track of where the last swap occurred to avoid iterating through parts of the array that you know are sorted. You can even sort in both directions within the same loop.
Patrick Coston The robots might need some upgrades for that.
I think one of the rules of the scenario is that the robots cannot remember any swap they've made. The only thing they can remember is their sorting methodology.
Loved it!
however bubble sort is sensitive to the sort direction,
imagine a case where the largest element is first, and you sort it in the bottom up direction. then you need'll need *N passes* until the top elements will reach the bottom - on the other hand if you sort it from top to bottom you'll need only *1 pass* to sort it.
this is why if you do use bubble sort, you run it iteratively in both directions.
That's a different sort called cocktail shaker sort also known as bidirectional bubble sort
Bubble sort ran in both ways has its own name
It is called "cocktail shaker sort"
great content as per usual ........more frequent posts & this would clearly be among the "top' channels of its kind.
Far better than anything Wikipedia would offer.
You can also dramatically reduce the number of comparisons insertion sort does by using binary search to figure out where the new item belongs. At least if you're dealing with an array not an LLL. This ends up with O(NlogN) comparisons and easily beats superior sorting algorithms on comparison count.
however, it does not end up with O(NlogN) total moves but O(N^2). meaning it's still slow.
One potential optimization would be to move the sorted data into a different data structure. LLLs come to mind since reordering an LLL is free but binary searching an LLL without indexing is an O(N) operation which is too slow.
One possible solution then is to perform the search on a binary tree, where insertion is not such an inherently costly operation. Of course turns our insertion sort into BST sort but still, now it actually has NlogN performance.
Legend says, each year, udiprod will have a day off from work. In this day, he ... :))
The brawl finally continues...
first tym in 4 years I got the concept right love from Pakistan
I was subbed to this channel years ago because the bots looked goofy and the videos were interesting but now I have grown and I am here again to learn and pass collage exams.
Wow guys u put a lot of effort on ur vids i really appreciate that
First!!!!
One of the best channels on TH-cam!!!!
The end of an era. Please come back :
Thanks. I'm working on a new video. I hope to release it soon.
@@udiprod That's awesome. Can't wait!
Insertion sort at the end was just like "so wtf do i do now"
Maybe radix sort next time? Great video btw
oh the sorting videos with sounds with radix base 10 get so LOUD
Radix sort is for sorting numbers not colors
FplusE TV Channel you can easily number the colors
Aaron Luedemann no, it would be something like 190,280,245,346,766,455
For radix to works, single digit won’t do
@@326inminecraft Radix could work if you translate the colors to binary values. So the darkest color would be 0000, then 0001, then 0010, aso. The lightest color would be treated as 9, or 1001. The question then is using MSD or LSD (MSD would be better, since it would show how Radix uses divide and conquer)
Yes I was waiting for this. I really liked the previous parts so I want to see one about insertion. Thank you :)
You're alive! You're alive!
This video should be in every programming 101 education.
This is awesome! These videos are going to carry me throug my algorithms course!
This is so relaxing and fun!
wonderfull video. explained the log(n) i was always wondering about in terms of performance and scalability of a method.
*The time complexities are*
Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Storage: O(1)
Can you make a video about selection sort ? The videos are amazing bro .
Yay a video!
See you next year!!!
Next, can you please do Insertion versus selection sort?
This would be an excellent introduction to big O notation
You still haven't done Bogosort :)
Rishi Is Here
nevermind short-sighted, this robot’s fuckin blind
That One Guy thats for bozo sort
Bogo sort is still sorting the balls to this day
@@diamboy dont be mean hes trying his best
Oh my god udiprod actually did it
And they animated it fully
finally a video worth my time
How about a video on Timsort, most likely quickest sorting algorithm of them all?
Glad to have a new video
Not here for computer science. Here for the intense competition. It wasn't even a fair match. You'll always be the winner in my heart Bubble Sort :_)
I really like these animations, too bad the uploads are infrequent. It takes a lot of work to do this
These videos are amazing. Great content!
STANDINGS:
21 Quicksort
44 Bubble Sort
44 Merge Sort
52 Quicksort
39 Heap Sort
23 Merge Sort
30 Insertion Sort
44 Bubble Sort
what an awesome explanation
im oddly addicted to these
Lovely demonstration
Could you please make videos on pointers and self referential structures?
Could you do a video on BOGO sort vs some other sorting algorithm like gravity or insertion sort?
Still no glasses on the robots!?it would increase efficiently by like,400%!
Even before the match I knew insertion sort would win
I love your videos so much
But can't you do Insertion Sort using a binary search on the sorted part? Theoretically this would cut it down to n*log(n) as well.
This reduces the number of comparisons, but it still requires the algorithm to move elements to make room for the newly added element. The video doesn't count these swap operations, but they play a part in the overall performance.
See discussion of this idea along with others here: en.wikipedia.org/wiki/Insertion_sort#Variants
What about if your robots can see far and wide, unlike insertion sort or bubble
We could perform radix
That animation at the end was so legit
This is perfection.
They are back 0.0
This is awesome!
Recently youtube added the ability to change audio track to another language, I would love to help for dubbing in french
Loved it! Great job!
Fantastic. Thanks. So this is about AI and computer efficiency. And can it be applied to commercial processes?
Robots are really nice.
Competition is awesome😀
Insertion sort is usually how I sort things, though admittedly a bit less robotic.
are bubble sort and insersion sort the same thing but one backwards?
Welcome back to why is this in my recommends and why do i like it?
Woo Hoo! Finally another video
hey, this is super helpful, thanks!
Thank you for your effort...
I LOVE this videos, thank you!
What is really the difference between the two. Both involves comparing the neighbors and swapping
i had to watch this for homework!
Super analysis
it is a really great video to understand algorithm
Can you try radix sort? I don't know how that would work with colors, though.
Number the colours