Transcript for:
Searching and Sorting Algorithms Overview

welcome to part three of topic four of the IB computer science curriculum in this video I'm specifically going to focus on searching and sorting and for each searching algorithm as well as sorting algorithm I'm going to give an explanation code and maybe take a look at some sample IB questions furthermore I'm going to compare both of the searching methods searching algorithms rather and both of the Sorting algorithms this will be followed by a quick Channel update let's get started before we actually get into linear search our first search algorithm I want to talk about what exactly you need to know for the IB exam so one thing you do need to know is you need to know how to explain how all four algorithms work so how linear and binary search work and how bubble sort and selection sort work and perhaps the most common question or type of question that's linked to this topic is writing a text based description of how any one of these algorithms work now next there's a lot of confusion as to whether you actually need to be able to write code in pseudo code for these algorithms and what I will say is that at some point I have seen questions involving actually writing IB pseudo code for these algorithms on past paper once both slcl and HL however I would say that it's extremely rare on the SL exam and if it does exist it's more common on the HL exam so if you don't have the time to learn how to code all four of these exams I would at least focus on being able to code a linear search which is by far the most common uh sorting and searching based code question on the exam however if you are doing HL I would recommend that you know how to code all these all of these algorithms now next you need to know about when you can use binary search hint you can only use it on sorted arrays and we'll go into that more uh in detail and finally you need to be able to compare the linear and binary search and bubble sort and selection sort knowing some of the similarities and differences between both of them and again we'll also go through all of this in this video anyways let's get started now whenever we're searching for something what that basically means is that we're going to look into an array or a list of numbers to find a particular value and we're looking for either the index of that particular value or we want to go through and then find that value and complete some operation on it but a search means we just want to find something and generally the IB exam we're going to be looking in an array so a linear search is the simplest type of the two searches and I'll just illustrate that by going through an example let's say that we want to find some Target value 51 the target ter Target value just refers to what we're looking for in linear search we're literally going to go through the array one by one to find our Target value so we'll start at 31 check is 51 uh equal to 31 1 no keep going is 54 equal to 31 no keep going and we just keep going to each subsequent element in the array until we find what we want here we see that this is equal to the Target value and so we're basically done and what would probably end up doing what we probably end up outputting in any code would be the index where we found to match which in this case would just be four and that's a linear search we're literally just going to go through every element one by one from beginning to end until we find what we're looking for now when we're actually writing code for this we may stop when we found a match we may not stop it depends and honestly the result is going to be the same it doesn't really matter so now that we've seen how a linear search works let's go ahead and see how we can actually code this using IB pseudo code now we've already entered nums in a pseudo code and what we're going to do is we're going to set our Target Target equal to 51 like in our previous example we're also going to create something called a flag which you may or may not have come across and that's just going to be a Boolean variable that allows us to keep track of whether we've actually found the Target in the array or not so we're going to say found equals false and then we can say loop I from 0o to nums do length minus one and we can say if nums I is equal to Target so going through the entirety of the array from zero to the last index if nums equals Target uh then which I guess it's got to be one equals in pseudo code um output we can just output a message Target found at um I and then we can change our flag we can say found equals false then we can end that if statement we can do end if and end Loop then we can also well what we also want to do is create an if statement to handle what happens if we never found the target value in the array so you can say if found uh equals false uh then just output a message and just say uh Target not found in Array and end if and that's about it so as you can see the linear search is fairly straightforward just go through the array check whether each of the elements is equal to the Target and if so actually this has got to be F this is actually got to be true if so I'll put a message at the index where it was found and then change found to true and if not then we'll output a message if we go through the entirety of the array and found is never changed if found remains false okay now let's talk about the binary search the objective of the binary search is the same which is to find some Target value however there are two important differences first we can only do a binary search on an array that has been sorted either in ascending or descending order for example this array nums is sorted in ascending order with the smallest number 23 being at index zero and the largest number 67 being the last uh the last element in the array at index 7 so I mean this has eight elements so first index zero last index is seven and the second difference is just the way in which we approach the searching BAS basically we split the array in half each time until we find our Target element so let's say that in this array we want to use a binary search to check if if 61 is in the array and if so at what index so let's say that the index is 61 the first thing we need to do is we need to find an element at the center of the array now there are two candidates for this it could either be 35 or 51 doesn't really matter which one it is but we'll just start with 35 now we're gonna basically consider two things here first we're going to check whether the target is equal to 35 so is 61 equal to 35 it's obviously not so what we're going to do is we're going to check whether 61 is greater than or less than 35 now 61 is greater than 35 so we're going to go ahead and F focus on the portion of the array that is greater than 35 so that's this portion right here then we're going to repeat the same process we're going to choose an element at the center of the array again there's two candidates here it could be either 54 or 61 for argument sake let's just choose 54 now we're going to check is 54 equal to 61 uh it's not but is 54 well is 61 greater than or less than 54 uh 61 is greater than 54 so now we're going to focus on this port on the portion of the array that's greater than 54 which is this portion right here now right here we have two possibilities 61 or 67 um we're generally going to choose the lower of the two and I'll go into why that is in a second so we end up at 61 we check is 61 equal to 54 it is or 61 is equal to six is uh equal to is equal to 61 so we find a we find a match and we can output the index now as to why we chose the lower element here I mean honestly it doesn't really matter we would have ended up um finding 61 or finding the index of 61 at the end but generally when we start out with this binary search and we're looking at the first index and the uh the last index the way we can find the element in middle of those is we can add them up and divide them by two or divide them by two using the div operator so we could do 7 + 0 div 2 which is going to equal three so we would start at index 3 right here then when we move up to the portion that's greater than 35 we had we we we were at index uh 4 and then index 7 those were like the upper and lower bounds or the lower and upper bounds of that new portion of the array we were looking at so in that case we could just do uh 4 + 7 div 2 and then we would end up um so it's going to be 11 divided by uh div 2 then we just end up with index 5 which was this one right here and then we moved to the next uh portion of the array which was like the purple portion and that was at index 6 and index 7 and then we would do uh index we do 6 Plus 7 uh div 2 which is 13 div2 which is going to equal 6 so that means that we would go to this element right here so basically what I wanted to do in this example is illustrate just how we can do this process just by eyeballing it and then also explain the math behind it because that'll be useful when we get into actually coding now let's go ahead and look at another example so right here there are two important differences between this example and the previous example first we're going to have a different Target we're going to say our Target equals 23 and then this array also has an odd number of elements instead of an even number of elements so the previous array had eight elements this one has seven elements so our first element is going to be at zero and our second element is going to be at uh six so I'm just going to go through the process without using mathematics what's the middle pretty clear 35 is at the middle now compared to 35 uh so 23 is not equal to 35 23 is actually just less than 35 so we're going to look at these at the uh at this portion of the array and we'll go to the middle 29 uh 29 is so 23 is actually less than 29 23 is less than 29 so then we're going to go to our new portion right here and there's only one element and that's equal to 23 so we have a match now whenever we go through this binary search process we are going to get to a point where there is only one element either one or two elements left in our set and basically if you get to a point where so mean right here we got to the point where there were only two elements left and we found a match so we just stopped right here however if you get to the point where we only have like one element left we're looking at and it's not equal to the Target then we just know that that value is not in the binary search so we can have situations where um an element is not in the array that we're sorry the element is not in the array that we're analyzing for some reason I said that is not equal to the binary search I meant or it's not in the binary search I mean that the target is not in the array that we performing performing the binary search on now let's look at a slightly uh longer example and I'm going to look at this just by doing the binary search and then I'm also going to uh do the math so all right right here we've got um 1 2 3 4 five 6 7 8 9 10 11 elements I guess that means this is going to be zero and this is going to be um this is just going to make that blue this is going to be zero this is going to be 10 so let's see 0o 1 2 3 4 5 6 7 8 9 10 always helps to make sure now let's say that our Target is 29 okay so I just want to look at what's in the middle um so I think that's 61 just because we have five elements on one side and five elements on the other um so that's going to be at index uh I guess that's index five again we could have also found that with 10 + 0 div 2 so 10 div 2 equal 5 so now I'm going to compare 29 to 61 uh 29 is obviously less than 61 so we're going to focus on on this part right here and look for what's in the middle and that's going to be 31 again we could have found that by doing um uh like what is it 4 + 0 CU it's four 4 + 0 uh div 2 um which is just going to equal two this is index two now 29 is uh is less than 31 so we're going to focus on the portion less than 31 which is this right here now now we can choose either of these two elements again we're probably going to choose a lower CU we're going to have 0 + 1 div 2 which is just going to be equal to uh that's probably going to be equal to zero so we'll be right here at 23 and then we'll check is 29 less than or equal to or less than or greater than 23 and 29 is greater so that was our middle but now we're going to focus on a portion right here which only has one element and we can just check is 29 greater than or equal to 23 or is it equal to sorry is great is 29 greater than or less than 29 or is just equal to 29 and it's equal to 29 so that means we're good we have our match at index one so now that we've seen how the binary search works and um we've also seen the math behind the binary search let's see how we could approach this from uh the stand point of writing code because there may AR a circumstance there have in past papers you've actually had to code a binary search or at the very least describe a binary search with with a c with an amount of detail that basically requires that you know how to code it anyways okay so let's see how we can approach this Pro this process programmatically so we can understand like how we would actually work through a binary search using Code before writing the code itself now the first thing we would want to do is create a variable called Target and this would just be to hold the value that we're looking for or the value that we're searching for using the binary search method next we would want to create another variable called Low that's going to be at the beginning of the array and a variable High that's going to be at the uh end of the array and then we want to create a variable mid now mid is going to be low so we'll say mid equals low low plus High div 2 following the mathematical formula we went over in the previous examples so at least when we start out mid is going to be assigned to 35 because high is at six and low is at zero and that would make mid three now this is just where we're starting out but what we want to do next is is we want to compare Target to Mid so we're going to say if Target is so we're going to compare T we're going to say if Target is less than mid then we're going to move High to um Mid minus one so that means that now high is going to be equal to Mid minus one so this will be our new high on the other hand if Target is greater than mid so we have a situation where Target is um actually greater than mid that means that we're going to be focused on this portion whereas we focused on this portion when the target was less than mid so what we're going to do now is we're going to say that low is going to be equal to uh mid Plus one so we're basically using a low and high to define the portions the array that we're going to analyze in each step of course before we check before we to make any of these changes for whether Target is less than mid or greater than mid we would obviously check whether the target is equal to Mid in that case if the target is equal to Mid then we would just return mid right then that means our answer is just going to be mid our index is just going to be whatever is at Mid that's kind of our goal now once we've changed our high and our low then we would calculate a new MID so for example if Target is less than mid then our um then we create we calculate a new MID and we check I mean we basically use the same formula we had before which is uh mid equals low plus high but actually be using the old low and the new high so I'll just go ahead and I'll erase low so it actually be the the old low and the new high so it be low plus High uh div 2 and that would just make I mean basically in that case then we'd have mid right here and if Target was greater than mid then we would have mid is going to be equal to um the I'll go ahead and write that here the new l low so it' be uh low plus the old high the new low plus the old high divided by two or div two and that give us a new MID right here and we're basically going to keep um carrying out this process until low is equal to high so let's say that our Target for example is 61 actually I mean if our Target was 61 then we'd have a mid and we' compare our Target to Mid and Target be equal to Mid so we'd be done actually so if if targets ever equal to Mid then we would just stop our program and if not then we would keep continuing until the condition where low is equal to high because that means that we're basically going to be on a single element like our it means our portion has been reduced down to a single element which might be for example 67 uh if that was our Target so basically we're going to beut we're going to be doing this whole process so this process right here checking whether Target is less than mid greater than mid and equal to Mid and then subsequently changing our lows and highs while low is less than or equal to high once that condition is false then we stop moving around low high and mid and just doing all this because we've either we've either gotten to the point where we found a match um or um we've gotten to the point where we've settled on one last element and we've and maybe we haven't found something we've either found something or we haven't by the time this condition ends up being false and our Loop would stop so now having an understanding of how a binary search would work programmatically let's go ahead and write the code itself Okay so we've already gone ahead and we've created our nums array which comes straight from our example right here and what we want want to do as well well we defined our Target variable as well and now what we want to do is Define low and high and low is going to be equal to zero so basically the first index and high is going to be equal to nums do length minus one which is going to be our last index and then we're going to proceed to create our Loop which is going to be Loop while low is less than or equal to High um then go ahead and do whatever it is to do and here we're going to start with mid being equal to uh low plus High div 2 so we'll just have low plus High uh div 2 and we're basically going to have another condition let going to say that if if nums uh mid is equal to our Target or I guess in C we're just using one equal sign is equal to Target uh then go ahead and we can just output uh well we want to Output the index which we found it so we can just go ahead and output mid now I'm also going to create a flag so I'm going to say found equals false and we're only going to change this if the value has actually been found in the array so right here we can just say output mid so just print that out and then we can say false or so found equals true now this is something we're going to check in each iteration every time that we change low and high but to actually make changes in low and high we're going to have another if block and By changes in low and high I mean changing based on how the target compares to our mid value here and then subsequently when we when we move around our mid based on what is an array so we've got if nums mid equals Target and we're also going to we're going to close up this if block and then we're going to have um if if nums mid rather I would say if Target is greater than nums mid then so this is going to be the situation where the target is somewhere in here it's greater than the mid uh then we're going to say low is going to be equal to Mid + one so right here and we're going to say well so this is going to be a targets greater than nums mid um but we're also going to have an else block here and the else block is going to be if Target is less than nums mid um and we can do that because the case where they're equal to each other has already been taken care of so if we get to this block and uh the target is not greater than nums mid then it must be less so here we'll say else um High uh sorry rather high is going to be equal to Mid minus one which is going to be uh this situation right here basically where the target is less than mid so we've got that and then we can end this if statement and we can end our Loop and now we can deal with the situation which found uh which just basically the target was never found and we can just say um so if not if found equals false uh I'm terrible at typing then we can just return a output uh Target not found and that's basically the binary search what I want to do now is take a look at a practice question specifically connected to binary search now we're not going to look at a lineary a linear search question because frankly all the linear search questions are basically the code that we wrote but the most common binary search question looks like this outline the steps involving performing a binary search on an array of ascending numbers or it could be descending numbers probably the best answer here is in a numbered fashion and it basically follows the algorithm that we just wrote with one exception so right here it says calculate mid if array mid is the search value and else do basically the things we talked about in in the code and repeats repeat steps 1 2 and three until found until found is the difference between what we wrote basically we had a while loop that says continue um continue while low is less than or equal to high so basically it's going to stop when that condition isn't true so when low is neither less than or equal to or well when no is either sorry when low is neither less than or equal to high but here particularly if we're looking at a problem where we're going to assume that the target value exists in the array we can just repeat steps 1 2 and three or we can just repeat our algorithm until we found the target value and that could also go with a while condition so we could just say Loop uh while uh Target is not equal to uh mid or something like that depending on the nature of the question um and the and the array that we're working with so I wanted to show you this question because it's a very common binary search question and I but I also wanted to highlight another possibility when writing code if you have to beyond all of that this is this is undoubtedly the best way to answer this question 1 2 3 4 don't write a huge paragraph make everything super clear now moving on the last thing I want to look at with regards to searching is a comparison between linear search and binary search so we can start with some pretty simple points of comparison the first is the search Direction so linear search is sequential meaning that we're checking um an array one by one to see whether their values there and binary search effectively divides the arrays into half the prerequisites to binary search are that the array must be sorted but there really no prerequisites to linear search and practically a linear search is best for small arrays or unsorted data and the binary search is ideal for large arrays and sorted data now to see why we want to take a look at the number of comparisons that both will make in the best and worst case scenario we're going to create an array um we'll just make it ordered so we can work with both binary and linear search let's say 1 2 5 9 uh 11 13 15 uh 17 so we've got 11 elements in this particular sorry eight elements in this array now the best case scenario for a linear search is one comparison by comparison I'm talking about checking whether the target is less than greater than or equal to a specific value now this is important because every comparison takes up a certain amount of memory and processing power now the best case scenario for a linear search is that the value we're looking for is at the zero index so we only need to make one comparison and then we found uh the index of our Target value now the um the best case scenario for a binary search is when our Target value is the middle so for example if our Target value is N9 in this array that would be the best case scenario for the binary search because that would be the first um value we look at and we'd only need to make one comparison now the worst case scenario is is where in a linear search we have a value all the way at the end of the array right here because that means that we would have need to check all the values in the array um including the last one and so we'd have n comparisons where n is the length of the array so that means that in this particular case because we have eight elements we'd have to make eight comparisons and that would be our worst case scenario however if we go back to example of our binary search our worst case scenario looks a little different it's going to be log 2 of n where n is the size of our um array so it means to be log 28 which just equals three or three comparisons now let's say that we're looking for a value like two first we would start the mid we would see that two is less than n uh so then we would actually end up at uh I guess we'd end up at the mid which would not be the worst case scenario probably a better example might actually be even um one if we were looking for one we'd end up with the mid um and then our and then we look right here and our next value would be right here and then finally we'd end up at one and that's basically our worst case scenario for an array with eight elements and and it's less than and the worst case scenario is actually better with the binary search than for linear search now there's one caveat to that if we're talking about efficiency yes there are fewer comparisons in the binary search but we also do need to sort an array we we need to make sure that we have a sorted array and sorting by itself takes up a bunch of memory and processing power so unless our array the array we're looking at is already sorted uh binary search may not necessarily be more efficient than a linear search but we definitely do need to make so if you have a scenario where we do have a sort array then a binary search is definitely going to be uh more efficient than a linear search all things being equal anyways that's linear search versus binary search let's move on to sorting so the bubble sort is going to be the first sorting algorith algorithm that we're going to look at now in general sorting algorithms are meant to take an array and sort it in ascending or descending order so let's see how the bubble sort can do that so the first thing we're going to do is we're going to start with the array and we're going to start with 31 and 54 so 31 is less than 54 so we're not really going to do anything basically going to compare each element to the element after it and if the element after it is less than it is then we're going to swap them otherwise we're not so you've got 31 and 54 now we're going to compare 54 and 67 but 54 is less than 67 so we're still good now we're going to compare 67 with 29 and 29 is less than 67 so we're actually going to go ahead and we're going to swap them so we'll erase this and then we'll have 29 and 67 now we're at index 3 so after 6 after 67 we'll be 51 and 51 is actually less than 67 so so basically 67 moved over here so 67 or 51 is less than 67 so we're actually going to swap those so this will become 51 and then we'll have 67 so now 67 is actually at index 4 so now we're going to compare 67 to the next number which is uh 61 right here and 61 is less than 67 so we're going to go ahead and we're going to swap them and so we have 61 and 67 now the next element is going to be 23 um because we swapped this we swapped 61 67 so 2 23 is less than 67 so we're going to swap them again so we're going to have uh 23 and then 67 and finally we have we just have 35 left and 35 is still less than 67 so we're going to swap those and we're going to have 35 and 61 sorry 67 so as you can see higher values bubble to the end of the array now one thing you might notice is that this array is still not sorted we're going to have we need to go we need to have multiple passes to go through the array until we can actually sort it and we tend to run this array for the number elements there are in the array itself so now that we've done that let's go ahead and let's see again what we're going to do so we got 31 and 54 all is good but uh 29 is less than 54 so we need to swap those so we're going to have 2031 29 and 54 and now 54 is greater than than 51 so we're going to have 51 and 54 and 61 is actually greater than 54 so we'll just stick right there um but 23 is less than 61 so we're going to have to swap those so we have 23 and 61 and now we've got uh 61 being less than 35 or 61 being greater than 35 so we're going to swap those as well so we're going to have 35 uh 61 and then 67 and so you can kind of see how things are slowly starting to fall in order but let's keep going so we got 31 and 29 29 is less than 31 so we're going to swap those so we got 29 and 31 and 31 is less than 51 so we're not going to do anything 51 is less than 54 so we're not going to do anything uh 54 is less than or is greater than 23 so we are going to swap them so we're going to have 23 and 54 and 54 is greater than 35 so we're going to have to swap those as well so we're going to have 35 and 54 and then 61 and 67 and there's no swapping there but let's keep going 29 and 31 are good 31 and 51 are good but um 20 51 is greater than 23 so we need to swap those so 23 and then 51 and then 35 but actually 35 is less than 51 so we need to swap those 51 and then everything else is pretty much sorted and so we're just going to repeat the process again 29 and 31 are good but um 23 is less than 31 31 is greater than 23 so we're going to have 29 uh 23 31 and 35 and we're pretty much not going to swap anything else because the rest of the array is in order but we're not done yet um so we've got 29 and 23 which we can swap so we're going to end up with 23 29 31 35 uh 51 54 uh 6 1 and 67 and that's basically how a binary search works um each time we're going through we're comparing one number to the next and if the next number is less than our current number then we're going to swap them now this is going to produce an ascending um an ascending order if we wanted if you wanted a descending order we would just do the reverse so we'd compare the number next to it and if the number next to it is greater than the current number then we would swap those rather than less than that's basically how a bubble sort works so now what I want to do is focus on how we can take a bubble sort and write code to execute this algorithm so if you look back at the process that we just went over basically we had higher values bubble to the top by the top I mean the end of the array so first we had 67 right here and then 61 and then 54 and then 51 and then 35 and 31 so basically it took us 1 2 3 4 five six times to get this done and in this array there are let's see what is that there are eight elements so we kind of got lucky in the fact that these last two arrays ended up or these last two values ended up already being in ascending order but that's not a guarantee so when we are doing sorting we're basically going to have to do this uh the number of times we basically have to do this eight times or the number of times that's equivalent to the number of elements we have in an array so if you think about a loop we'd have to do we'd have to go from 0 to n minus one times right so from the first index until the last index so basically again in this situation we'd be start we'd be going from here to the end and we'd be going through this process the number of times that's the number of times equivalent to the number of elements in Array so 0 to n minus one but each time we're going to kind of do something different right so if we go back to this process um right here once we basically so the first time around we Traverse the array from here to here okay I mean that's all that was necessary we didn't have to go through the end because we were just going to swap values with whatever it was was at the end so we had to check what was at the end but we didn't actually have to go to the end go to the last index then we just have to go from here to here and then from here to here and here to here and here to here and so forth okay so basically to recap we're going through this array uh n minus one times okay right here we didn't have to go we didn't really go through n minus one times but in general that's what would take to get to the end of the bubble store now each time we're going from we're going to a different index so the portion of the array that we're covering each time gets smaller and smaller so here we went from 0o to index uh six um because there's eight elements 0 to index 5 0 to index 4 0 to index 3 0 to index 2 um 0 to one and then eventually we just would have had zero right so recovering a smaller recovering an amount or a portion of the array that's getting reduced by one element each time and if we turn this into a formula we can say that we're going to go from zero right here 0 to nus1 - one right and then 0 to nus1 - 2 and then n minus one - 3 uh n -1 -4 n -1 - 5 n -1 - 6 and we're actually I mean there's there's no point in getting to zero so we're basically going to do this right and I want you guys to keep this pattern in mind because now when we go to write code we're going to take this apply it in a loop structure now basically each time we go through the loop um so each time we go from value to Value which is this one right here like the red so this one's controlling the number of times that we go through the array and this green is controlling each element that we access whenever we go through the array itself so that's controlling this movement from 31 to 54 29 to 51 to 61 23 Etc that's what we're talking about with this process right here and each time we do that we're going to have some code to swap the element next to with the one next to it if the um if the relevant conditions apply so if it's less than or greater than depending on whether it's ascending or descending so now kind of having some understanding of how the bubble sort Works in a programmatic sense let's go ahead and actually write the code Okay so we've already filled in our array right here from our example now the first thing that I want to do is I want to create a Loop for basically this process in which we are iterating um so basically to control the process in which we're going from um from zero so basically from this array all the way down to this array so the process that controls how many times we're actually going to go through the array and what we're going to do for that is we're just going to say uh loop I from 0 to nus1 to n minus one and N is going to be equal to nums we're going to Define that nums do length minus or nums out length so this first Loop is going to actually I need to say loop I yeah that's actually good this first Loop is going to be corresponding to the red it's going to control the number of times we're actually going to go through the array and then inside we're going to have another loop for each um for basically each time so it's going so basically basically for every time that we pass through the array we're going to be passing through a different component and that's marked by the green which we just went over and we explained um our algorithm so that corresponds to this right here so basically what we're going to have is we're going to say loop loop J uh loop J from uh zero to uh n minus1 minus I and that I is representing this value right here so that J is basically going to allow us to um iterate iterate within the component that does not include the maximum or the maximums that we've calculated and that are circled in Red so now that we've written our two Loops what we're going to do here is we're actually going to do the swapping so remember when we want an array that's in ascending order we're going to take the uh current element and if it's greater than the element next to it then we're going to swap it with that one and we're going to keep repeating that process throughout uh the portion that isn't doesn't include the current maximum or maximums so for example as J is going through each time we're going to check whether the current element is uh is greater than the element next to it and if it is we're going to swap them so to illustrate that process we can say if nums of J is greater than nums of J + 1 so the element uh just above it then temp is going to be equal to nums J the uh lower number uh nums J is going to be equal to uh nums or sorry temp is going nums J is going to be the higher number nums J is going to be equal to J + 1 which is a lower number and then we're going to have nums uh J + 1 is equal to Temp and this is look going to allow us to swap those two values um as part of the the swapping process that J controls so then we can just do end if and end Loop for the first uh loop and then end Loop for the second outside Loop and that about covers it for the bubble sort now that we've had a chance to look at the bubble sort let's get started with the selection sort so what we're going to do first is well we want to we want to sort this aray into in ascending order so what I basically want to do is I'm going to start by finding the minimum value in this whole array now it looks like the minimum value in this whole array is 23 so I'm going to swap that with the first element with the element at index zero I'm going to end up with 23 uh 54 67 29 uh 51 61 and 31 CU 31 was index0 and then 35 so that was index zero now what I'm going to do is I'm going to look for the minimum between index one and the end of the array so if you look we have 23 and then if you look at the minimum um it looks like the minimum value from index one so from index one until the end of the array is going to be uh 29 so we're going to swap 29 with index one and we're going to have 29 67 uh 54 51 61 31 and then 35 and now we're going to go to index 2 so from index 2 Until the End we're going to look for the minimum so we're going to end up with 23 29 and then I guess the minimum here is 31 so we're going to have uh 31 54 51 61 67 and then 35 now next we're going to keep going so index 3 until the end and we end up with 23 29 31 and then the minimum from 54 to 35 is going to be 35 uh 51 61 67 and then 54 next we'll look from 51 to 54 um we've got 23 29 31 35 uh let's see the minimum from 51 to 54 is actually just 51 so we can leave this in place 51 61 67 uh 54 and that's pretty much it now we're going to look from here to here and we'll end up with 23 29 31 35 uh 51 and the minimum here is going to be 54 so 54 67 61 and next we've only got two elements left so I mean this is pretty much going to be the last iteration 23 29 uh 31 35 51 54 uh 61 and then 67 and we are literally sorted now one thing to pay attention to is that this section in purple is our unsorted portion and the section outside is our sorted portion and as we continually go through the array the sorted portion will grow and the unsorted portion will decrease until it's only one element at which point the entire array is sorted now basically what we did each time is we looked for the minimum in our in the unsorted portion and that was that was sufficient to get us or that's what we needed to do to get it to get the array in ascending order however if we wanted to look if we wanted to um put the array into descending order then we would look for the maximum instead of the minimum and in that case the first element at the first element at index Z would be 67 and so forth so sending order we're looking for the minimum and descending order we're looking for the max that's something to keep in mind when you have to write code to use a selection sort to sort an array in a particular order which does actually come up on the IB exam okay so now that we've seen how selection sort Works let's see how we can approaches programmatically so the first thing to keep in mind is that we are essentially going to start an index 0 and then we're going to find the maximum or the minimum value from index 0 all the way until the end of the array so we start index zero and then we go to the end of the array and then s and then the next time around we'll start at index one 2 3 4 5 6 and then seven although we don't necessarily need to go to seven and each time from that index we're going to find the maximum or minimum from that index until the end of the array end of the array end of the array end of the array end of the array end of the array and it's I guess it's just that element right there now to do this we need two Loops first we're we're going to need one Loop to access every element from 0 to n minus one where n is equal to the length of the array minus or is equal to the length of the array so we're going to have one Loop we can just say Loop um we could say loop I uh from zero to uh n minus one and then basically every time I changes we're going to need another loop that's going to go from I until the end of the array and that's that can be represented by the purple lines that we used so inside that every time I changes we need a loop that goes so we need a loop J from I to n minus1 so for example when I is equal to 1 then J is going to go from uh or it's going to go from 1 to n minus one actually we'll um we'll use some different colors to make it really clear so when I is equal to 1 when I is equal to one then we're going to go from um we're going to go so J is going to go from 1 to nus1 when I is equal to 2 then J is going to go from 2 to n minus one and as J is going from 1 to n minus one we're going to be finding the max or Min in in like to that process so as We're looping through from 1 to n minus1 we'll be executing operations to find the max or min and we'll do this until essentially we get to the end of the array so now we understand now we have some understanding as to how we could write this code then let's go ahead and let's actually write the write the um entirety of the code so you can see how everything works okay we've already got the nums array that we will be sorting so if you look right here the first loop we're going to write is going to be to control the number of passes that uh that we need to to turn the unsorted array into a completely sorted array that's just going to be 0 to n minus1 and that's illustrated by these red numbers that we have right here so we're going to have uh loop we're going to Define n as nums do length and we're just going to say uh loop I from 0 to n minus one and then inside that we're going to control the process that goes on right here which is basically just finding the maximum or the maximum or the minimum each time we pass through and then uh and then swapping the value at the given index with whatever that maximum or minimum is so basically the way that we could do that is we could say uh loop I or Loop J uh from from I 2 N minus one because we can go from our current index uh to the end and we can say um if array J or if num J so that means that this J is going to be going from here to here and then here to here and then here to here and then here to here until we get to the end then we can just say num J or we need to calculate a we let's say we want to turn this into to ascending order which should require a minimum we're going to create a variable right here that says Min index equals I uh which is basically the first element in our unsorted portion it's going to be right here then we're going to say Loop J from that to the end and we're going to say uh if we're calculating the minimum right so we're going to say if num J is less than that first element or is less than the minimum index that variable then or Nom Min index and we can change Min index to what the new minimum is so we can say Min index equals J again keep in mind J is going to be the counter that uh allows us to go through the unsorted portion starting at I and going to the end that's marked by the uh purple uh arrows and then we can say end if and end Loop so once we've actually gone through um the entirety of the unsorted portion then we can actually um use our swapping logic so we can say temp equals array I or num I we could also do num index if we wanted to actually get min index would have changed so we can't do that anymore but we can just say num I that corresponds to the top Loop so that's going to be this value this value value this value this value whatever and then we can say um num I equals uh num Min index so we're swapping the current minimum with that one and then wherever Min index was we put whatever it was at num I so we'll say num Min index uh equals Temp and then end if so we're going to end actually we don't have an if statement we're just going to say end Loop right there so all of this is happening after we've actually found the minimum in the unsorted portion and then we're just doing the swapping process within the array and that's how the selection sort works so now that we've had a chance to look at both the bubble sort and selection sort in depth let's just do a little comparison now the first and obvious difference is the methodology which we've talked quite a bit about but also there's a different number of swaps you make by swaps I mean when we have something like3 67 69 71 I guess okay let's just make this like 51 just so it's not sorted swaps is when we're actually swapping elements and partly because we do need to hold um we need to create an extra variable and hold a value in memory while we swap them this can be Memory inefficient or take up some memory space now this isn't really a big problem until we get into values that consist of like millions or get into millions but it's still something to consider so basically with the bubble sort when we go through a bubble sort every time we pass through because our uh maximum values are bubbling to the top like for example we'd have 69 eventually ending up right here we're making multiple swaps each time we go through for this bubbling process but with the selection sort we only we're only making one swap each time we pass through an array that's a swap between the maximum value and the value of the current index that we're on in the sort so in some ways a selection sort can actually be more efficient than the bubble sort but it really depends on the circumstances so I would say besides methodology this is one big difference now let's take a look at some IB questions involving both the bubble sort and the selection sort so describe how a selection sort algorithm could be used to sort the array three in ascending order um here we have a paragraph that basically simulates the code that we wrote which is why I wanted to to write the code um I'm not going to go through all this but I just wanted to show this to you as an example of probably one of the most common selection stort questions although I have also seen pseudo code coding questions involving selection sort okay so now this next question is a great question that speaks to our comparison between bubble swort and selection sord Identify two differences and two similarities between a bubble swort and a selection sort when sorting an array of 10 elements so the comparison given here is that both use NE Loops which is true each time reducing the inner loop which I guess if we're talking about reducing the inner loop that means that the this I don't know if I necessarily agree with this one but I guess we're decreasing the set of um of numbers at which we're working with each time but then also we say that the bubble swort swaps adjacent items and the selection sort finds the next smallest item each time it goes through the list so those are two important differences right there and the bubble sort can exit early if already sorted this depends on the algorithm but that is a possibility so we've got these two as our similarities and basically these two as our differences right here now for some Channel updates in the short term I have two videos that I'm playing on making which are a part two of the SL pseudo code problem series and a part one of the HL pseud code problem Series in the long term I am thinking about making an option B video I haven't really decided yet definitely going to add some more a Lev videos which probably aren't relevant to you but it kind of tells you what I'm doing and then I'm going to start work on a new channel which I'm really excited about and I will be announcing somewhere here soon anyways I hope this video was of value to you if it was please consider liking this video and subscribing to the channel have a nice day