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?).
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
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 RUclips. 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?
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.
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.
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 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.
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.
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.
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.
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
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.
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!
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.
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.
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.
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
@@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)
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.
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
I edited my last comment because I realized that selection and shell start with s so I decided to keep your sorts all different letter beginners and I think cocktail sort can be more fun
Maybe if you use numbers on ball instead of colours then it will be more clearer... Comparing colours intensity is sometimes difficult... JazakuMuLLahu Khairan...
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](/img/1.gif)
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
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
😂😂
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 RUclips.
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?
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 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.
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.
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
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
Analysis part in this video is great....
please add this part in every future videos.
Thanks for including the "map" of comparisons. Watched the video several times during the years and every time finding something useful.
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.
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.
A new udiprod video on sorting! I love these videos.
That graph visualization at the end was ABSOLUTE GENIUS!
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
following channels you think are dead pays off
I love how these videos could help do every day lives especially for sorting
I can't wait for Radix Sort (LSD)! That sort is my favorite.
this was LIFE CHANGING. NEVER have my eyes witnessed such beauty before this glorius day. thank you. for everything. 😘😘
moving.
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)
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.
I've learnt more from these little sorting videos than I did in about three lessons of Computer Science. Good work!
I love how all the comments are so supportive and it makes the content even more wholesome
I just want to thank you for making the best sorting algorithm videos I have ever seen!
Also, the analysis part is brilliant!
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
Finally udiprod make another video :D
"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.
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.
jesus christ this is amazing! Every cs student SHOULD watch this video series, its so awesome!
BEST video on algorithms i found yet, LOVE IT
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!
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.
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.
these videos made the boring sorting techniques interesting hats off.
Insertion sort at the end was just like "so wtf do i do now"
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"
Thank for turning lesson into cartoon for representing the work. The best explanation.
*The time complexities are*
Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Storage: O(1)
The brawl finally continues...
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
Far better than anything Wikipedia would offer.
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)
Best channel for sorting algo
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!
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.
This video should be in every programming 101 education.
I wish i could give two thumbs up, the explanation of the sorting time was superb
This would be an excellent introduction to big O notation
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
great content as per usual ........more frequent posts & this would clearly be among the "top' channels of its kind.
Legend says, each year, udiprod will have a day off from work. In this day, he ... :))
Can you make a video about selection sort ? The videos are amazing bro .
Still no glasses on the robots!?it would increase efficiently by like,400%!
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
Next, can you please do Insertion versus selection sort?
Wow guys u put a lot of effort on ur vids i really appreciate that
and so, here we are again, watching educational videos at midnight trying to sleep
wonderfull video. explained the log(n) i was always wondering about in terms of performance and scalability of a method.
This is awesome! These videos are going to carry me throug my algorithms course!
first tym in 4 years I got the concept right love from Pakistan
im oddly addicted to these
Yes I was waiting for this. I really liked the previous parts so I want to see one about insertion. Thank you :)
How about a video on Timsort, most likely quickest sorting algorithm of them all?
You're alive! You're alive!
That animation at the end was so legit
This is so relaxing and fun!
This is awesome!
Recently youtube added the ability to change audio track to another language, I would love to help for dubbing in french
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 :_)
STANDINGS:
21 Quicksort
44 Bubble Sort
44 Merge Sort
52 Quicksort
39 Heap Sort
23 Merge Sort
30 Insertion Sort
44 Bubble Sort
Yay a video!
See you next year!!!
Insertion sort is usually how I sort things, though admittedly a bit less robotic.
Legends Say The Comparison Amount Is Still Racing...
Robots are really nice.
Competition is awesome😀
It has been a year, WHERE ARE YOU?!
I'm working on new videos. I hope to post them soon.
Can you make selection sort and cocktail sort
Yes, they're often requested. I'll try to get to them too.
I edited my last comment because I realized that selection and shell start with s so I decided to keep your sorts all different letter beginners and I think cocktail sort can be more fun
Even before the match I knew insertion sort would win
Lovely demonstration
Glad to have a new video
Do counting sort, gravity sort or bogo sort next
are bubble sort and insersion sort the same thing but one backwards?
What is really the difference between the two. Both involves comparing the neighbors and swapping
Could you do a video on BOGO sort vs some other sorting algorithm like gravity or insertion sort?
I'd like to see Gravity Sort, Counting Sort, and Radix Sort
Could you please make videos on pointers and self referential structures?
These videos are amazing. Great content!
finally a video worth my time
Welcome back to why is this in my recommends and why do i like it?
They are back 0.0
Maybe if you use numbers on ball instead of colours then it will be more clearer... Comparing colours intensity is sometimes difficult... JazakuMuLLahu Khairan...
See you next year :D
First!!!!
One of the best channels on RUclips!!!!
what an awesome explanation
Bogo sort next please!
What would make it a close game except for luck and two bogos?
With your Upload-Shedule your next Video should come soon. NICE.
More interested in newer n log n algorithms that also optimize the memory operations cost, such as tsort.
I think the heap sort would be good by doing quick sort to make 2 groups
Fantastic. Thanks. So this is about AI and computer efficiency. And can it be applied to commercial processes?
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
We NEED to collab on the next sorting video.