Everything is smartly thought to approximate all the concepts for everyone to understand, like the robot only being able to compare 2 balls at a time to explain the fact that only humans can roughly compare lots of values (and also the fact that with merge sort the robot had to push the balls when finished sorting...)
While this may seem like it's a marginal improvement over insertion sort if you manage to crack the gap code, remember that we are only working with very small lists of 10 items at a time. Once you scale up the list to hundreds or thousands, it becomes a completely different ball game and things like shell sort kick insertion sort to the curb.
Insertion sort is also being handy capped by not using an binary search to find the insertion location. On 10 it would be a rather small reduction of checks, but savings scale up significantly on the hundreds or thousands of element cases.
@@TheFinagle You also need to account for the complexity of actually inserting the value into the array. Binary search makes it faster for you to find the location, but once you do, you still need to shift a bunch of elements over by one position to make room. Insertion sort does that as it is walking the array.
It's been over a decade since his first sorting video yet he is still interested in making sorting videos. Guys, dedicate to your friends and family like this guy dedicate to sorting algorithms.
for the question at 6:16, I think it's due to shell sort spending more time moving different elements from one place to another on the rack, whereas insertion sort was almost always holding one element and comparing others to it.
I think that's also why the jet boosts were way more advantageous for Shell Sort. Insertion Sort didn't really utilize the rockets much, but Shell Sort necessarily has to go long distances.
There are several general-case sequences that work pretty close to optimally for larger lists; The Wikipedia article on Shell Sort has a list of them and how to generate them.
Having watched a decade of sorting videos as if they were released as a series over the course of a week, the robots getting jet engines is hilarious and a wild plot twist. Also the whole series is just well made and really shows off the differences in the algorithms.
I really like this lines display. Surely on Quick sort it would show at a glance how the first iteration partitions the set into two non-overlapping subsets.
Insertion is best with actual physical objects, when making room to insert an object in is as simple as shoving everything to the right of it further to the right, rather than with computer memory, moving it over to the next memory address for each and every individual item in memory. With my DVD collection, inserting a movie between positions 23 and 24 out of 50 means shoving all DVD cases 24 through 50 together to the right by .5 inch all at once which can be done in one swift motion of a hand. While in a computer, that means moving the item in slot 50 to slot 51... then moving the item in slot 49 into slot 50, and then moving the item in slot 48 to slot 49... all the way down to then moving the item in slot 24 to slot 25, and then and only then having the space to put the new item into slot 24.
Or if you have a linked-list, but you then need a way to perform the binary search. A linked list is where the computer grabs a random chunk of memory for the new data field, uses pointers to identify that chunk of memory, then has the predecessor and successor items re-point from each other to the new item. After the list is sorted, you then copy the elements from the linked list to the final list. A linked list is composed of multiple individual data elements, where each data element is composed of the data value, and two pointer values (forward and backward). Element number one has a data value, and two empty pointers. When element number two is added (assuming element number two is supposed to go after element #1), then the 'forward' pointer is reassigned to point at the location of data element number two. Element number two has its backwards pointer to point at element number one. From there, items number three is analyzed. Item number thre3e is discovered to fit between elements #1 and #2. So another chunk of memory is grabbed, the data value for item #2 is put in that chunk of memory, and then the pointers for element number three are updated. The #3 'forward' pointer is changed to point to element #2, and the backward pointer is changed to point at element #1. Similarly, element #1 has its forward pointer changed to point to element #3, and element #2 has its backwards pointer changed to point at element #3. (apologies for the words, but I need pretty pictures to better explain it)
I think it'd be better if the balls were numbered because it's hard to tell the difference between some of the shades of red and think about sorting them. would also be better for colorblind people
I love this channel, and what I love the most is that even thought it's been 15 years the art style hasn't changed a bit. Wish you would upload more often
I would like to see gnome sort next, you explain sorting algorithms really well and i cant understand the difference between gnome sort and insertion sort so making a video about it would help me a lot, thanks. Edit: i finally understood it, but a video about it would be cool!
The Ciura gaps are said to be the most optimal for shell sort of no specific input length, and shell sort is preferred over quicksort in tight applications because of its small code size, but it's cache unfriendly because of why the robot lags behind in comparisons per second. One reason why the optimal gaps barely beat insertion is because its best case is O(n log n) instead of O(n)
While using "the jet engines" do not forget it doesn't always work like this in the real life where we have caches and bus widths. Chances are the comparisons (let's assume we just sort some 8-bit values) will take the addresses far enough to make the memory controller trigger a full-width read for every byte it needs, see ya performance :)
@@typhoonzebra there's a Bogosort video it's hilarious it's 40 minutes long, and 35 of it is literally waiting for Bogosort to actually finish randomizing
I would absolutely watch a 1 hour video of this style animation with the robots sorting a 100-element list or whatever the max you could do in an hour or so. Maybe get more algorithms going at once even.
I eventually want to see a large competition of all sorts. Not only to see all the different screens of each sort all together, but a "look how far we've come" from slower but vaguely effective sorts to...shell and beyond.
Great sorting explanation as always! If you guys take requests, can you show the way a Circle Sort acts? Or a Comb Sort? Either one would be really fun to see.
You should do a comparison on bigger lists. With 100+ elements shell sort will be significantly faster than simple insertion. Actually the biggest reason why Quick, Merge or Shell Sort are much faster is because they can easily switch elements that are far from each other. Comb sort was developed with this idea in mind. Comb sort is a simple bubble, that uses sublists with wide gaps. However Insertion Sort works really well on small or almost sorted lists, where each element has to move just a few spaces. This is why hybrid sorts often use Insertion sort as a last step on almost sorted list, because it's the fastest way.
I remember watching these in high school! I don’t know if you thought about visualizing quantum algorithms, and most quantum sorts don’t outperform classical sorts, but if you could figure out how to visualize Grover’s algorithm or Shor’s that’d be so cool!
Not in the gap sequences used in the video, but for some gap sequences it's true. For example a gap sequence of 3-2-1 guarantees it. Other gap sequence guarantee larger bounds. I'll soon post more details on that.
If the second to last gap size is n (assuming the last gap size is 1) then I'm pretty sure each element is guaranteed to be n-1 positions away from it's final position at most. Assuming my math is good, I feel like you could improve the worst case speed of the algorithm pretty significantly by having it move on to the next element after n-1 comparisons since the nth comparison would be guaranteed to show the two elements don't need to swap. You might even be able to use a similar rule for every sub-sort after the first.
I have some ideas for future episodes. Slow Sort vs Stooge Sort: Who Is Slower? Bozo Sort vs Bogo Sort: Who Is Slower? Comb Sort vs Shell Sort: What's The Difference Bitonic Sort vs Merge Sort: What's The Difference Radix LSD Sort vs Quick Sort: What's The Difference Cocktail Shaker Sort vs Bubble Sort: Who Is Faster? Tim Sort vs Cycle Sort: Who Is Faster? Radix MSD Sort vs Quick Sort: What's The Difference? Odd-Even Sort vs WikiSort: Who Is Faster?
As for the question in the end, I'm sure the answer is insertion sort keeps comparing the same ball with others for longer, and changing only one ball while keeping the other in it's hand is faster than dropping and picking up two balls
I think the lag in comparisons per second has to do with the fact that insertion sort does most of its comparisons with one ball at a time, and so it only has to pick up and put down one ball at a time. Shell sort has more putting down and picking up of two
Would be interesting to see binary insertion sort. Of course, the improvement would be very minor on such a small set, but it would still be interesting.
Never had I felt this tense between two robots in a sorting competition. Shell sort should work better in theory due to moving elements closer and closer, but the time it took moving and the lack of optimization made me nervous in this match.
I have a sorting algorithm that idk its name. Here's the algorithm: + Step 1: Called "gap" = length(array) - 1 + Step 2: Assign k = 0 + Step 3: If (gap + k) is larger than or equal to length(array) then decrement gap and go to step 2. + Step 4: Swap the element at (k) and the element at (gap + k) + Step 5: Increment k. Go to step 3.
In those robot sort matches, the robots take time performing certain actions like moving left and right a lot in shell sort, or pushing balls down the shelf in merge sort. How much time would an actual modern computer perform each operation in a sort algorithm?
![[Laser] Firing squad synchronization problem](http://i.ytimg.com/vi/xV1aKUdlljU/mqdefault.jpg)
I like how the robots having to move the full distance between balls approximates the idea of data locality
Everything is smartly thought to approximate all the concepts for everyone to understand, like the robot only being able to compare 2 balls at a time to explain the fact that only humans can roughly compare lots of values (and also the fact that with merge sort the robot had to push the balls when finished sorting...)
I thought this was cool too but what is the real life equivalent of the rocket boosters in the second race?
@@stuartallen2001 clock speed
@@stuartallen2001 Increased cache size.
@@stuartallen2001 memory latency
While this may seem like it's a marginal improvement over insertion sort if you manage to crack the gap code, remember that we are only working with very small lists of 10 items at a time. Once you scale up the list to hundreds or thousands, it becomes a completely different ball game and things like shell sort kick insertion sort to the curb.
And shell sort is among the slower sorts in that tier, too.
Insertion sort is also being handy capped by not using an binary search to find the insertion location. On 10 it would be a rather small reduction of checks, but savings scale up significantly on the hundreds or thousands of element cases.
@@TheFinagle You also need to account for the complexity of actually inserting the value into the array. Binary search makes it faster for you to find the location, but once you do, you still need to shift a bunch of elements over by one position to make room. Insertion sort does that as it is walking the array.
@@TheFinagle Yeah, that's a huge handicap. It would go from O(n^2) comparisons, to O(n*log(n)) comparisons by using a binary search.
@@pseudo_goose Your right, I hadn't though of that.
And if your data type can do easy arbitrary insertion its usually not binary search friendly.
I love that 13 years after the first video you guys are still doing 3d animations with the exact same robot model
me too. it does a good job of keeping the old videos feeling pretty timeless
Hey, if it ain't broke, don't fix it!
It's been over a decade since his first sorting video yet he is still interested in making sorting videos. Guys, dedicate to your friends and family like this guy dedicate to sorting algorithms.
🥺
😊
for the question at 6:16, I think it's due to shell sort spending more time moving different elements from one place to another on the rack, whereas insertion sort was almost always holding one element and comparing others to it.
I was thinking the same thing. You hit all the points I noticed.
Right! I just added a detailed account here: www.udiprod.com/shell-sort/#timing
But she'll sort had 1 extra comparison
I think that's also why the jet boosts were way more advantageous for Shell Sort. Insertion Sort didn't really utilize the rockets much, but Shell Sort necessarily has to go long distances.
The fact that this channel is still making these late 1990s-esque animations in the 21st century really keeps me going. Love these robots!
Shell sort is one of the most interesting sorting algorithms, im glad you’re making videos about it
Upside: gets into O(nlogn) territory with the right gap sequence
Downside: you need to calculate that gap sequence ahead of time
There are several general-case sequences that work pretty close to optimally for larger lists; The Wikipedia article on Shell Sort has a list of them and how to generate them.
Thanks to these videos, I now understand the "sounds of sorting" videos TH-cam keeps recommending me.
Having watched a decade of sorting videos as if they were released as a series over the course of a week, the robots getting jet engines is hilarious and a wild plot twist.
Also the whole series is just well made and really shows off the differences in the algorithms.
I really like this lines display. Surely on Quick sort it would show at a glance how the first iteration partitions the set into two non-overlapping subsets.
Yeah, it definitely would, could be a cool addition for quick sort video.
The fact that you've used this same visualization for 10+ years with few changes is delightful to me
I like these animations. They make the video easy and intuitive to understand.
Almost 10 years and still making these animations. Kings
Finally, a new udiprod video! I've been waiting for so long lol
Good that the sorts are back
Babe wake up, new udiprod video just dropped
Wow, the coolest explanation and visualization of Shell sort I've seen! Thank you so much. So simple, short and clear explanation
The sort comparisons are back! How about a video highlighting how much the result can be rigged with carefully crafted inputs?
Insertion is best with actual physical objects, when making room to insert an object in is as simple as shoving everything to the right of it further to the right, rather than with computer memory, moving it over to the next memory address for each and every individual item in memory. With my DVD collection, inserting a movie between positions 23 and 24 out of 50 means shoving all DVD cases 24 through 50 together to the right by .5 inch all at once which can be done in one swift motion of a hand. While in a computer, that means moving the item in slot 50 to slot 51... then moving the item in slot 49 into slot 50, and then moving the item in slot 48 to slot 49... all the way down to then moving the item in slot 24 to slot 25, and then and only then having the space to put the new item into slot 24.
Or if you have a linked-list, but you then need a way to perform the binary search. A linked list is where the computer grabs a random chunk of memory for the new data field, uses pointers to identify that chunk of memory, then has the predecessor and successor items re-point from each other to the new item. After the list is sorted, you then copy the elements from the linked list to the final list.
A linked list is composed of multiple individual data elements, where each data element is composed of the data value, and two pointer values (forward and backward). Element number one has a data value, and two empty pointers. When element number two is added (assuming element number two is supposed to go after element #1), then the 'forward' pointer is reassigned to point at the location of data element number two. Element number two has its backwards pointer to point at element number one.
From there, items number three is analyzed. Item number thre3e is discovered to fit between elements #1 and #2. So another chunk of memory is grabbed, the data value for item #2 is put in that chunk of memory, and then the pointers for element number three are updated. The #3 'forward' pointer is changed to point to element #2, and the backward pointer is changed to point at element #1. Similarly, element #1 has its forward pointer changed to point to element #3, and element #2 has its backwards pointer changed to point at element #3.
(apologies for the words, but I need pretty pictures to better explain it)
In most cases, an array will be faster. The properties of a linked list are more suited for algorithms like the shunting yard algorithm
I think it'd be better if the balls were numbered because it's hard to tell the difference between some of the shades of red and think about sorting them. would also be better for colorblind people
Commenting to boost this, cus I have red-green color deficiency.
Really? I thought you could differentiate shades of the same color, just not tell the colors apart
Would also help understanding radix sort
@@affegpus4195 it might depend on the specific type of colourblindness, perhaps?
no
Boy I can't wait for you guys to explain the absolute magic that is Radix sort. I wish I understood how that thing worked.
I have a feeling that this is about to be recommended to everyone
I need more of this. I love coming back here from time to time to watch these guys sort!
Really awesome to see this channel upload!
I love these visual expressions and explanations of algorithms! Please more!
STANDINGS:
21 Quicksort
44 Bubble Sort
44 Merge Sort
52 Quicksort
39 Heap Sort
23 Merge Sort
30 Insertion Sort
44 Bubble Sort
36 Bubble Sort
81 Stooge Sort
27 Stooge Sort
605 Bogosort
30 Insertion Sort
31 Shell Sort
Where is Shell(9,6,1) Sort? It's not a proper sort, just a modification of Shell Sort.
I don't get what's going on here
Those are the current standings of all the sorting algorithms featured so far.
Its the same list?
@@affegpus4195 I don't remember.
Wake up babe, new udiprod video about sorting algorithms just dropped
The Return of The King
I love this channel, and what I love the most is that even thought it's been 15 years the art style hasn't changed a bit. Wish you would upload more often
It's always a good thing to see a new Udiprod video.
I found this channel just a few weeks ago, glad they updated
new udiprod sorting algo vid dropped?????? why was i not informed immediately. absolutely fantastic
I am CS student but I'm bad at math and algorithm
Thank you, now I can understand most of basic understanding
I would like to see gnome sort next, you explain sorting algorithms really well and i cant understand the difference between gnome sort and insertion sort so making a video about it would help me a lot, thanks.
Edit: i finally understood it, but a video about it would be cool!
@qwrt Actually me too, but as of now, I STILL DON´T KNOW THE DIFFERENCE OF GNOME SORT AND INSERTION SOTR, PLEASE EXPLAIN!
When the world most called for him, he returned
so glad we are getting another sorting video
I love that you keep making videos! I really like them, they're quite interesting and relaxing
I had no idea you were still making videos and I am so glad you are. Keep up the good work! I love these vids
Finally! Another video!
"This is a sorting algorithm, it loses. So lets give it alot of extra advantages and see it win"
Yay! Another sorting video! We sub for these and we will always come back no matter how long!
Would have been interesting to see binary insertion sort, another optimization to insertion sort
Why is this so fascinating to binge watch?
Thank you for continuing this series!
what a beauty this channel is!
its always a great surprise when you upload !
Thanks! I didn't know how shell sort worked until I saw this video!
I never thought I'd understand Shell sort. Thank you
Ooo, new sorting videos! I love these!
The Ciura gaps are said to be the most optimal for shell sort of no specific input length, and shell sort is preferred over quicksort in tight applications because of its small code size, but it's cache unfriendly because of why the robot lags behind in comparisons per second. One reason why the optimal gaps barely beat insertion is because its best case is O(n log n) instead of O(n)
I really enjoyed this demonstration of shell and insertion sorting. Thank you so much for making these videos :)
Thanks. I now know shell sort. I was confused what shell sort does. This video helped me.
HUGE UPSET!! LETS GO INSERTION SORT
Shell sort training arc went crazy though
While using "the jet engines" do not forget it doesn't always work like this in the real life where we have caches and bus widths. Chances are the comparisons (let's assume we just sort some 8-bit values) will take the addresses far enough to make the memory controller trigger a full-width read for every byte it needs, see ya performance :)
Could we get some comparisons on MUCH larger sets? I feel like some only truly shine when the amount of data grows.
Like Bogo sort
Or std::sort
@@typhoonzebra there's a Bogosort video
it's hilarious
it's 40 minutes long, and 35 of it is literally waiting for Bogosort to actually finish randomizing
@@musicexams5258 Just came back from that. Glad to see they have recognised the ultimate sorting method.
Thank you Uriprod, your videos are so helpful and intuitive!!
Thanks once again for these extremely informative videos!
I would absolutely watch a 1 hour video of this style animation with the robots sorting a 100-element list or whatever the max you could do in an hour or so. Maybe get more algorithms going at once even.
Nothing better than watching these videos at 2:30 AM
I eventually want to see a large competition of all sorts. Not only to see all the different screens of each sort all together, but a "look how far we've come" from slower but vaguely effective sorts to...shell and beyond.
this is the best channel
Great sorting explanation as always! If you guys take requests, can you show the way a Circle Sort acts? Or a Comb Sort? Either one would be really fun to see.
i have wanted more of these so bad
Nobody:
Nosoul:
These videos lore if robots weren't shortsighted:
Finally, a new algorithm! Could you please do a video on Cocktail Shaker Sort, or maybe Gravity Sort?
You should do a comparison on bigger lists. With 100+ elements shell sort will be significantly faster than simple insertion. Actually the biggest reason why Quick, Merge or Shell Sort are much faster is because they can easily switch elements that are far from each other. Comb sort was developed with this idea in mind. Comb sort is a simple bubble, that uses sublists with wide gaps.
However Insertion Sort works really well on small or almost sorted lists, where each element has to move just a few spaces. This is why hybrid sorts often use Insertion sort as a last step on almost sorted list, because it's the fastest way.
th-cam.com/video/8MsTNqK3o_w/w-d-xo.html
Hey this is actually really easy to understand
I know nothing about computing, but I do like those hardworking bots moving the balls.
I remember watching these in high school! I don’t know if you thought about visualizing quantum algorithms, and most quantum sorts don’t outperform classical sorts, but if you could figure out how to visualize Grover’s algorithm or Shor’s that’d be so cool!
In the last shell sort step, is each ball guaranteed to be either in its correct position or next to it? Or can it be further away?
Not in the gap sequences used in the video, but for some gap sequences it's true. For example a gap sequence of 3-2-1 guarantees it. Other gap sequence guarantee larger bounds. I'll soon post more details on that.
If the second to last gap size is n (assuming the last gap size is 1) then I'm pretty sure each element is guaranteed to be n-1 positions away from it's final position at most. Assuming my math is good, I feel like you could improve the worst case speed of the algorithm pretty significantly by having it move on to the next element after n-1 comparisons since the nth comparison would be guaranteed to show the two elements don't need to swap. You might even be able to use a similar rule for every sub-sort after the first.
These videos r kinda helpful to learn sorts
I love these robot dudes so much. 24 ball race when
I have some ideas for future episodes.
Slow Sort vs Stooge Sort: Who Is Slower?
Bozo Sort vs Bogo Sort: Who Is Slower?
Comb Sort vs Shell Sort: What's The Difference
Bitonic Sort vs Merge Sort: What's The Difference
Radix LSD Sort vs Quick Sort: What's The Difference
Cocktail Shaker Sort vs Bubble Sort: Who Is Faster?
Tim Sort vs Cycle Sort: Who Is Faster?
Radix MSD Sort vs Quick Sort: What's The Difference?
Odd-Even Sort vs WikiSort: Who Is Faster?
Babe wake up, there's a new sorting robot video
Babe wake up new udiprod sorting video
babe wake up new udiprod sorting algorithm video
The advantage of shell sort over insertion sort grows substantially as the size of the set rises.
Let's goo, another sorting video
I'd like to see how bitonic sort works.
Or maybe cocktail shaker
Love the animation. Keep up the good work.
yoooo new sorting method video just dropped
I wonder how Radix LSD out of place sorting would be like
wake up babe. new uniprod video just dropped.
Amazing! Very well explained
As for the question in the end, I'm sure the answer is insertion sort keeps comparing the same ball with others for longer, and changing only one ball while keeping the other in it's hand is faster than dropping and picking up two balls
Can you please make a merge sort vs insertion sort? My friends have a debate that needs to be solved
I think this is a very good idea!
I think the lag in comparisons per second has to do with the fact that insertion sort does most of its comparisons with one ball at a time, and so it only has to pick up and put down one ball at a time. Shell sort has more putting down and picking up of two
Would be interesting to see binary insertion sort. Of course, the improvement would be very minor on such a small set, but it would still be interesting.
New sorting algorithm dropped. All my friendsove sorting algorithms.
Can you do bozosort? It's like bogosort but instead of shuffling the entire thing it shuffles two random parts of the thing
Never had I felt this tense between two robots in a sorting competition. Shell sort should work better in theory due to moving elements closer and closer, but the time it took moving and the lack of optimization made me nervous in this match.
Shell sort is quite a smart one, I feel that if we have a thousand balls instead of just 10, shell sort would have an immense advantage.
Oh hey, you're still alive!
Can we get Radix sort
I feel like just a 5-second snippet of these robots sorting 100 items would have been a good visual representation that Shell Sort scales way better.
Honestly this editing was better imo
I have a sorting algorithm that idk its name. Here's the algorithm:
+ Step 1: Called "gap" = length(array) - 1
+ Step 2: Assign k = 0
+ Step 3: If (gap + k) is larger than or equal to length(array) then decrement gap and go to step 2.
+ Step 4: Swap the element at (k) and the element at (gap + k)
+ Step 5: Increment k. Go to step 3.
Other people: Watching Netflix Stranger Things 4
Me: Watching two robots sorting color balls
Hello! What is the best way to contact you, because I have a question about your work in general. I have tried email in the past and failed.
I replied you email just now, I think. Sorry I must have missed it.
@@udiprod Thank you, I have replied to your reply.
In those robot sort matches, the robots take time performing certain actions like moving left and right a lot in shell sort, or pushing balls down the shelf in merge sort. How much time would an actual modern computer perform each operation in a sort algorithm?
The time will depends on the number of comparisons
Practically instant for array data structures, linear time for linked node structures