Insertion Sort vs Bubble Sort + Some analysis
Vložit
- čas přidán 1. 08. 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.com/insertion-sort/
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
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 CZcams.
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.
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.
A new udiprod video on sorting! I love these videos.
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
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.
Thanks for including the "map" of comparisons. Watched the video several times during the years and every time finding something useful.
following channels you think are dead pays off
Finally udiprod make another video :D
I just want to thank you for making the best sorting algorithm videos I have ever seen!
Also, the analysis part is brilliant!
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!
I've learnt more from these little sorting videos than I did in about three lessons of Computer Science. Good work!
These sorting videos are by far my favorite videos I've ever seen
BEST video on algorithms i found yet, LOVE IT
I can't wait for Radix Sort (LSD)! That sort is my favorite.
I love how these videos could help do every day lives especially for 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
That graph visualization at the end was ABSOLUTE GENIUS!
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
"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.
Yes I was waiting for this. I really liked the previous parts so I want to see one about insertion. Thank you :)
this was LIFE CHANGING. NEVER have my eyes witnessed such beauty before this glorius day. thank you. for everything. 😘😘
moving.
jesus christ this is amazing! Every cs student SHOULD watch this video series, its so awesome!
I wish i could give two thumbs up, the explanation of the sorting time was superb
This is so relaxing and fun!
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 channel for sorting algo
Wow guys u put a lot of effort on ur vids i really appreciate that
I love how all the comments are so supportive and it makes the content even more wholesome
great content as per usual ........more frequent posts & this would clearly be among the "top' channels of its kind.
these videos made the boring sorting techniques interesting hats off.
These videos are amazing. Great content!
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.
Legend says, each year, udiprod will have a day off from work. In this day, he ... :))
Thank for turning lesson into cartoon for representing the work. The best explanation.
First!!!!
One of the best channels on CZcams!!!!
wonderfull video. explained the log(n) i was always wondering about in terms of performance and scalability of a method.
Glad to have a new video
This is awesome! These videos are going to carry me throug my algorithms course!
Yay a video!
See you next year!!!
finally a video worth my time
I love your videos so much
The brawl finally continues...
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 LOVE this videos, thank you!
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.
Could you do a video on BOGO sort vs some other sorting algorithm like gravity or insertion sort?
what an awesome explanation
Loved it! Great job!
Well done! big thumbs up
Lovely demonstration
This is perfection.
Could you please make videos on pointers and self referential structures?
Fantastic. Thanks. So this is about AI and computer efficiency. And can it be applied to commercial processes?
Woo Hoo! Finally another video
Can you make a video about selection sort ? The videos are amazing bro .
You're alive! You're alive!
Far better than anything Wikipedia would offer.
Thanks for the new vid!
May i suggest smoothsort? Or could you just explain it to me in the reply? Thanks.
This video should be in every programming 101 education.
Thank you for your effort...
hey, this is super helpful, thanks!
are bubble sort and insersion sort the same thing but one backwards?
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.
This would be an excellent introduction to big O notation
Great video!
Excellent little vid
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.
it is a really great video to understand algorithm
How about a video on Timsort, most likely quickest sorting algorithm of them all?
first tym in 4 years I got the concept right love from Pakistan
Can you try radix sort? I don't know how that would work with colors, though.
Number the colours
Super analysis
Insertion sort at the end was just like "so wtf do i do now"
Next, can you please do Insertion versus selection sort?
im oddly addicted to these
this is just an art
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)
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!
How does counting sort work?
See you next year :D
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)
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 You !
Can we have tim and intro sort
That animation at the end was so legit
and the shell sorting?
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.
HE LIVES!!!
What is really the difference between the two. Both involves comparing the neighbors and swapping
i had to watch this for homework!
Radix sort or counting sort?