Which Sorting Algorithm Should You Use? ;'Most Popular Sorting Algorithms..

 

In this video we're going to be looking at the most popular sorting algorithms and compare their performance based on different input sizes we're  first going to look at the Theoretical and see which ones perform the fastest but what I really want to do is to actually implement these in code and time them based on different input sizes and see which one is really Fastest before we jump into it I want to explain what this video is not this video is not an explanation of how these algorithms work there are already a ton of resources on that also we're going to be going over the time complexity of these algorithms in big o notation so if you know if you don't know big o notation that part might be a little confusing but I think other than that you should be okay and then after we do all the comparisons I'm going to give you guys my opinion on which algorithm you guys should be using so stick around for that so here we have a chart of the sorting algorithms I mentioned and their Respective time complexities from a worst case scenario average case and best case scenario and what I really want to focus on is this average case so we see that for bubble sort insertion sort and selection sort the average case is going to be n squared and for quick sort and merge Sort the average is going to be n log of n so quick sort and merge sort these are considered the quote-unquote fast sorting algorithms and then these top three up here are considered the slow algorithms and we're not going to worry about heap sort for this video and a couple interesting things here to mention are that we see that for bubble sort and insertion sort the best case scenario is actually big o of n whereas the best case scenario for the you know the quick algorithms are going to b n log of n so say your input list is already sorted well the way that these two first algorithms work is that uh basically they only have to go through the list one time in order to realize that it's already sorted the other interesting thing is for the worst case scenario for quicksort it's actually going to be big o of n squared so based on the order of the items in the list given to the quick  Sort or if you know how quick sort works depending on how the pivots are selected you could actually get a runtime of n squared and one other thing to mention here is that for the average case it's actually  impossible for a sorting algorithm to get faster than n log n there's an entire proof dedicated to that which I used to know very well but the main takeaway is that it's impossible for a list that's unsorted to get sorted faster than n log n alright so here's the game plan I Implemented each one of these sorting algorithms and put it in their own class and by implemented I mean I just copied it from geeks for geeks so how the code is going to work is here we create an array initially we're going to use a small array of size 10 we loop through that Array and for each element we just pick a random number that's either from 0 to the size of the array that way it'll be a pretty random array we might have duplicates in it but that's totally fine and then down here we have a variable called start time which we just set it to whatever the time is of the system using nanoseconds then we call the sort Method we let that run then we create another variable called end time and capture the system time at that time this gives us a pretty not an exact but a pretty good estimate of how long the algorithm took and then finally what I do is I just print out the difference so end time minus start time so I'm going to run each one of these five sorting algorithms we're going to use an input size of ten a thousand a hundred thousand and a million and I'm going to run each one a few times I'm going to take the average of it we're going to put it in a chart and then we're going to do some analysis one eternity later all right so I went ahead and ran everything and I made a little chart here so on the left side we have every single sorting algorithm and then each column is going to be the number of elements that I ran it against so if we look at something with a small list like 10 elements we actually see that the  quote unquote slow algorithms were actually faster than merge sort and Quicksort and this is due to the fact that these are actually really simple algorithms they're usually just double for loops whereas merge sort and quick sort there's just a little bit more going on there I know quick sort uses a little bit of recursion merge sort has uh more operations here so that additional overhead for merge sort and Quicksort takes longer than those actual extra comparisons that we're doing for these other three algorithms but once we get to a thousand elements this is where we really see the performance hits of using the slow algorithms we see that bubble sort is the slowest and by the way these are all in Nanoseconds so bubble sort is the slowest one here followed by selection sword and insertion sort and then we see a dip here with these other two algos and it really just gets amplified more once we get to a hundred thousand elements we see bubble sort here this took about 13 seconds selection store took three seconds insertion sort took about three quarters of a second and then merge sort and quicksort took just a fraction of a second and then finally for a million elements these three didn't even finish I had them running for a while but since these algorithms grow exponentially going from 100 000 to a million um I mean I don't even know how long it would have taken for these and then we see a merge store and quicksort still ran pretty quickly the interesting thing here is the quicksort actually performed a lot Better than merge sort despite them having the  same time complexity and that's just due to the nature of how the algorithm works so as we can see from these results unless you're using a very small data set like 10 elements or less merge sort and quicksort are going to be the way to go now how do you decide which one to use a lot of it is  based on preference but one thing to note is that quick sort is an unstable sorting method Whereas merge sort is a stable sorting method now what's the difference between the Two basically an unstable sorting method means that if you have two elements that are the same before the list is sorted once they're sorted they're not necessarily going to stay in that same order and for things like primitive types like strings and integers it doesn't really matter because say you have a five and another five like it doesn't really matter what order they're in because they're exactly the Same but say you're dealing with something like objects that could have different properties you might want to keep the integrity of the initial order of the list and that's something that merge sort does do so when you're coding what do you want to us well most languages will have a built-in sorting method and that's the one that you generally want to use so in java this would be arrays .sort and this is because this code has been written by a team of professionals it's been thoroughly Tested it's been thoroughly used it's been optimized so  you're going to want to go with whatever your language's built-in sorting algorithm is and the cool thing here is I'm using INTELLII and what you can do is you can Actually right click and go to the implementation of the IDK so if we go here we see that the sorting method so there I put a couple in here right so we have arrays. sort for an array of integers and then we have arrays. sort for an array of objects so for the integer if we right Click if we go to the implementation we see here that it's using what's called a dual pivot quick sort so dual pivot quick sort is really just a flavor of quick sort that's been optimized to run faster and if we go back here if you go to the sorting method of the objects we see that down here it's using what's called a comparable TIM sort and that's just another flavor of this other algorithm called TIM sort which is a stable sorting algorithm so with the objects it's using a stable sorting algorithm with the integers it's using an unstable one in that dual pivot quick Sort all right so there you have it those are comparisons of the five most popular sorting algorithms hopefully you guys got a lot of value out of the video if you did make sure you guys hit the like button don't forget to join the coupon coding discord server where you can talk to and connect with other Developers as always thank you guys so much  and keep on coding