[Music] hey guys and welcome to new video in this algorithms and data structures tutorial in this video we're going to talk about sorting and we're going to talk about different sorting algorithms there are and i'm going to show you some like different kind of examples of like how to work and i'm going to show you some some code examples as well like how we can implement those sorting algorithms and use them in cpus plus so first of all we need to like know what an inversion is when we're talking about sorting because like we use inversions to measure like how much and a list or like a vector array is unsorted so we can say that like it's an ordered pair of numbers if we see here like i comma j here for which that i has to be less than j but like the index index um i in the in the array has to be bigger than the element at index j in in the array as well so an example of an inversion list um down here is down here where we have this uh where we have this unsorted list here and then we can measure like how much this array here is unsorted by the numbers of inversions so we can see down here like inversion is like how many how many different uh like swaps we need to make until our list is sorted so we can see down here that we have like these kind of like um possibilities or like uh things that we have to swap so we have like one two three four five six seven eight nine nine inversions in this uh unsorted list here so we have to like do nine operations if we're using like just a standard just like a standard sorting algorithm that can only like remove one inversion um for every operation like we're also going to talk about some other uh sorting algorithms that can like in some cases it can like remove more inversions uh per operation so like in version is like how much and and list is unsorted um so we're going to use this like to measure like um which kind of sorting algorithm we should use and stuff like that but this is like how um how we how we know like how much our our list is unsorted and we can use this for for different kind of things so then we're going to talk about like sorting and and like as they're totally like the more inversions the list contains the more unsorted it is so like sorting is used to reduce the number of uh often inversions and ideally we will want like the inversions to be silver because then we can swap more elements and then can swap more elements to get our list or like are containing more um more sort so when we hit like inversions of zero we have like a totally sorted array so the average number of uh of inversions is is a list of indistinct integers is like is this formula down here which is like just kind of like uh the map for algorithms and data structures so like it's just like some formula that you just plotted the number here which is like the n distinct integers and where you just plug this in and you'll get the average number of of inversions in that list if you want uh if you want to know that and in case of like how many operations you need to do and to like choose which holding sorting algorithm you want because if you don't have like that many inversions in in your list that like it could be beneficial to choose um and and sorting is some sort of written over another and even though it has like a worse time complexity and it would still be better if we had like um only a few inversions in our list so if one operation can eliminate one inversion then the soaring algorithm must have a quadratic quadratic time complexity and we're going to see some sorting algorithms that has this quadratic time complexity where we have to like to to run through the whole array and then sort it and then like um do that first for some iterations until our our array is stored so we can also have some other sorting algorithms like say let's say like if more than one inversion can be removed in one operation then it is like it is possible to do better than quadratic and we're going to see some starting mechanisms to actually do it better than this time complexity here so first sorting algorithms we're going to talk about is is these like a quadratic um time complexity where we have this o n n square so it's like it's like not really that efficient like time wise um for our academics but it can be used for for some in some cases where we don't have that many elements or or for some of the cases where we don't have that many invasions and versions so the first algorithm here is the insertion sword which is like it places an unsword element at it attitude at a suitable place in each iteration so we like we go through our list here our list and then we just place or like insert an element into that list at a suitable place so in the end we will end up having a sorted array we can also have this like a selection sort here which just like selects the smallest element from the unsorted list in each iteration and then it places that element at the beginning of the unsorted list so after like a number of other iterations we just take all the like the smallest elements and then just like place that element at the beginning of the unsorted list so we're not really going to go more in depth with these two first distorting algorithms here if you want if you want to go more in depth and like you can you can go check them up or like uh drop a comment under if you want me to go more in depth but we in this video we're going to focus more about like bubble sword and some of the other sorghum algorithms that has has a better time complexity and it's like more used for for bigger arrays and data structures so we can also have this bubble store here which is like it compares that json elements and swap them if they're not in intended order so we're just going through the whole list again here with for example like two photos where we just like check the two adjacent um adjacent elements and if they're not in order we just swap those two elements and go to the like the next element in the list and check if those two new adjacent elements are are in intended order and if they're not we swap them or else we just keep them as as they so the bubble store here is just like as i said by mo but i'll just visualize it here so in the first in the first iteration here like or in the first example like iteration here we have these two adjacent adjacent spots here like our elements and then we can see that if if if five is is if five is bigger than one then we swap these two elements and we can see that we did it down here and then we go to the next spot so we look at these two adjacent elements here and if we need to swap those two elements because like five is bigger than four then we do that and then we go further to the next element here and we do the same here and again four five and so on and then we have done this we have we're done with our with our first step and we have to go through um our whole list again and do our our um bubble sort until i will have a totally sorted array so we also have some other sorting algorithms that are like more um time efficient and for in some situation and also if we're working with with larger um with larger arrays or like uh data sets so let's say we have like for example anybody that contains like 10 000 elements then if you have like a quadratic time complexity that will be like 10 000 um to the power of two like or ten thousand square so that will be a really uh huge number compared to if we only have this n log n time complexity here so like these are sorting algorithms uh that we're going to talk about now like they're more super suitable for for larger arrays and if we're only working with like a 10 20 100 um elements in our array like it doesn't really matter like what kind of sorting algorithm we're using if we're talking about like uh time complexity so the first starting algorithm here it's it's it's is merge sword um and it's like it's time it's kind of like the dividing concur like um programming and programming as we talked about in some of the previous videos and then we first we divide our our list and then we conquer our list so we get our elements um ordered and then we in the end we merge all all the all the elements again so the merge over here it divides the array into two halves until we reach a stage where we try to perform merge sort on a sub array with size m so we just like divide our array like for each iteration we divide them in half and then we take one more iteration and we divide the new two halves in two more halves so we can we will now have four halves and we keep on doing that until uh we have sub arrays um that we're trying to like perform merge sort on that only has a size one because then we only have one element in that array and then we can like sort that and because then it will be in sorted order and when we have done that we can like merge all the elements together again like all our sub arrays together again and then we will have um and then we will have a sorted array so another uh approach here or like a sorting algorithm is the heap sort um which is which uses a binary tree and a mat like for example the maxim you can also use the min heap but in this case here we're removing the largest element um from the root in our binary tree so the root in this case here will be like the largest element when we're talking about a max heap and then we keep defined like then we remove the largest element that's stored in an array and then we hemify the trees again so so it will now be ordered and the new largest element would would now be on top and we have like um heavified or order all our nodes in our binary tree and then we just keep like storing the largest element on on like some other like array and then in the end we will have an assorted array so the last example here of it like a sorting algorithm is the quick sort which is like kind of the most one of the most used ones and also the standard in cbs plus as i'm going to show you in some code example as well um where like the sorting algorithm in cbs plus like the building in the stl library uses quicksort as default and quicksort is like first of all we choose a pivot point um so we just choose like some point in our list it could be like the first element the mid element or last element in our list and then we divide um we divide our like list into two sub arrays according to whether the elements are less than or greater than the period so choose one one value in our list and then we go like through a list and and and check if and check if like those elements are bigger or or less than the pivot point that we chose and it and if they are we then divide them into two sub-arrays and so we have like one array that is less than our pivot point and one array that is that is like all the elements are higher than our period point and then those sub arrays then they are then sorted recursively which we're going to see um some examples on in code so remember here if we're just going to visualize like how how it works how it works and then we take here we first take like the middle here and we just like split our array into into two halves and then we again do the thing here where we split our array into two halves and until we only have like one element in our sub array and then we can't perform merge or anymore or like the merger anymore and over here we do the same thing here because we still have two elements here and we divide it down here so here in this um row here at this level here we have like all our elements stored like all our sub arrays only contains one element and then we can sort um sort those elements here again when we are merging our list together again so in this case here we can see that we're merging uh our sub arrays together again and it will now be at this list over here and then when we merge them together in the end here to the to the final list we then do this merge here where we're then merging the list so the elements will be ordered in the end when we have like the final uh the final sorted array down here so the quick start algorithm here is again as i told you if you first choose our pivot point in this case you will choose the last element of the of the list so we choose seven in this in this case here and go through the list here or array and then we check if if the if elements are less than or greater than our pivot point and this case here all the numbers here to the left are less than seven and all the then all the elements here on the right array um is greater than um greater than or equal to our pivot point and then we do the same here again um we do the same here again when we choose a new period point for our sub arrays and we didn't just do this recursively as i just told you and then in the end we'll just end up with our and with our sorted array here and we can just combine them all again so we now get one two five six 12 15 so then we will end up with an sorted array we can also use this like some some special case algorithm that is called a bucket sword and in some special cases we can actually like do better than than o n log n and this is like a very special case and and usually like you can only use it if this like um if these like this different kind of special cases occur um in our problem so because like then we can actually get uh get a sorting algorithm that that the time complexity is is linear which is like pretty good but it's not really that often that we can use the special case algorithm so we if we use this um bucket sword here we need like if if we have like some some array where we like sort positive engineers with a max value m then it's possible to solve the problem by like creating an m sized array and then the number is there read from one end to the other end like from the list so we go like from the from from from like the start to the to the end of the list and then we're reading the value x index x in m and then like m is incremented um incremented by one as and then like in the end when all the numbers have been read the array is the input output in accordance with the number of occurrences in the indexes and then after that that everything is done and we have like this special case here where we want to like sort the positive injuries that that has like it's this is like um especially phase up here like where we have like these positive integers with a max value of m so let's say we want to sort like some some values between like uh zero and one so if we have like floating point numbers then we can have like a time complexity of o of n which is then linear and and much better than like or like kind of better than the n log n here and definitely better than our quadratic time complexity so just to recap before we go into code and seeing some different kind of examples of of these soaring algorithms here we just want to like recap and just like get a recap and get an overview or like what we need to know before we can implement this in code so and and start with talking about these inversions here which just measures like how much our our array or like our list or some other kind of data structure is is um is sorted or unsorted and then we have these time different types of sorting algorithms with different time complexities where we have this quadratic and n log n and our linear here for the special case pocket story and there are different kind of approaches to like choosing the right sorting algorithm and it really depends on your problem for example as i talked about like if you have a really large um array that you need to perform some some sorting on like it's better to choose like the n log n um sorting algorithms here and then and then like the quadratic here because then it will just like end up with it with a really huge number and a real really bad time complexity and if you like only have like a couple of elements in your array like it's it's fine to just use this quadratic um sorting algorithms here which is also like kind of kind of like a bit easier to implement and also like work around with or if you have an array that is like uh only has a few i only have like only has like a few inversions then it's always like better to just use um some of the starting algorithms here that are quadratic time complexity compared to to some of the other um sorting algorithms i just wanted to show you guys uh this like sorting visualizer here made by clement another youtuber here where we can like have uh create an array here that we want to sort with these four different kind of soaring algorithms that we talked about in the slides here so if you just have this array this array here that we want to sort with like for example like the bubble sort we can see that it goes through all the lid like the whole list and then just like um swap the two elements if the if the less than or greater than um and then we just like stored the elements here from from the from the back here so we get the large largest element and the second largest element for the large gentleman and so on so we can see that if we have like a bigger array here and we want to use this bubble store which which is like quadratic time complexity and we want to sort it with bubble sort we can see that that is like really slow and and like it takes a lot of time to sort like even now we don't only like sorted four elements in our list so this is like not really the optimal um sorting algorithm for this type of like um data set or like our array here because like it's just too big and it takes too much time to sort our to sort out in this case here so if you just hit refresh here and try to do the same sorting with the quicksort algorithm here we can see that this goes much faster than the bubble sort algorithm and this will be like a more appropriate uh chose a choice of sorting algorithm uh compared to the bubble store if you had like this this type of um this size off array here and also because like when we create a new way here just like get randomized and all like a lot of the values are unsorted so we have a lot of inversions so we can also use like this heap sword and merge sort here and we can see like we can just go in here and see like how it works so here we just divide all of our um our list into like into smaller sub arrays and then we do this merge sort here um and then merge all the elements together in the end so it's a pretty nice um visualizer here so like see how all the all the like the soldering algorithms are like some of the most important sorting algorithms we have so let's jump into the code here and see like how to implement these these sorting out garments here in c plus and see some examples of it so we're gonna turn it into the blind text here and we're going to do some different kind of examples um with the sorting algorithms that i just showed you like or we went over in the slides so the first one here is the bubble sword algorithm here where we have these two nested for loops so like that the method behind the the bubble sort here is that we look at the two adjacent elements in the in the array so first of all we just have this for loop here that is like running through all the adjacent elements in our array and then we check if the if the if the element here is greater than the adjacent element in the list and if it is uh we swap we swap those two elements in the list and if they're not we just keep them and we just go to the next adjacent element so in this case here we are we are sorting in ascending order and if we want to like um sort it in descending order we need to change this um this this greater than here to less than and then we will like um sort our our array in and descending order so like and then we just continue doing this until our our array is swapped here with the without the for loop here so we've go down here and see like how it works we have have to create this array here with some random numbers that is unsorted so we have to this unsword array here and we perform our bubble sort down here and then we just print out the array here with this for loop so if i control b here it will print out it will print out the original array before we sort it and then we will like uh it will print out the sorted array in ascending order uh with our bubble sort algorithm here so we can see that we have sorted our our numbers or like our elements here in our array and we get like one two three four five six seven eight so this this like a bubble sword evidence works fine and also with with um with only a few number of elements in arnold ray so next sorting algorithm i want to show you is is the merge sort algorithm where we like uh divide our list into like uh smaller like sub arrays from the mid so if i just go in here to the header file where i've implemented the merge merge store here we just need to like first we have this function here that just merges two sub arrays so when we have divided all or or array into like smaller sub arrays until it only stores like each celery only stores like one element then we need to merge all this all the like the two sub arrays again onto we will end up with with um with our stored array so i won't go like through uh the whole code here with with the merge and but it's like where it's like we just take like and array here and we take the first element middle element and last element and within them we just merge our our two sub arrays together so we will end up with um we just with a sorted um with a sorted array so remember function down here is um is like what does like the the sorting and it calls like these recursive functions down here where we like um have this merge sort here that we call twice and then the merge here where we merge the sorted sub arrays that we have done with the merge sort here so first of all we just check if if if if the first is is less than the last because the first year is the first index in the array and the last year is the last index so as long as we're not in the end of the array here we just um we just um like we if we if it don't like this is the same as saying that um like the size of our sub array is is bigger than one because if it was equal to one we will then like stop this um stop this merge sort here so then we need to find the midpoint here of our array and our sub arrays when we when we call this recursively and it is like the first plus the last minute is first and then we divided by two because we need to get um the middle of our array and then we call the function here again like our recursive function sort here again with the array and with the first and then um then the last element here in our first sub array will be the mid uh here and then the first point here in our second sub array would be the first point and the last will then be the last because then we just divide our our array on the middle and we have a left sub array and then we have a right sub array from that midpoint um that we calculated here and then we just do the same again until until like each element in the sub arrays are only one and then in the end here when when that when that is done we then merge all our sub arrays so we'll get a sorted sub array with this function up here so like this is how we implement like um a merge sort and we just like divide uh divide our um divide our array into smaller sub arrays and then we sort those sub arrays and then we can merge them together again on so we'll get an assorted list so if we see that this um this um merge sword algorithm here in code we just do the same with the numbers here the the array up here and we call the merge sword here and if we ctrl b here again we can see that the original array before sorting was the same as before and then when we perform our merge store here on our array we'll get this sorted right here in ascending order so it works fine as with the bubble sword um so yeah that's how we can like use merged sword into blue cbs plus so the last starting algorithm here i'm going to show you um how implemented is the quicksort algorithm here and if you're just going to hit the file for it for the quick sort here we need a function here to partition our array a basis on the pivot element that we choose so we also have this like quick sort function down here and where again we check if the like if the last like if the first element is less than the highest element and we haven't been through the whole um like the whole whole list and then we have this um pivot point here um that is equal to the partition of the array and then we pass it the first index and the last index and then our partition function here is just like it partitions the array bases on the pivot point in this case here we just choose we just choose the pivot point as the as like the last element in our array that we passed to the partition function here and then we put all the elements that are smaller than the pivot point on the left and all the all the elements that are greater than the pivot point on the right uh of the period so we have a folder period we just run through all the elements in the list and we check if if if the element here is less than the period period and if it is we just increment i here because we need i in case of um in case of like we want the pivot point like to the right of it and then we swap the elements here on the array at position i and j because then we know that that that the element here in our array is less than our pivot point that we chose and the peripheral objects is the highest element or like the last element in in our array that we passed to the position function and then after that we just swap the elements here at array at the i plus one um index uh with the like with the our period point here because then we increment the i here if the if the like if this um element here is less than the pirate point them in current i here and then it determine determines like which element we need to swap here with our pivot point up here in on in our array and then we just return this index here from our partition and then this index here is what we set equal to our pi down here and then the pi here like or our petition will be the next um will like be the next high here or like the next like the index like the last index here when we call a quick quick start here again recursively and also like um when we need to like sort the elements on the right of the viewpoint so when we call these functions here again and recursively we can see that when we do this with the partition here at the highest element then we sort the elements on the left of the pivot point because this will be the highest element or like the last element which will be like um the midpoint and then the lowest element here and then here again we have like the midpoint or like all the values from the right of the pivot point of joe's up to like um the last index in on in our array and then we just keep calling this recursively until we have a sorted array so we go down in here again to our main function uh we can now perform quick sort here on the numbers array we have created up here as as in the last example as well and if we just print this out with hitting ctrl b we can see that we again um sort sort the array in ascending order and we store the original array here so we'll get these numbers out down here and we have now sorted our our array with our quicksort function so like th these are three three um three different types of sorting algorithms that we can implement um in cbs plus but there's also some built-in functions that you're probably going to use like a lot more time like a lot more times but it's always good to know like what's going on behind and behind all the building functions in cbos plus and also like what it does and like why and how it does it um so if we want to use this building function from the stl library and i'll just go down here and we create a vector here with a bit more numbers here that we want to sort and then we can use this sort a built-in sort function here from the standard library or stl library and in cbos plus and we can call this begin which is the first element of our numbers 2 vector here and then we will sort it until the end here with this end function here that we call on the vector as well so if we hit control b here um again we will now sort this vector up here and we can see that our vector is sorted with stl function and the stl function uses quick sort as the default sorting algorithm and then we can see down here that it is um it is sorting it in ascending order as default as well and if we wanted to to like sort in a descending order we could use this r um before like our begin and r in front of the end here because then it will do in reverse so so if you do this it will do like the sorting in reverse and then it will um sort it in in descending order if you want to do that we can also parse this another parameter here which could be a lambda function so we can define on ourself and define ourselves how we want to sort our like data structure or our vector so if you want to like um sort in like some alphabetic order or if we had like some pixel values or some other like coordinates we wanted to sort in some in some way that we chose ourselves like then we can create a lambda function and pass it to the sort function here and then it can sort it in that way as well so like it's it's it's pretty nice like we we can just use this sword function here but we also need to know like what's going on behind the scenes and like also like how to implement other uh data like like uh outsourcing algorithms so that's pretty much it for this video guys and we've been over like the different kind of sorting algorithms how they work and and what a different kind of situations like some of the sorting algorithms are better than others so thank you guys for watching this video and remember to hit the subscribe button and notification on the video and also like this video if you like the content and you want more of it in the future i'm currently also doing this a computer vision tutorial um with opencv and an osteophysical intelligence tutorial so if you're interested in one of those i'll link to one of them up here and you're going to go check that out if you want to or else i'll just see in the next video guys bye for now [Music] [Music]