Insertion Sort vs Bubble Sort + Some analysis
Вставка
- Опубліковано 30 вер 2024
- A visual demonstration of insertion sort, competition with bubble sort, and performance analysis including these two and quick sort.
See more notes and a more accurate analysis of the algorithms performance:
www.udiprod.co...
Previous matches:
Heaps sort vs merge sort
• Heaps and Heap Sort
Merge sort vs quick sort
• Merge Sort vs Quick Sort
Quick sort vs bubble sort
• Visualization of Quick...
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!
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
The analysis at the end...
You just made one of the best videos on sorting on UA-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?
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
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
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.
following channels you think are dead pays off
Analysis part in this video is great....
please add this part in every future videos.
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.
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
A new udiprod video on sorting! I love these videos.
Finally udiprod make another video :D
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
I can't wait for Radix Sort (LSD)! That sort is my favorite.
The brawl finally continues...
"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.
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 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
Still no glasses on the robots!?it would increase efficiently by like,400%!
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)
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.
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)
Thanks for including the "map" of comparisons. Watched the video several times during the years and every time finding something useful.
*The time complexities are*
Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Storage: O(1)
Legends Say The Comparison Amount Is Still Racing...
I just want to thank you for making the best sorting algorithm videos I have ever seen!
Also, the analysis part is brilliant!
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.
I know this is smart. Yeah. I know this... :D cool video :) greetings from Poland :)
Insertion sort at the end was just like "so wtf do i do now"
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 have no idea what any of this is or what it means, i just like watching these sweet lil robot fellas sorting their colourful balls :))))
Far better than anything Wikipedia would offer.
Insertion sort is usually how I sort things, though admittedly a bit less robotic.
This is awesome! These videos are going to carry me throug my algorithms course!
This would be an excellent introduction to big O notation
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.
Can you make a video about selection sort ? The videos are amazing bro .
are bubble sort and insersion sort the same thing but one backwards?
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.
Thank You !
this poor robot lives inside my cpu?
Next, can you please do Insertion versus selection sort?
They need to get glasses for the next robots
This is so relaxing and fun!
I really like these animations, too bad the uploads are infrequent. It takes a lot of work to do this
When the Fuhrer yells,
WE GOTTA HAVE MORE SHELLS! 🐚
(Please create shell sort)
this was LIFE CHANGING. NEVER have my eyes witnessed such beauty before this glorius day. thank you. for everything. 😘😘
moving.
I love how these videos could help do every day lives especially for sorting
this video is so...f*cking awesome.
How to sort your books:
I love how all the comments are so supportive and it makes the content even more wholesome
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
hey, this is super helpful, thanks!
Bubble-sort:
am I a joke to you?
What is really the difference between the two. Both involves comparing the neighbors and swapping
You're alive! You're alive!
I wish i could give two thumbs up, the explanation of the sorting time was superb
Best channel for sorting algo
First!!!!
One of the best channels on UA-cam!!!!
STANDINGS:
21 Quicksort
44 Bubble Sort
44 Merge Sort
52 Quicksort
39 Heap Sort
23 Merge Sort
30 Insertion Sort
44 Bubble Sort
Maybe if you use numbers on ball instead of colours then it will be more clearer... Comparing colours intensity is sometimes difficult... JazakuMuLLahu Khairan...
I've learnt more from these little sorting videos than I did in about three lessons of Computer Science. Good work!
what an awesome explanation
With your Upload-Shedule your next Video should come soon. NICE.
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.
BEST video on algorithms i found yet, LOVE IT
Thank you for your effort...
Lovely demonstration
See you next year :D
Insertion Sort is basically the backwards version of Bubble Sort
green man pls hurry up bro
Now do pigeonhole
I love your videos so much
That graph visualization at the end was ABSOLUTE GENIUS!
I never forgot merge sort
What about RandomSort
its so good and unique ..but it could be best if you added 'Numbers' with the balls..however its a nice video
:)
All robots would get painful as heck if the n = 100
Remarkable!
wonderfull video. explained the log(n) i was always wondering about in terms of performance and scalability of a method.
Yes I was waiting for this. I really liked the previous parts so I want to see one about insertion. Thank you :)
Just thought of something. What if you use binary search to figure out where to insert the next element. But then, doing the insert will still take O(n) (n/2 on average) copies IF the list is an array, but if the list is a linked list, it would be constant time. Binary search is O(log n). Oh crap, you can’t do a binary search of a linked list though. Never mind.
great content as per usual ........more frequent posts & this would clearly be among the "top' channels of its kind.
Poor Bubble Sort.
first tym in 4 years I got the concept right love from Pakistan
The jobber of sorting competitions: bubble sort. You know you have a weak challenger when you have to reach for the weakest possible opponent to make the match seem fair.
é o vídeo mais lindo do mundooooo
Bogo sort next please!
What would make it a close game except for luck and two bogos?
This is awesome!
Recently youtube added the ability to change audio track to another language, I would love to help for dubbing in french
How about a video on Timsort, most likely quickest sorting algorithm of them all?
Great 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 :_)
The problem is that you don't have sound, to get it please, please go to scratch.mit.edu/projects/191308642/
Do radix sort.
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"
b.o.g.o.s.o.r.t
Perfect.
*DO. BOGO. SORT.*