CS50 2020 - Lecture 3 - Algorithms

[Music] [Music] all right this is cs50 and this is week three and you'll recall that last week we equipped you with all the more tools by which to solve problems not only problems that we had proposed but problems in your own code that is to say bugs and recall that those tools involve uh command line tools like help 50 for help with cryptic error messages that the compiler might spit out style 50 which gives you a bit of feedback on the stylization of your code the aesthetics thereof check 50 which checks the correctness of your code against the specifications in a given problem set or lab printf which is a function that exists in some form in almost any programming language that you might ultimately learn and this is simply a way of printing out anything you might want from the computer's memory onto the screen then perhaps the most powerful of these tools was debug 50 which was this interactive debugger and even though this command debug 50 is a little specific to cs50 what it triggers to happen that little side window where you can see the stack of functions that you might have called uh during some break point and you can see the local variables that you might have defined at some point during the execution of your code that's a very common conventional feature of any debugger with most any language and then lastly recall there was this ddb duck debugger which of course takes this physical form if you happen to have a rubber duck lying around with whom you can talk but i'm so pleased to say that if you lack that currently uh while at home uh cs50 zone kareem and brenda and sophie have wonderfully added if you haven't noticed already that same virtual duck to cs50 ide so if you click in the top corner you can actually begin to have a chat of sorts with the rubber duck and while this is certainly a more playful incarnation of that same idea we really can't emphasize enough the value of talking through problems when you're experiencing them in code with someone else or with something else this particular duck not all that large of a vocabulary but it's not so much what the other person says but what you say and what you hear yourself saying that is undoubtedly the most valuable part of the process so our thanks to kareem and brenda and sophie on that recall last week too that we took a look underneath the hood literally in some sense at the computer's memory in your laptop or desktop or phone and then we decided to think about this more artistically as just a grid of bytes so within that chip there's a whole bunch of bits and if you look at eight of them at a time there's a whole bunch of bytes and it stands to reason that we could think of this as like the first bite the second bite the third bite and so forth and sort of chop this up pictorially into just a whole uh sequence of bytes in the computer's memory and recall that if we zoom in on that and focus on just one contiguous block of memory otherwise known as an array we can do things within this array like storing a bunch of different values so recall last week we started by defining a little goofily multiple variables that were almost identically named like scores one scores two scores three and then we begin to clean up the design of our code by introducing an array so we can have just one variable called scores that is of size three and has room for multiple values so today we'll continue to leverage this feature of many programming languages being able to store things contiguously back to back to back to back in a computer's memory because this very simple layout this very simple feature of the language is going to open up all sorts of powerful features and in fact we can even revisit some of the some of the problems we tried to solve way back in week zero but there is a catch with the rays and we didn't really emphasize as much last week and that's because even though you and i can glance at this picture on the screen and see immediately that though there's seven boxes on the screen there's seven locations in which you can store values you and i can sort of have this bird's eye view of everything and just see what's inside that entire array all at once but computers recall are much more methodical more algorithmic if you will and so a computer as powerful as they are can technically only look at one location in an array at a time so whereas you and i can glance at this and sort of take it all in at once a computer just can't glance at its memory and take in all at once all of the values they're in it has to do so more methodically for instance from left to right maybe right to left maybe middle onward but it has to be an algorithm and so today we'll formalize that notion and really kind of hide the fact that this array cannot be seen all at once you can only look at one location in an array at a given time and this is going to have very real implications for instance if we consider that very first problem in the very first week where we tried to find my phone number in a phone book the very naive approach was to start at the beginning and search from left to right and we tried a couple of variants thereafter but the problem quite simply is that of searching and this is a term of art and computer science super common certainly for you and i as users on google and the like to search for things all day long and so certainly searching well designing a search algorithm well is certainly a compelling feature of so many of today's tools that you and i use so if we think of this really as a problem to solve we've got some input which for instance might be an array of numbers or maybe an array of web pages in the case of google and the goal is to get some output so if the input to the problem is an array of values the output hopefully is going to be something as simple really as a bull yes or no is the value you're looking for discoverable can you search for and find that value yes or no true or false now within this black box recall is going to be some algorithm and that's where today we'll spend most of our time indeed we won't really introduce that many more features of c we won't introduce that much more code we'll focus again on ideas just taking for granted now that you have some more tools in your toolkit beyond loops and conditions and boolean expressions we now have this other tool known as arrays but let's first introduce some some other terms of art some jargon if you will related to what we'll call running time so we've alluded to this a few times when we're thinking about just how good or bad an algorithm is we describe how long it takes to run that is it's running time the running time of an algorithm is how long it takes how many steps it takes how many seconds it takes how many iterations it takes it doesn't really matter what your unit of measure is maybe it's time maybe it's iterations or something else but running time just refers to how long does an algorithm take and there are ways that we can think about this a little more formally and we kind of did this already in the first week but we didn't give it this name this italicized o this capital o on the screen is otherwise known as big o notation and computer scientists and some mathematicians will very frequently use literally this symbol to describe the running times of algorithms or mathematically like a function so recall this picture in fact when we were searching that phone book we did it sort of good better best we did it linearly that is searching one page at a time we did it twice as fast by doing two pages at a time and then we did it logarithmically by dividing and conquering in half and half and half and at the time i proposed that if we think of a phone book as having n pages where n is just a number in computer science vernacular we might describe the running time or the number of steps involved for that first algorithm as being maybe in the worst case n steps if the person you're looking for in a phone book maybe alphabetically has a last name starting with z in english well the z might be all the way at the end of the phone book so at the worst case you might be taking n steps to find someone like myself in that phone book the second algorithm though was twice as fast because we went two pages at a time so we might describe its running time as n divided by two and then the third algorithm where we divided the problem in half and half and a half literally throwing half of the problem away again and again was logarithmic technically log base two of n which again is just a mathematical formula that refers to having something again and again and again and you start with of course n pages in that scenario well it turns out that a computer scientist would actually wave their hands at some of these mathematical details indeed we're not going to get into the habit of writing very precise mathematical formulas what we're instead going to do is try to get a sense of the order on which uh the running time of an algorithm is just roughly how fast or how slow it is but still using some symbology like n as a placeholder and so a computer scientist would describe the running time of all three of those algorithms from week zero as being big o of n or big o of n over two or big o of log base two of n so big o just means on the order of it's sort of a wave of the hand maybe it's n minus one maybe it's n plus one maybe it's even two n but it's on the order of n or these other values but in fact two notice this chart there's something kind of curious like these first two algorithms from week zero kind of pictorially look pretty much the same like undoubtedly the yellow line is a little lower and therefore a little better and a little faster than the red line but they have the same shape and in fact i bet if we zoomed way out these two straight lines would pretty much look identical if you change your axis to be big enough and tall enough these would start to blur together but clearly the green line is fundamentally different and so this speaks to a computer scientist's tendency to not really quibble over these details like yes the second algorithm in week zero was better yes this yellow line is better but uh let's just call both of those algorithms running times on the order of n that is to say a computer scientist tends to throw away constant factors like the one half or the divided by two and they tend to focus only on the dominant factor like which value in that mathematical expression is going to grow the most grow the fastest and n divided by 2 n is going to dominate over time the bigger the phone book gets the more pages you have it's really n that's going to matter less so than that divided by 2. and same thing over here if you're familiar with and remember your logarithms we don't really have to even care about the base of that logarithm yes it's base 2 but we can just multiply that logarithm by some other number to convert it to any base we want base 10 base 3 base 7 anything so let's just say it's on the order of log n so this is good because it means we're not really going to waste time getting really into the weeds mathematically when we talk about the efficiency of algorithms it suffices to describe things really in terms of the variable and in this case if you will that dominates over time and indeed let's zoom out if i zoom out on this picture boom you begin to see that yeah these are really starting to look almost identical and if we kept zooming out you would see that they're essentially one and the same but the green one stands out so that's indeed on the order of log of n as opposed to n itself so here's a little cheat sheet it turns out that within computer science and within our the uh analysis of algorithms we're going to tend to see some common formulas like this so we've just seen on the order of n we've seen on the order of login it turns out that very common two is gonna be n times log n maybe even n squared and then even big o of one and the last of those just means that an algorithm takes wonderfully one step or maybe two steps maybe even ten steps but a constant number of steps so that's sort of the best case scenario at least among these options whereas n squared is going to start to take a long time it's going to start to feel slow because if you take any value of n and square it that's going to imply more and more steps so just a bit of jargon then to start off today whereby we now have this sort of vocabulary with which to describe the running times of an algorithm in terms of this big o notation but there's one other notation and just as big o refers to an upper bound on running times like uh like how many steps maximally how much time maximally might an algorithm take this omega notation refers to the opposite what's a lower bound on the running tom of an algorithm and we don't need another picture or other formulas we can reuse the same one so this cheat sheet here just proposes that when describing the efficiency or inefficiency of an algorithm and you want to come up with a lower bound like minimally how many steps does my algorithm take we can use the same mathematical formulas but we can note that with omega instead of big o so again looks fancy but it really just refers to a wave of the hand trying to sort of ballpark exactly what the running time is of an algorithm and thankfully we've seen a few algorithms already including in that week zero and now we're going to give it a more formal name linear search is what we did with that phone book first off by searching it page by page by page looking for my phone number in that particular example and so the difference today is that unlike us humans can who can sort of look down at a phonebook page and see a whole bunch of names and numbers at once unlike a human who can look at an array on the board a moment ago and sort of see everything at once we need to be more methodical more deliberate today so that we can translate week zero's ideas now not into even pseudo code but actual c code and so wonderfully here at the american repertory theater as we are on harvard's campus this semester we've been collaborating with uh the whole team here who are much more artistically inclined and certainly i could be on my own here and we have these seven wonderful doors that were previously used in various theatrical shows that took place here in this theater and we've even collaborated with the theater's prop shop who in back have wonderfully manufactured some delightful numbers and brought them to life which is to say that behind each of these seven doors is a number and this is going to be an opportunity now to really hammer home the point that when we want to search for some number in an array it's pretty equivalent to having to search for a number in this case behind an otherwise closed door you and i can't just look at all of these doors now and figure out where a number is we have to be more methodical we have to start searching these doors maybe from left to right maybe from right to left maybe from the middle on out but we need to come up with an algorithm and ultimately translate that to code so for instance suppose i were to search for the number zero how could we go about searching methodically these seven wooden doors for the number zero let me take a suggestion from the audience what approach might you take what first step would you propose i take here on my own with these doors any recommendations how do i begin to find myself the number zero florence what do you propose um i would propose starting from the left since zero is one a smaller number okay good and hang in there for with me for just a moment let me go ahead and start on the left as florence proposes go ahead and open the door and hopefully voila no it's a number four so it's not a zero so florence what would you propose i do next um i would probably start in the middle somewhere if like in case i don't know it's going down by one so okay so maybe it's going down so let me go ahead and try that so you propose middle i could go over here and voila nope that's the number two and i wonder where else should i should i look let me i'm a little curious i'm a little nervous that i ignored these doors so florence if you don't mind let's go ahead and look here and nope that's the number six it seems uh let's go ahead and check in here the number eight so they're kind of going up and down so florence how might i finish searching for this number what remains to be done would you say probably start from the right okay so i could start from the right now and maybe just go over here and voila and there it is so we found the number zero so let me ask florence what was your algorithm how did you go about so successfully finding the number zero for us um i guess i initially tried starting like by going down by one so uh like if uh the number was not at the left then going to the center which was like halfway in between okay right there i don't know and playfully how did how did that work out for you going to the middle better worse no different i mean i i guess uh maybe it helped a little bit to then go all the way to the right okay yeah we might have gleaned some information but let's go ahead and take a look at all of the doors for a moment there's that four and the six again here's that eight again over in the middle we had the two again over here we have a seven uh for the first time over here we have a five and then of course we have a zero and if you took all of that in honestly florence you and i we couldn't really have done any better because these these numbers it turns out are just randomly arranged behind these doors so it wasn't bad at all that you kind of hopped around although the downside is if you hop around you know you and i as humans can pretty easily remember where we've been before but if you think about how we would translate that to code i feel like we're starting to accumulate a bunch of variables maybe because you have to keep track of that so frankly maybe the simplest solution whoops maybe the simplest solution would have been where we started in week 0 where we just take a very simple if naive approach of starting with our array this time of size 7 behind which are some numbers and if you don't know anything about those numbers honestly the best you can do is just that same linear search from week zero and just check one at a time the values behind each of these doors and just hope that eventually you will find it so this is already sort of taking a lot of time right if i do this linear search approach like i did in week 0 i'm potentially going to have to search behind all of those doors i'm going to have to search behind all of those doors so let's consider a little more formally exactly how i could at least implement that algorithm because i could take the approach that florence proposed just kind of jumping around and maybe using a bit of intuition but again that's not really an algorithm we really need to do something more step by step and in the meantime let's go ahead joe and let's close the curtain and see if we can't clean those up with another problem in a moment while we consider now linear search and the analysis thereof so with linear search i would propose that we could implement it in in pseudocode first if you will like this for i from 0 to n minus 1 all right we'll see where we're going with this if the number is behind the ice door return true otherwise at the very end return false so it's a relatively simple translation into pseudo code much like we did with the phone book some time ago and why though these values because i'm now starting to express myself a little more like c even though it's still pseudo code so for i from zero to n minus one so computer scientists tend to start counting from zero if there's n doors or seven doors in this case you wanna go from zero on up to six or from zero on up to n minus one so this is just a very common way of setting yourself up with a for loop maybe in c maybe in pseudocode in this case that just gets you from left to right algorithmically step by step if a condition number is behind the ith door i just being a colloquial way of saying what is behind the door at location i go ahead and return true i have found myself the number i want for instance the number zero and then notice that this return false is not part of an else because i don't want to abort this algorithm prematurely and abort simply because a number is not behind the current door i essentially want to wait all the way to the end of the algorithm after i've checked all n doors and if i have still not found the number i care about then and only then am i going to return false so a very common programming mistake might be to nest this internally and think about things in terms of ifs and else's but you don't need to have an else this is kind of a catch-all here at the very end but now let's consider if this is the pseudo code for linear search just what is the efficiency of linear search what is the efficiency of leading your search which is to say how well designed is this algorithm and we we put i gave ourselves a framework a moment ago big o notation which is an upper bound which we can think of for now as meaning like a worst case in the worst case how many steps might it take me to find the number zero or any number for that matter among n doors is it big o of n squared big o of n times log n big o of n big o of log n or big o of one which again just means a constant fixed number of steps brian could we go ahead and pull up this question let me go ahead and pull it up on my screen as well if you go to our usual url to propose what you think an upper bound is on the running time of linear search okay indeed if we consider now the running time of linear search it's going to be big o of n why is that so in the worst case the number i'm looking for 0 might very well be at the end of that list which is going to be on the order of n steps or in this case precisely n steps so that's one way to think about this well now let me ask a follow-up question proposing instead that we consider omega notation which is a lower bound on the running time of an algorithm brian could we go ahead and ask this question next at that same url we'll see a question asking now for the possible answers for the running time for a lower bound on the running time of linear search so let's go ahead and take a look at this one here and in just a moment we'll see as the responses come in about 75 plus percent of you are proposing that it's actually omega of one so omega is a lower bound one refers to constant time and why is that let me just take a quick answer on this point among the 75 percent of you who said one step or a constant number of steps why is that how do you think about this lower bound on running time how about from keith why omega of one uh yeah you can just open it and be lucky and find it in the first tour yeah so it really speaks to just that you might just get lucky and the number you're looking for might be at the very first door so the lower bound in the best case if you will of this algorithm linear search might very well be omega of one for exactly that reason that you have to get lucky and the element might be there at the beginning so that's pretty good we really can't do any better than that so we have this range now of a lower bound from omega of one on up to big o of n being an upper bound on the running time of linear search but of course we have this other algorithm in our toolkit and recall from week zero that we looked at binary search although not necessarily by name it was that divide and conquer third algorithm where we took the phone book and split it in half and half a half again now while i fumbled there joe kindly has given us a new set of doors if joe we could go ahead and reveal our seven doors again behind which we still have some numbers but i think this time i'm going to be a little better off cue joe and the doors behind there we go so we have our same seven doors but behind those doors now is a different arrangement of numbers and suppose this time i want to find myself the number six so the number six will change the problem slightly but i'm going to give you one other ingredient this time which is going to be key to this working why were florence and i able to do no better than linear search before why were florence and i able to do no better than randomly searching even last time what was it about the array of numbers or the array of doors that didn't not allow me previously to use binary search iris what do you think um it's because the we didn't know if the numbers were sorted or not yeah we didn't know if the numbers were sorted or not and indeed barring that detail florence and i really couldn't have done any better than say linear search so this time though joe has kindly sorted some numbers behind these doors for us and so if i want to search for the number six now i can begin to use a bit of that information so you know what i'm going to start just like we did with the phone book and start roughly in the middle and voila number five all right so we're pretty close we're pretty close but the thing about binary search recall is that this is now useful information if the numbers are sorted behind these doors all of the doors to the left should presumably be lower than 5 and all of the doors to the right should presumably be larger than 5. now i might kind of cut a corner here and be like well if this is 5 6 is probably right next door literally but again algorithmically how might we do this we don't want to necessarily consider these special cases so more generally it looks like i now have an array of size three so let me go ahead and apply that same algorithm voila to the middle now i have the number seven and now it's becoming pretty clear that if the number six is present it's probably behind this door and indeed if i now look at my remaining array of size one and voila in the middle there's that number six so this time i only had to open up three doors instead of all seven potentially or maybe all six doors to find my way to that number because i was given this additional ingredient of all of those numbers being sorted so it would seem then that you can apply the better more efficient better designed algorithm now known as binary search if only someone like joe would sort the numbers for you in advance so let's consider now a little more algorithmically how we might implement this so with binary search let me propose this pseudocode if the number is behind the middle door return true we found it so if we got lucky then we might very well have found the number six behind the middle door and we would have been done but that didn't happen and in the general case that probably won't happen so if the number is less than that behind the middle door then just like with the phone book i'm going to go to the left and i'm going to search the left half of the remaining doors in the array else if the number is greater than that behind the middle door then like the phone book i'm going to go ahead and search the right half of the phone book but there might still be one final case potentially whereby if there's no doors left at all or no doors in the first place i should at least have this one special case where i do say return false for instance if six for whatever reason weren't be among those doors and i were searching for it i still need to be able to handle that situation where i can say definitively return false if i'm left with no further doors to search so here then might be the pseudo code for this algorithm a bit more formally now let's consider the analysis thereof before where we left off linear search was big o of n linear search was big o of n this time let's consider where binary search actually falls into place by asking a different question i'm going to go ahead and go back and ask this question now what's an upper bound on the running time of binary search an upper bound on the running time of binary search and go ahead and buzz in if you'd like similarly to before what's an upper bound on the running time of binary search and you can see here answers are getting pretty dominant around log n and indeed that jives with exactly what we did in week 0. the correct answer is indeed log of n because that's going to be the maximum number of times that you can take a list or an array of a given size and split it in half and half and half until you find the number you're looking for or ultimately you don't find that number at all meanwhile if we consider now not just the upper bound on this algorithm so in the worst case binary search takes big o of log n now let's consider a related question which is what's a lower bound on the running time of this same algorithm what's a lower bound on the running time i'll go ahead and plug this one off myself and and go back to some of the suggestions thus far in the best case maybe two you do get lucky and the number you're looking for six or some other number is smack dab in the middle of the array and so maybe indeed you can get away with just one step and indeed a lower bound on binary search now might very well just be an omega of one because in that best case you just get lucky and it's right where you happen to start in this case in the middle so we seem to have a range there but strictly speaking it would seem that binary search is better binary search is better than linear search because as n gets big big big you can really feel that difference in fact recall from week zero we played a little bit with these light bulbs and right now all 64 of these light bulbs are on and let's consider for a moment just to put this into perspective how long it would take to use linear search to find one light bulb among these 64. and recall that in the worst case maybe the light bulb or the number that we're looking for is way down there at the end but we don't know it in advance and so sumner if you wouldn't mind executing linear search on these light bulbs let's just get a feel for the efficiency or inefficiency of this algorithm linear search in light bulb form so you'll notice that one light bulb at a time is going out implying that i've searched that door searched that door searched that door but we've only gotten through 10 or so bulbs and we've got another 50 plus to go and you can see that if we look uh inside of these doors one per second or turn off these light bulbs one per second it's going to take a long time in fact i it doesn't seem worthwhile to even wait until the very end so summer if you won mine let's bring all the lights back up and let's try once more another algorithm this one binary search just to get again a feel of what the running time is of an algorithm like binary search that runs in logarithmic time so in just a moment we'll go ahead and execute binary search on these light bulbs the idea being that there's one bulb we care about let's see how fast we can get down to just one bulb out of 64. so sumner on your marks get set go and we're done just a few steps later and then we have this soul light bulb that was so much faster and in fact we did this deliberately one iteration at a time the algorithm that we just executed with sumners and matt's help algorithmically was operating what's called one hertz one hertz and if you're unfamiliar hertz is just one something per second it's very often used in physics or just in discussions of electricity more generally and indeed in this case if you're doing one thing per second that first algorithm linear search might have taken us like 64 seconds to get all the way to that final light bulb but that second algorithm was logarithmic and so by going from 64 to 32 to 16 to 8 to 4 to 2 to 1 we get to the final result much faster even going at the same pace so in fact if you think of your computer cpu cpus are also measured in hertz h-e-r-t-z probably measured in gigahertz which is billions of hertz per second so your cpu the brain of your computer if it's one gigahertz that means it can literally do one billion things at a time and here we have this sort of simpler setup of just light bulbs doing one thing per second your computer can do one billion of these kinds of operations at once so just imagine therefore how much these savings tend to add up over time if you can take big bites out of these problems at once as opposed to doing things like we did in week zero just one single step at a time all right well let's now go ahead and start to translate this to code we have enough tools in our toolkit in c that i think based on our discussion of arrays last week we can now actually start to build something in code on our own so i'm going to go ahead and create a file here in just a moment in cs50 ide called for instance numbers.c let me go ahead and translate this to a file nc code called numbers.c and the goal at hand is just to implement linear search in code just so that we're no longer waving our hands at the pseudocode but doing things a little more concretely so i'm going to go ahead and include cs50.h i'm going to go ahead and include standardio.h and i'm going to start with no command line arguments like we left off last week but just with main void and i'm going to go ahead and give myself an array of numbers seven numbers just like the doors and i'm going to go ahead and say int numbers and then this is a little trick that we didn't see last week but it's handy for creating an array when you know in advance what numbers you want which i do because i'm going to mimic the doors that joe kindly set up for us here i'm going to go ahead and say give me an array that is equal to 4 six eight two seven five zero and this is the feature we didn't see last week if you know in advance the numbers that you want to assign to an array you actually don't have to bother specifying the size of the array explicitly the compiler can figure that out intelligently for you but you can use these curly braces with commas inside to enumerate from left to right the values that you want to put into that array so after this line six has executed in my computer i'm going to be left with an array called numbers inside of which are seven integers listed from left to right in the computer's memory so to speak in this way now what do i want to do with these numbers well let's implement linear search linear search as we latched on to earlier is a searching from left to right or equivalently right to left but convention tends to go left to right so i'm going to do a standard for loop for int i get 0 i is less than i'm going to keep it simple for now and hard code this but we could clean this up if we want and i'm going to do i plus plus on each iteration so i'm pretty sure that my line 8 will induce a for loop that iterates 8 total times and what question do i want to ask on each iteration well if the numbers array at location i equals equals for instance the number i was searching for initially let's go ahead and search for zero then what do i want to do let me go ahead and print out something arbitrary but useful like found quote unquote so the human knows and then let me go ahead and just for good measure let me go ahead and return zero and we'll come back to that in just a moment but at the end of this program i'm also going to do this printf not found with a backslash n and then i'm going to go ahead and return one but before we tease apart those returns just consider the code in the aggregate here's my entire main function and on line six to recap i initialize the array just as we did very at the very beginning with a seemingly random list of numbers behind the doors then on line eight i'm going to iterate with this for loop seven total times incrementing i in each turn and then line ten just like i was opening the doors one at a time i'm going to check if the ith number in this array equals equals the number i care about 0 with that first demo i'm going to print found otherwise not else per se but otherwise if i go through this entire loop checking if if if if and i never actually find zero i'm going to have this sort of catch-all at the end that just says no matter what if you reach line 16 print not found and then return one now this is a bit of a subtlety but could someone remind us what's going on with the return 0 on line 13 and the return 1 on line 17. why 0 and 1 and why am i returning at all what problem is this solving for me even though most of our programs thus far we haven't bothered too much with this uh to me is it what do you think um it's uh it's demi but um basically return zero is like it was executed correctly or it found it um and it kind of exits that loop saying that it was like found and then return one is like the return false um and it accesses as well exactly and exit really is the operative word in maine when you are done ready to quit the program as we've done with the word quit in some of our pseudo code in the past you can literally return a value and recall at the end of last week we introduced the fact that maine always returns an inch you and i have ignored that for at least a week or two but sometimes it's useful to return an explicit value whether it's for auto grading purposes whether it's for automated testing of your code in the real world or just so it's a signal to the user that something indeed went wrong so you can return a value from main and as uh demi proposed zero means all is well and it's a little counter-intuitive because thus far true tends to be a good thing but in this case zero is a good thing all is well it's success and if you return any other value for instance one that indicates that something went wrong so the reason i'm printing out after the word found i'm returning zero is so that effectively the program exits at that point i don't want to keep going again and again if i already found the number i care about and down here this one admittedly isn't strictly necessary because if i hit line 16 and maybe deleted line 17 the program is going to end anyway but there wouldn't be that so-called exit status that we discussed last week briefly whereby you can kind of signal to the computer whether something was successful or unsuccessful and the reason that zero is a good thing and one or any other number is not consider how many things can go wrong in programs that you write or that companies in the real world right when you get those error messages sometimes with those cryptic error codes there are hundreds thousands of problems that might happen in a computer program that could be that many error codes that you see on the screen reasons explaining why the program crashed or froze or the like but xero is sort of special in that it's just one value that the world has decided means success so there's only one way to get your program right in a sense but there's so many millions of ways in which things can go wrong and that's why humans have adopted that particular convention all right but let's consider now not just numbers but let's make things more interesting besides the door suppose that we actually had people's names behind them well let's go ahead and write a program this time that not only searches for numbers but instead searches for name so i'm going to go ahead and create a different file here called names.c and i'm going to start a little similarly i'm going to include cs50.h at the top i'm going to include standard io at the top but i'm also this time going to include string dot h which we introduced briefly last week so that we have access to stur lang for getting the length of a string and it turns out some other functions let me go ahead and declare int main void as usual and then inside here i need some arbitrary names let's come up with seven names here and here too i can declare an array just as i did before but it doesn't have to store only ins it can store strings instead so i've changed the data type from into string and i've changed the variable name from numbers to names and i can still use this new curly brace notation and i can give myself a name like bill and maybe charlie and maybe fred and maybe george and maybe ginny and maybe percy and lastly maybe a name like ron and it just barely fits on my screen so with that said i now have this array of names and beyond there being an perhaps obvious pattern to them there's a second less obvious or maybe obvious pattern to them how would you describe the list of names i arbitrarily just came up with what's a useful characteristic of them what do you notice about these names and there's at least two right answers to this question i think what do you notice about these names uh jack uh they're in alphabetical order yes so beyond being the names of the weasley children and harry potter they're also in alphabetical order and that's the more salient detail for our purposes i've had the forethought this time to sort these names in advance and if i've sorted these names that means implicitly i can use a better algorithm than linear search i can use for instance our old binary search but let's go ahead first and just search them naively for now let's still apply linear search because you know what we haven't yet done is necessarily compare strings against one another we've done a lot of comparisons of numbers like integers but what about name so let me go ahead and do this so for int i gets 0 just like before i less than 7 i plus plus and i'm doing this only because i know in advance there's seven names i think we could probably improve the design of this code too by having a variable or a constant storing that value but i'm going to keep it simple and focus only on the new details for now and it turns out for reasons we'll explore in more detail next week it is not sufficient to do what we did before and do something like this if i'm searching for ron it turns out that in c you can't use equals equals to compare two strings you can for an int you can for a char we've done both of those in the past but there's a subtlety that we'll dive into in more detail next week that means you can't actually do this and this is curious because if you have prior programming experience in languages like python or the like you can do this so in c you can't but we'll see next time why but for now it turns out that c can solve this problem and historically the way you do this is with a function so inside of the string.h header file there is not only a declaration for sterling the length of a string like last week there's another function called stir compare and stir compare for short str cmp allows me to pass in two strings one string that i want to compare against another string so it's not quite the same syntax indeed it's a little harder to read it's not quite as simple as equals equals but string compare if we read the documentation for it will tell us that this compares two strings and it returns one of three possible values if those two strings are equal that is identically the same letter for letter then this function is going to return zero it turns out if the first string is supposed to come before the second string alphabetically in some sense then this function's going to return a negative value if the first string is supposed to come after the second string alphabetically if you will then it's going to return a positive value so there's three possible outcomes either equal to zero or less than zero or greater than zero but you'll notice and in fact if you look at the documentation sometime it doesn't specify what value less than zero or what value greater than zero you have to just check for any negative value or any positive value and i also told a bit of a white lie a moment ago this does not check things alphabetically even though it coincidentally does sometimes it actually compares strings in what's called ascii order or asciibetically which is kind of a goofy way of describing this function looks at every character in the two strings from left to right it checks the ascii values of them and then it compares those ascii values character by character and if the ascii value is less than the other then it returns a negative value or vice versa so if you have for instance the letter a capital a in the string that gets converted first to 65 and then if you have an a in the other string capitalized it too gets compared to 65 and those would be equal but of course all of these names have more than one character so this ascii order or asciibetical proceeds left to right so that stir compare checks every character in the names for you and it stops when it hits that terminating null character recall that strings underneath the hood always end in c with this backslash zero or eight zero bits so that's how stir comp knows when to stop comparing values but if i go ahead and find someone like ron let me go ahead and print out quote unquote found and like before i'll go ahead and return like demi proposed zero just to imply that all is successful otherwise if we get all the way to the bottom of my code i'm going to print out not found to tell the story that we did not find ron in this array even though he does happen to be there and i'm going to go ahead and return one so even though i've hard coded everything to hard code something in a program means to type it out explicitly you could imagine using a command line argument like last week to get users input who would you like to search for you could imagine using getstring to get users input and ask them who would you like to search for but for now just for demonstration's sake i've used only ron's name and if i haven't made any typos let me go ahead and type in make names enter so far so good dot slash names and i'll hopefully we'll see indeed found because ron is very much in this array of seven siblings but the building blocks that are new here are again the fact that when we declare an array of some fixed size we don't strictly need to put a number here and we have this curly brace notation when we know the arrays contents in advance but perhaps lastly and most powerfully we do have this function in c called stir compare that will allow us to actually store and compare strings in this way so let me pause here and just ask if there's any questions about how we translated these ideas to code for numbers and how we translated these ideas to code for now names each time using linear search not binary caleb question uh yeah so if would that program still work if ron for example was like all caps like if you're trying to like search like if like the cases are different in terms of like uppercase and lowercase really good question and let me propose an instinct that's useful to acquire in general when in doubt try it so i'm going to do exactly that i do happen to know the answer but suppose i didn't let me go ahead and change ron to all caps just because maybe the human the caps lock key was on and they typed it in a little sloppily let me go ahead and make no other changes notice that i'm in leaving the original array alone with only a capital r let me remake this this program make names dot slash names and voila he's still in fact found stand by oh okay um uh uh caleb you have just helped me unearth a bug that was latent in the previous example none of you who should have uh accepted the fact that the previous program worked with ron because i didn't practice literally what i'm preaching so caleb hold that thought for just a moment so i can rewind a little bit and fix my apparent bug so ron was indeed found but he wasn't found because ron was found i did something stupid here and it's uh perhaps all the more pedagogically appropriate now to to highlight that so how did this program say ron was found even though this time it also says ron was found in all caps and you know what let me get a little curious here let me go ahead and search for not even ron how about we search for ron's mom molly make names all right and now just to reveal that i really did do something stupid dot slash names okay now something's clearly wrong right i can even search for the father arthur make names dot slash names it seems that i wrote you a program that just literally always says found so we shouldn't have accepted this as correct can anyone spot the bug based on my definition thus far [Music] can anyone spot the bug you know in the meantime this isn't uh really a bad time to open up the duck and say hello duck i am having a problem whereby my program is always printing found even when someone is not in the array and i could proceed to explain my logic to the duck but hopefully sophia can point me at the solution even faster than the duck we need to compare the value that we received from stir comp with something so we need to compare it with like zero and make sure that we receive the value that they're equal perfect so i said the right thing but i literally did not do the right thing if i want to check for equality i literally need to check the return value when comparing names bracket i against ron to equal zero because only in the case when the return value of stir comp is zero do i actually have a match by contrast if the function returns a negative value or the function returns a positive value that means it's not a match that means that one name is supposed to come before the other or lay after the other but the catch with my shorthand syntax here which is not always an incorrect syntax to use whenever you have a boolean expression inside of which is a function call like this notice that the entirety of my boolean expression is just a call so to speak to stir comp i'm passing in two inputs names bracket i and quote unquote ron and therefore i'm expecting stir comp to return output a so-called return value that return value is going to be negative or positive or zero and in fact to be clear if the first name being searched for is bill and names bracket i or names bracket zero is bill bill comma ron is effectively what my input is on the first iteration bill alphabetically and asciibetically comes before ron which means it should be returning a negative value to me and the problem with boolean expressions is as implemented in this context is that only zero is false any other return value is by definition true or a yes answer whether it's negative one or positive one negative one million or positive one million any non-zero value in a computer language like c is considered true also known as truthy any value that is zero is considered false but only that value is considered false so really i was getting lucky at first because my program was finding bill but i was confusing bill for ron then when i did it again for caleb and i capitalized ron i was getting unlucky because suddenly i knew ron capitalized wasn't in the array and yet i'm still saying he's found but that's because i didn't practice what i preached per sophia is fined and so if i actually compare this against zero and now caleb we come full circle to your question i rebuild this program with make names i now do dot slash names and search for all caps ron i should now see thankfully not found so i wish i could say that was deliberate but thus is uh the common case of bugs so here i am 20 years later making bugs in my code so if you run up to a similar problem this week uh rest assured that uh it never gets um it never ends uh but hopefully you won't have several hundred people watching you while you do your problem set this week all right any questions then beyond caleb so great question caleb and the answer is no it is case sensitive so it does not find rob ron any questions here [Music] any questions on linear search using strings no all right well let's go ahead and do one final example i think with searching but let's introduce just one other feature and this one's actually pretty cool and powerful up until now we've been using data types that just come with c or come from cs50 like int and char and float and the like and you'll see now that there's actually sometimes reasons where you or i might want to create our own custom data types our own types that didn't exist when c itself was invented so for instance suppose that i want to represent not just a whole bunch of numbers and not just a whole bunch of names but suppose i want to implement like a full-fledged phone book a phone book of course contains both names and numbers and suppose i want to combine these two ideas together wouldn't it be nice if i could have a data structure that is a data type that has some structure to it that can actually store both at once and in fact wouldn't it be nice if c had a data type called person so that if i want to represent a person like in a phone book who has both a name and a number i can actually implement that end code by calling that variable of type person now of course the designers of c did not have the force site to create a data type called person and indeed that would be a slippery slope if they had a data type for every real world entity you can think of but they did give us the capabilities to do this so if a person in our limited world here of phone books has both a name and a number we might think of it as follows a name and a number both of type string but a quick check here why have i now decided somewhat presumptuously to call phone numbers strings as well we've been talking about ants behind these doors we've been searching for ins in code but why did i just presume to propose that we instead implement a phone book using strings for names and numbers any thoughts here kurt uh yeah because because we're not doing math on it it's like like a phone number could be like letters for all we care and in fact i mean like sometimes you see like 1 800 contacts or something like that and maybe we want to allow that yeah absolutely a phone number despite its name isn't necessarily just a number it might be 1 800 contacts which is an english word uh it might have hyphens in it or dashes it might have parentheses in it it might have a plus sign for country code so there's a lot of characters that we absolutely can represent and see using strings that we couldn't represent in c using ants and so indeed even though in the real world there are these numbers that you and i talk about once in a while like phone numbers maybe in the u.s social security numbers credit card numbers those aren't necessarily values that you want to treat as actual integers and in fact those of you who did the credit problem and tried to validate credit card numbers very may very well have run into challenges by using a long to represent a credit card number it probably in retrospect might very well have been easier for you to treat credit card numbers as strings the catch of course by design is that you didn't yet have strings in your vocabulary at least in c yet so suppose i want to create my own custom data type that encapsulates if you will two different types of values a person shall be henceforth a name and a number it turns out that c gives us this syntax here this is the only juicy piece of new syntax besides those curly braces a moment ago that we'll see today and see typedef and as the name rather succinctly suggests this allows you to define a type and the type will be a structure of some sort so a data structure in a programming language is typically a data type that has some structure to it what do we mean by structure it typically has one or more values inside of it so using typedef and in turn using the struct keyword we can create our own custom types that's a structure a composition of multiple other data types so if we want to keep persons together as their own custom data type the syntax is a little cryptic here you literally do type def struct open curly brace then one per line you specify the data types that you want and the names that you want to give to those data types for instance name and number and then outside of the closing curly brace you literally put the word person if that's indeed the data type that you want to invent so how can we use this more powerfully well let's go ahead and do things the wrong way without this feature first so as to motivate its existence let me go ahead and save this file as phonebook.c and let me start as always with include cs50.h and then let me go ahead and include standardio.h and then lastly let me also include string.h because i know i'm going to be manipulating some strings in a moment let me go ahead now and within my main pro function let me go ahead and give myself initially for the first version of this program a whole bunch of names specifically how about brian comma david we'll keep it short just so as to focus on the ideas and not the actual data they're in then brian and i each have phone numbers so let's go ahead and store them in an array numbers equals again the curly braces as before and plus one six one seven four nine four nine five one thousand and indeed there's already motivation per kurt's comment to use strings because we've got a plus and a couple of dashes in there and then my number here so we'll do plus 1 949 468 2750 closed curly brace semicolon so i've gone ahead and declared two arrays one called names one called numbers and i'm just going to have a sort of handshake agreement that the first name and names corresponds to the first number and numbers the second name in names corresponds to the second number in numbers you can imagine that working well so long as you don't make any mistakes and you have just the right number in each now let me go ahead and do in i equals zero i less than two i'm going to keep that hard coded for now just to do the demonstration and then inside of this loop let me go ahead and search for my phone number for instance even though i happen to be at the end so if stir compare of names bracket i equals rather comma david uh equals equals zero so i'm not going to make that mistake again let me go ahead inside of this loop uh inside of this condition here and i'm going to go ahead and do the following print out that i found for instance my number and i'm going to plug that in so numbers bracket i and then as before i'm going to go ahead and return 0. and if none of this works out and i happen not to be in this array i'll go ahead and print out as before not found with a semicolon and then i'll return one arbitrarily i could return negative one i could return a million negative million but human convention would typically have you go from one zero to one to two to 3 on up if you have that many possible error conditions all right so i essentially have implemented in c a phone book of sorts right we did this verbally in the week zero now i'm doing it in code it's a limited phone book it's only got two names and two numbers but i could certainly implement this phone book by just using two arrays two parallel arrays if you will by just using the honor system that the first element in names lines up with the first element in numbers and so forth now hopefully if i didn't make any typos let me go ahead and make phone book all right it compiled okay dot slash phone book and it found what seems to be my number there so it seems to work correctly though i've tried to pull that one over you before but i'm pretty sure this one actually works correctly and so we found my name and in turn number but why is the design of this code not necessarily the best this is starting to get more subtle admittedly and we've seen that we can do this differently but what rubs you the wrong way about here this is another example of what we might call code smell like something's a little funky here like uh this might not be the best solution long term nick what do you think yeah so what i'm guessing is that uh like you know how you made the data frame before like the new data structure where the two things were like linked together in this case we're just banking on the fact that like we don't screw something up and like unintentionally like unlink them from like the same index so they're like not intrinsically linked yeah which might not be like that's exactly the right instinct in general as great as a programmer as you're maybe aspiring to be you're not all that and like you're gonna make mistakes and the more you can write code that's self-defensive that protects you from yourself the better off you're going to be the more correct your code is going to be and the more ye more easily you're going to be able to collaborate successfully if you so choose in the real world on real world programming projects whether it's for a research project a full-time job a personal project or the like generally speaking you should not trust yourself or other people that with whom you're writing code you should have as many defense mechanisms in place exactly along these lines so yes there's nothing wrong with what i have done in the sense that this is correct but as noted if you screw up and maybe you get an off by one error maybe you transpose two names or two numbers i mean imagine if you've got dozens of names and numbers hundreds of names and numbers thousands of them the odds that you or someone messes the order up at some point is just probably going to be too too high so it would be nice then if we could sort of keep related data together this is kind of a hack to just on the honor system say my arrays line up i'm just going to make sure to keep them the same length we can do better let's keep related data together and design this a little more cleanly and i can do this by defining my own type that i'll call for instance a person so at this top of this file before main i'm going to go ahead and type def a structure inside of which are the two types of data that i care about string name and string number just as before notice though here that what i have done here is not give myself an array i've given myself one name and one number outside of this curly brace i'm going to give this data type a name which i could call person i could call it anything i want but person seems pretty reasonable in this case and now down here i'm going to go ahead and change this code a little bit i'm going to go ahead and give myself an array still but this time i'm going to give myself an array of persons and i'm going to call that array somewhat playfully people because i want to have two persons two people in this program me and brian now i want to go ahead and populate this array that is i want to fill it with values and this syntax is a little new but it's just to enable us to actually store values inside of a structure if i want to index into this array there's nothing different from last week i do people bracket zero that's going to give me the first person variable inside so probably where brian is supposed to go the one last piece of syntax i need is how do i go inside of that structure that person data structure and access the person's name i literally just do a dot so people bracket zero gives me the first person in the people array and then the dot means go inside of it and grab the person variable i'm gonna go ahead and set that name equal to quote-unquote brian the syntax now for his name is almost identical people bracket zero dot number equals quote unquote plus one six one seven four nine five one thousand semicolon meanwhile if i wanna access a location for myself i'm gonna go ahead and put it location one which is the second location name will be quote unquote david and then over here i'm going to do peoplebracket1.number equals quote unquote plus 1 949.468.2750 close quote semicolon so it's a bit verbose admittedly but you could imagine if we just let our thoughts run run ahead of ourselves here if you used get string you could sort of automatically do this if you used command line arguments maybe you could populate some of this we don't just have to hard code that is write my name and number and brian's into this program you can imagine doing this more dynamically using some of our techniques using get string and so forth from week one but for now it's just for demonstration's sake so now if i want to search this new array this new single array of people i think my for loop can stay the same and i think i can still use stir compare but now i need to go inside of not names but people and look for the dot name field so data structures have fields or variables inside of them so i'm going to use the dot notation there too go into the ith person in the people array and compare that name against for instance quote unquote david and then if i have found david in this case myself go ahead and access the people array again but print out using printf the number so again the dot operator is the only new piece of syntax that's letting us go inside of this new feature known as a data structure if i go ahead and make phone book again after making those changes all is well it compiled okay and if i run dot slash phone book i now have hopefully found my number again so here is sort of a seemingly useless exercise and that all i really did was re-implement the same program using more lines of code and making it more complicated but it's now better designed or it's a step toward being better design because now i've encapsulated all inside of one variable for instance people bracket zero people bracket one all of the information we care about with respect to brian or me or anyone else we might put into this program and indeed this is how programs this is how googles of the world facebooks of the world store lots of information together consider any of your social media accounts like instagram or facebook or snapchat and the like you have multiple pieces of data associated with you on all of those platforms not just your username but also your password also your history of posts also your friends and followers and the like so there's a lot of information that these companies for better for worse are collecting on all of us and can you imagine if they just had one big array with all of our user names one big array with all of our passwords one big array with all of our friends like you can imagine certainly at scale that's got to be a bad design to just trust that you're going to get the ordering of all of these things right they don't do that they instead write code in some language that somehow encapsulates all the information related to me and brian and you inside of some kind of data structure and that's what they put in their database or some other server on their back end so this encapsulation is a feature we now have in terms of c and it allows us to create our own data structures that we can then use in order to keep related data together all right any questions then on data structures or more specifically type def and struct the c keywords with which you can create your own custom types that themselves are data structures uh basley uh hi so is it typical to define the new data structure outside of main like in the header really good question is it typical to define a new data structure outside of main quite often yes in this case it's immaterial because i only have one function in this program maine but as we'll see this week and next week and onward our programs are going to start to get a little more complicated by nature of just having more features and once you have more features you probably have more functions and when you have more functions you want your data structure to be available to all of those functions and we'll so we'll begin to see definition of some of these structures being indeed outside of our own functions peter over to you oh yeah uh would we define uh new classes and header files later or will we keep defining them outside of main really good question might we define our own uh types and our own data structures in header files yes eventually we'll do that too thus far you and i have only been using header files that other people wrote we've been using standardio.h string.h that the authors of c created you've been using cs50.h with wii the staff wrote it turns out you can also create your own header files your own dot h files inside of which are pieces of code that you want to share across multiple files of your own we're not quite there yet but yes peter that would be a solution to to this problem by putting it in one central place uh thiago over to you [Music] i was i was thinking this course really takes enough information to solve the upsets because i feel there's uh misinformation uh i am a a freshman and i was taking i was so concentrated and i can't go on go ahead on the sets is there anything that i'm missing it's a really good question and quite fair we do move quite quickly admittedly so indeed recall from week zero this the the fire hose uh metaphor that i i borrowed from mit's water fountain indeed that's very much the case um there's a lot of new syntax a lot of new ideas all at once but when it comes to the individual problems and the problem sets do realize that you should take those step by step and invariably they tend to work from less complicated to more complicated and throughout each of the lectures and each of the examples that we do either live or via the examples that are pre-made on the course's website for your review there's always little clues or hints or examples that you can then do and certainly by way of other resources like labs and the like will you see additional building blocks as well so feel free to reach out more individually afterward happy to point you at some of those resources in fact most recently two will you notice on the course's website what we call shorts which are shorter videos made by another colleague of mine cs50s own doug lloyd which are literally short videos on very specific topics so after today you'll see short videos by doug with a different perspective on linear search on binary search and on a number of other algorithms as well good question sophia back to you i was wondering what the return values that we have for different like error cases um would that be like what's an example of what we would use that for is that like for later if there are like several different cases and we want to somehow keep track of them exactly the latter so right now honestly it's kind of stupid that we're even bothering to spend time returning zero or returning one like we don't really need to do that because we're not using the information but what we're trying to do is sort of lay the foundation for more complicated programs and indeed this week and next week and beyond as your own programs get a little longer and as we the course start providing you with starter code or distribution code that is lines of code that the staff and i write that you then have to build upon it's going to be a very useful mechanism to be able to signal that this went wrong or this other thing went wrong so all we're doing is sort of preparing for that inevitability even if right now it doesn't really seem to be scratching an itch anthony i was just going to ask really quickly obviously in this code we have brian and your name david and that's two people so let's say we had 10 or 20 or even 30 people i know there's a question in the chat but i just wanted to clarify for myself too and the what if being what what would change or what what's the end of that question yeah what would change in the code or what would we do exactly to address that problem oh okay good question so if we were to have more names like a third name or a tenth name or the like the only things that we would have to change in this version of the program is first on line 14 the size of the array so if we're going to have 10 people we need to decide in advance that we're going to have 10 people better still i could for instance allocate myself a constant up here so let me actually go up here just like we did uh in a previous class where we did something like this const inst uh number and i'll just initialize this to 10. and recall that const means constant that means this variable can't change int of course means it's an integer the fact that i've capitalized it is just a human convention to make a little visually clear that this is a constant just so you don't forget but it has no functional role and then this of course is just a value to assign to number then i could go down here on line 16 and plug in that variable so that i don't have to hard code what people would call a magic number which is just a number that appears seemingly out of nowhere now i've put all of my special numbers at the top of my file or toward the top of my file and now i'm using this variable here and then what i could do and i alluded to this only verbally before i could absolutely start hard coding in for instance montague's name and number and rithfix and benedict's and cody's and others but honestly this seems kind of stupid if you're just hard coding all of these names and numbers and in a few weeks we'll see how you can actually store all of the same information in like a spreadsheet or what's called a csv file comma separated values or even in a proper database which the the facebooks and googles of the world would use but what i could do for now is something like this for int i gets 0 i less than the number of people i plus plus and maybe i could do something like this people bracket i dot name equals get string what's the name question mark and then here i could do people bracket i dot number equals get string what's their number and i can ask that question too so now the program is getting to be a little better designed i'm not arbitrarily hardcoding just me and brian now it's dynamic and technically the phone book only supports 10 people at the moment but i could make that dynamic too i could also call getint or like you did this past week use a command line argument and parameterize the code so that it can actually be for two people 10 people whatever you want the program can dynamically adapt to it for you other questions on structs on types or the like no all right so how did we get here recall that we started with this problem of searching whereby we just want to find someone in the doors we just want to find someone in the array we've sort of escalated things pretty quickly to finding not just numbers or names but now names with numbers in the form of these data structures but to do this efficiently really requires a smarter algorithm like binary search up until now we've only used in c code linear search even though recall that we did have at our disposal this pseudocode for binary search but with binary search we're going to need the data to be sorted and so if you want to get the speed benefits of searching more quickly by having sorted numbers somehow someone is going to have to do that for us uh joe for instance sorted behind the curtain all of these numbers for us but what algorithm did he use is going to open up a whole can of worms as to how we can sort numbers efficiently and indeed if you're the googles and the facebooks and the instagrams of the world with millions billions of pieces of data in users you surely want to keep that data sorted presumably so that you can use algorithms like binary search to find information quickly when you're searching for friends or for content but let's go ahead here take a five minute break and when we come back we'll consider a few algorithms for sorting that's going to enable us to do everything we've just now discussed see you in five all right we are back so to recap we have a couple different algorithms for searching linear search and binary search binary search is clearly the winner from all measures we've seen thus far the catch is that the data needs to be sorted in advance advanced order to in order to apply that algorithm so let's just give ourselves a working model for what it means to sort something well as always if you think of this as just another problem to be solved it's got input and output and the goal is to take that input and produce that output well what's the input it's going to be a whole bunch of unsorted values and the goal of course is to get sorted values so the interesting part of the process is going to be whatever there is in the middle but just to be even more concrete if we think now in terms of this unsorted input as being an array of input because after all that's perhaps the most useful mechanism we've seen thus far to pass around a bunch of values at once using just one variable name we might have an array like this 63852741 which seems to be indeed randomly ordered that is unsorted and we want to turn that into an equivalent array that's just one two three four five six seven eight so eight numbers this time instead of seven but the goal this time is not to search them per se but to sort them but before i get ahead of myself could someone push back on this whole intellectual exercise we're about to do with sorting in the first place like could someone make an argument as to why we might not want to bother using a sorted array why we might not want to bother sorting the elements and heck let's just use linear search to find some element whether it's a number behind a door a name in an array like when might we want to just use linear search and not bother sorting uh sophia what do you think we could encounter errors in sorting and that might cause error like unpredictability in terms of like if we can find something versus linear search we know we can find it okay quite fair i will concede that implementing binary search not in pseudocode which we've already done but in code is actually more difficult because you have to deal with rounding especially if you've got a weird number of doors like an odd number of doors versus an even number of doors or an array of those lengths honestly you've got to deal with these corner cases like rounding down or rounding up because any time you divide something by two you might get a fractional value or you might get a whole number so we've got to make some decisions so it's totally solvable and humans for decades have been writing code that implements binary search it's totally possible there's libraries you can use but it's definitely more challenging and you open yourselves up to risk but let me stipulate that that's okay i i am good enough at this point in my progression where i pretty sure i could implement it correctly so correctness is not my concern what else might demotivate me from sorting an array of elements and what might motivate me to ah just use linear search it's so simple can anyone propose why olivia what do you think if the name of the game is efficiency and you have a small enough data set then you might as well just uh just search it versus sort it which would be extra expense yeah really well said if you've got a relatively small data set and your computer operates at a billion operations per second for instance my god who cares if your code sucks and it's a little bit slow just do it the inefficient way why because it's going to take you maybe a few minutes to implement the simpler algorithm like linear search even though it's going to take longer to run whereas it might take you tens of minutes maybe an hour or so to not only write but debug something like the fancier algorithm like binary search at which point you might have spent more time writing the code the faster code than you would have just running the slower code and i can speak to this personally back in grad school some of the research i was doing involved analysis of very large data sets and i had to write code in order to analyze this data and i could have spent hours days even writing the best designed algorithm i could to analyze the data as efficiently as possible or frankly i could write the crappy version of the code go to sleep for eight hours and my code will just produce the output i want by morning and that is a very real world reasonable trade-off to make and indeed this is going to be thematic in the weeks that proceed in the course where there's going to be this trade-off and quite often the trade-off is going to be time or complexity or the amount of space or memory that you're using and part of the um the arts of being a good computer scientist an intern programmer is trying to decide where the line is do you exert more effort up front to make a better faster more efficient algorithm or do maybe cut some corners there so that you can focus your most precious resource human time on other more fundamentally challenging problems so we for the course's problem sets and labs will always prescribe what's most important but in a few weeks time with one of our problem sets will you implement your very own spell checker and among the goals of that spell checker are going to be to minimize the amount of time your code is taking to run and also to minimize the amount of space or memory that your program is taking while running and so we'll begin to appreciate those trade-offs ever more but indeed it's the case and i really like olivia's formulation of it if your data set is pretty small it's probably not worth writing the fastest best designed algorithm as possible just write it the simple way the correct way and get the answer quickly and move on but that's not going to be the case for a lot of problems they're saying most problems in life if you're building facebook or instagram or whatsapp or any of today's most popular services that are getting thousands millions of new pieces of data at a time you can't just linearly search all of your friends or connections on linkedin efficiently you can't just linearly search the billions of web pages that google and microsoft index in their search engines you've got to be smarter about it and undoubtedly the more successful your programs are and your code are your websites your apps whatever the case may be the more important design does come into play so indeed let's stipulate now that the goal is not to search these doors once the goal is not to search these light bulbs once the goal is not to search the phone book once but rather again and again and again and if that's going to be the case then we probably should spend a little more time and a little more complexity up front getting our code not only right but also efficient so that we can benefit from that efficiency again and again and again over time so how might we go about sorting some numbers so in fact let me see to do this if we can maybe get a hand from brian in back brian do you mind helping with sorting yeah absolutely so i've got eight numbers here right now that all seem to be in unsorted order yeah and brian could you go ahead and uh could you sort these eight numbers for us yeah i'll put them in order so we'll take these and um and all right i think these are now in sorted order yeah indeed i agree and now let's take some critique from the audience some observations would someone mind explaining how brian just sorted those eight numbers what did brian just do step by step in order to get to that end result the input was unsorted the output now is sorted so what did he do peter what'd you see happen uh he went through them step by step and if they weren't in increasing order he flipped them and ended up doing it until they were all in the correct yeah he kept step by step kind of looking for small values and moving them to the left and looking for big values and moving them to the right so effectively selecting numbers one at a time and and putting it into its right place so let's see this maybe in more slow motion if you will brian and if you could be a little more pedantic and explain exactly what you're doing i see you've already reset the numbers to their original unsorted order why don't we go ahead and start a little more methodically and could you go ahead and for us more slowly this time select the smallest value because i do think per peter it's going to need to end up at the far left uh yeah sure so i'm looking at the numbers and the one is the smallest so i now have the smallest value all right so you did that really quickly but i feel like you took the liberty of being a human who can kind of have this bird's eye view of everything all at once but be a little more computer-like if you could and if these eight numbers are technically an array kind of like my seven doors out here such that you can only look at one number at a time can you be even more methodical and deliberate this time in telling us how you found the smallest number to put into place sure i guess since the computer can only look at one number at a time i would start at the left side of this array and work my way through the right looking at each number one at a time so i might start with the six and say okay this right now is the smallest number i've looked at so far but then i look at the next number and it's a three and that's smaller than the six so now the three that's the smallest number i found so far so i'll remember that and keep looking the 8 is bigger than the 3 so i don't need to worry about that the 5 is bigger than 3. the 2 is smaller than the 3. so that now is the smallest number i found so far but i'm not done yet so i'll keep looking the 7 is bigger than the 2 the 4 is bigger than the 2 but the 1 is smaller than the two so now i've made my way all the way to the end of the array and one i can say is the smallest number that i've found okay so what i'm hearing is you're doing all of these comparisons also similar to what peter implied and you keep checking is this smaller is this smaller is the smaller and you're keeping track of the currently smallest number you've seen yeah that sounds about right all right so you found it and i think it belongs at the beginning so how do we put this into place now yeah so i want to put it at the beginning there's not really space for it so i could make space for it just by like shifting these numbers over okay wait wait but i feel like you're just now you're doubling the amount of work i i feel like don't don't do all that that feels like you're gonna do more steps than we need what else could we do here okay so the other option is it needs to go in this spot like this first spot in the array so i could just put it there but if i do that i'm going to have to take the six which is there right now and pull the six out all right but i'm in the right place but the six isn't yeah i agree but i think that's okay right because this these numbers started randomly and so the six is in the wrong place anyway i don't think we're making the problem any worse by just moving it elsewhere and indeed it's a lot faster i would think to just swap two numbers move one to the other and vice versa then shift all of those numbers in between yeah so i took the one out of the position at the very end of the array all the way on the right hand side so i guess i could take the six and just put it there because that's where there's an open space to put the number yeah and it's not exactly in the right space but again it's no worse off so i like that all right but now the fact that the one is in the right place and indeed you've illuminated it to indicate as much i feel like we can pretty much ignore the one henceforth and now just select the next smallest element so can you walk us through that yeah so i guess i'd repeat the same process i start with the three that's the smallest number i found so far and i keep looking the eight is bigger than the three the five is bigger than the three the two is smaller than the three so i'll remember that two that's the smallest thing i've seen so far and then i just need to check to see if there's anything smaller than the two and i look at the seven the four and the six none of those are smaller than the two so the two i can say is the next smallest number for the array okay and where would you put that then that needs to go in the second spot so i'll need to pull the three out and i guess i can take the three and just put it into this open spot where there's available space yeah and i feel like it's it's starting to become clear that we're inside some kind of loop because you pretty much told the same story again but with a different number do you mind just continuing the algorithm to the end and select the next smallest next smallest next smallest and get this sorted sure so we got the eight five is smaller than that three is smaller than that and then the rest of the number is seven four six those are all bigger so the three that's going to go into sorted position here and i'll take the eight and swap it now i'm gonna look at the five eight and seven are both bigger the four is smaller than the five but the six is bigger so the 4 that's the smallest number i've seen so far so the 4 that's going to go into place and i'll swap it with the 5. and now i've got the 8 the 7 is smaller than the 8. so i'll remember that 5 is smaller than that but the 6 is bigger so the 5 that's going to be the next number and now i'm left with seven eight is bigger so seven is still the smallest i've seen but six is smaller so six goes next and now i'm down to the last two and between the last two the eight and the seven the seven is smaller so the seven is going to go in this spot and at this point i've only got one number left so that number must be in sorted position and now i would say that uh this is a sorted array of numbers nice so it it seems definitely seems to be correct it felt a little slow but of course a computer could do this much faster than we using an actual array and if if you don't mind making an observation it looks like if we have eight numbers to begin with or n more generally it looks like you essentially did n minus 1 comparisons because you you kept comparing numbers again it actually did n comparisons you looked at the first number and then you compared it again and again and again at all of the other possible values in order to find the smallest element yeah because for each of the numbers in the array i had to do a comparison to see is it smaller than the smallest thing that i've seen so far and if it is smaller then i needed to remember that yeah so in each pass you considered every number so a total of n numbers first until you found the number one you put it in its place and that left you to be clear with n minus one numbers thereafter and then after that n minus two numbers n minus three numbers dot dot dot all the way down to one final number so i think this is correct and i think that's a pretty deliberate way of sorting these elements a little more deliberately than your first approach brian which i might describe as a little more organic you kind of did it like more like a human just kind of eyeballing things and moving things around but if we were to translate this into code recall that we have to be ever so precise and so let me consider altogether how exactly we might translate what brian did ultimately to again pseudo code so what he did is actually an algorithm that has a name it's called selection sort why well it's sorting the elements ultimately and it's doing so by having brian or really the computer select the smallest element again and again and again and once you found each such small element you get the added benefit of just ignoring it indeed every time brian lit up a number he didn't need to keep comparing it so the amount of work we he was doing was decreasing each iteration n numbers then n minus 1 then n minus 2 n minus 3 and so forth and so we can think about the running time of this algorithm as being manifest in its actual pseudo code so how might we define the pseudo code well let me propose that we think of it like this for i from zero to n minus one now undoubtedly this is probably the most cryptic looking line of the three lines of pseudocode on the screen but again this is the kind of thing that should become rope memory over time or just instincts with code we've seen and see how you can write a for loop for loops typically by convention start counting at zero but if you have n elements you don't want to count up through n you want to count up 2n or equivalently up through n minus 1. so from 0 to n minus 1. all right now what do i want to do on the next on the first iteration find the smallest item between the ith item and the last item so this is not quite obvious i think at first glance but i do think it's a fair characterization of what brian did because if i is initialized to zero that was like brian pointing his left hand at the first number on the very left of the the shelf and what he then did was he found the smallest element between the ith item the first item zero and the last item so that's kind of a very fancy way of saying brian find the smallest element among all n elements then what he did was small swap the smallest item with the ith item so he just did that switcheroo so as to not have to waste time shifting everything over he instead just made room for it by swapping it with the value that was in its wrong place but now in the next iteration of this loop consider how a for loop works you do an i plus plus implicitly in pseudocode that's what's happening here so now i equals one find the smallest item between the ith item item one zero indexed and the last item so this is a fancy way of saying brian check all of the n elements again except for the first because now you're starting at location one instead of location zero and now the algorithm proceeds so you could write this code in different ways in english like pseudocode but this seems to be a reasonable formulation of exactly that algorithm but let's see it a little more visually now without all the switching around of the humans moving around the numbers let me go ahead and use this visualization and we'll put a link on the course's website if you'd like to play with this as well this is just someone's visualization of an array of numbers but this time rather than represent the numbers as symbols decimal digits now this person is using vertical bars like a bar chart and what this means is that a small bar is like a small number and a big bar is a big number so the goal here is to sort these bars which equivalently might as well be numbers from short bars over to tall bars left to right and i'm going to go ahead and along the top of the menu here i can choose my sorting algorithm and the one we just described we'll call with selection sort so let me go ahead and do this and notice it takes a moment i think to wrap your mind around what's happening here but notice that this pink line is going from left to right because that's essentially what brian was doing he was walking back and forth back and forth back and forth through that shelf of numbers looking for the next smallest number and he kept putting the smallest number over on the left where it belongs and indeed that's why in this visualization you see the small numbers beginning to be put into place on the left as we keep swooping through but notice the colored bar keeps starting later and later more rightward and more right where just like brian was not re tracing his steps as soon as he lit up the numbers he left them alone and voila all of these numbers are now sorted so that's just a graphical way of thinking about the same algorithm but how efficient or inefficient was that well let's see if we can apply some numbers here but there's also ways to do this a little more intuitively over time which we'll do too so if the first time through the shelf of numbers he had eight numbers at his disposal he had a look at all eight numbers in order to decide which of these is the smallest so that's n steps initially the next time he did a pass through the shelf he ignored the brightly lit number one because it was already in place by definition of what he had already done so now he had n minus one steps to go then he did another n minus two steps then n minus three n minus four n minus five dot dot dot all the way down to the final step where he just had to find and leave alone the number eight because that was the biggest number so one single step so this is uh some kind of series here mathematically you might recall something like this at like the back of your math book or in high school or back at your physics textbook or the like it turns out that this actually sums up to this formula here n times n plus 1 divided by 2. and if that's not familiar you don't remember that no big deal just let me stipulate that the mathematical formula with which we began where we had the series of n plus n minus 1 plus n minus 2 plus n minus 3 dot dot dot simply sums up ultimately to the more succinct n times n plus 1 divided by 2. this of course if we multiply it out gives us n squared plus n divided by 2 and this now i will propose gives us yes this n squared divided by 2 plus n over 2. so if we really wanted to be nitpicky this is the total number of steps or operations or seconds however we want to measure brian's running time this seems to be the precise mathematical formula therefore but at the beginning of this week we considered again the sort of big o notation with a wave of the hand we care more about the order of magnitude on which an algorithm operates i really don't care about these these uh divided by two and n over two because which of these factors is going to matter as n gets big the bigger the phone book gets the more doors we have the more light bulbs we have the more numbers we have on the shelf n is going to keep getting bigger and bigger and bigger and given that which is the dominant factor raunching if we could call in someone here which of these factors n squared divided by 2 or n divided by two really matters in the long run as our problems get bigger and bigger as n gets bigger and bigger which of those factors mathematically uh dominates annika oh it's annika annika um it would be the no problem it would be the n squared yeah n squared right if you take any number for n and you square it that's going to be bigger certainly in the long run than just doing n divided by two and so with our big o notation we could describe the running time of brian's selection sort implementation as ah it's on the order of n squared yes i'm ignoring some numbers and yes if we really wanted to be nitpicky and count up every single step that brian took yes it's n squared divided by two plus n over two but again if you think about the problem over time and n getting really large sort of facebook size twitter size google size what's really going to dominate mathematically is this this bigger factor here that's what's going to make the total number of steps way bigger than just those smaller ordered terms so in big o notation selection sort would seem to be on the order of n squared so if we consider our chart from before where we had the upper bounds on our searching algorithms both linear and binary this one unfortunately is at really the tip top of this particular list of running times and there's infinitely many more these are just a subset of the more common formulas that a computer scientist might use and think about selection sort is kind of a top the list and being number one on this list is bad n squared is certainly much slower than say big o of one which of course was constant time or one step so i wonder if we could be if we could do a little better i wonder if we could do a little better um and peter actually did say something else earlier which was about like uh comparing two numbers and and fixing problems and if i can kind of run with that let me propose that we brian return to you for a look at an algorithm that might be called instead uh bubble sort bubble sort being a different algorithm this one that tries to fix problems more locally so in fact brian if you look at the numbers that are in front of you which you've kindly reset to their original unsorted location i feel like this really if we focus on just pairs of numbers it's just a lot of small numbers like last time we tried to solve the big problem in sorting the whole thing what if we just look at pairs of numbers that are adjacent to one another can we maybe make some little tweaks and change our algorithm fundamentally so for instance brian six and three what can you what observation can you make there for us yeah sure so six and three that's the first pair of numbers in the array and if i want the array to be sorted i want these smaller numbers to be on the left and the bigger numbers to be on the right so just looking at this pair i can tell you that the six and three are out of order the three should be on the left and the six should be on the right all right so let's go ahead and do that and go ahead and fix that by swapping those two and just fix a small little problem and now let's repeat this process right loops seem to be omnipresent in a lot of our algorithms so six and eight is the next such pair what do you want what do you think about those that particular pair seems okay because the six is smaller and it's already on the left side so i think i can leave this pair alone all right how about eight and five uh the eight is bigger than the five so i'm going to swap these two the five should be on the left of the eight all right and eight and two same thing here the eight is bigger so the eight's gonna be swapped with the two all right eight and seven the eight is bigger than the seven so the eight i should switch with the seven all right eight and four eight and four same thing eight is bigger than the four and eight and one i can do it one last time the eight's bigger than the one and i've made that swap and with a nice dramatic flourish if you step off to the side voila not sorted in fact it doesn't really look all that much better but i do think brian's done something smart here brian can you speak to at least some of the marginal improvements that you've made yeah so there are some improvements at least the one originally was all the way at the very end and it moved back one spot and the other improvement i think is that the eight originally was way over here on the left side of the array somewhere but because the eight is the biggest number i kept switching it over and over again until it made it all the way to the end and so now actually i think this eight is in the correct place it's the biggest number and it ended up moving its way all the way to the right side of the array yeah and this is where this algorithm that we'll see the rest of in just a moment gets its name bubble sort alludes to the fact that the biggest numbers start bubbling their way up to the top of or the end of the list at the at the right-hand side of the shelf as brian notes but notice as brian does too the number one only moved over one position so there's clearly more work to be done and that's obvious from the other numbers being mis-ordered as well but we have improved things the eight is in place and one is closer to being in place so how might we proceed next well brian let's continue to solve some small bite-sized problems let's start at the beginning again three and six sure the three and the six those seem to be in order so i'll leave those alone six and five six and five are out of the order so i'll go ahead and take the six and put it to the right six and two those are out of order as well so i'll swap the two and the six six and seven six and seven are okay they're in order seven and four those are out of order so i'll switch the four and the seven seven and one and those two are out of order as well so i'll swap those and now i think the seven has made its way to the sorted position as well indeed so now we're making some progress seven has bubbled its way up to the top of the list stopping just before the eight whereas the one has continued its advance to its correct location so i bet brian if we keep doing this again and again and again so long as the list remains in part unsorted i think we'll probably get to the finish line do you want to take it from here and sort the rest yeah sure so i just repeat the process again the three and the five are okay and the two and the five are out of order so i'll swap them the five and the six those are fine as a pair the six and the four are out of order relative to each other so i'll switch those and and the six and the one those are out of order as well so i'll swap those and now the six that i can say is in its correct position and i'll repeat it again the three and the two are out of order so those get switched the three and the five are okay the five and the four are out of order so those get switched and then the five and the one need to be switched as well so there's the five inserted position and now i'm left with these four the two and the three are okay the three and the four are okay but the four and the one are out of order so those get switched and now the four that's in its place the two and the three are okay but the three and the one are not so i'll swap those and now the three goes into its sorted place and then finally the last pair to consider is just the two and the one uh those are out of order so i'll swap those now the two's in place and one is the only remaining number so i can say that that one's in place two and now i think we have a sorted array again nice so it felt like this was a fundamentally different approach but we still got to the same end point so that really now invites the question as to whether bubble sort was better or worse or maybe no different but notice too that we've solved the same problem fundamentally differently the first time we took the more human natural intuition of just find the smallest element all right do it again do it again do it again this time we sort of viewed the problem through a different lens and we thought about it would seem what does it mean for the list to be unsorted as peter noted it's when things are out of order like that very basic primitive where something is out of order suggests an opportunity to solve the problem that way just fix all of the tiny bite-size problems and it would seem that using a loop if we repeat that intuition it's going to pay off eventually by fixing fixing fixing fixing all of the little problems until the big one itself would seem to go away well let me return to the visualization from before re-randomize the bars short bar is small number big bar is big number and let me go ahead and run the bubble sort algorithm this time with this visualization and you'll notice now sweeping from left to right are two colored bars that represent the comparison of two adjacent numbers again and again and again and you'll see this time that the bars are being a little smart and they're not going all the way to the end every time just like brian illuminated the numbers and stopped looking at the eight and the seven and the six once they were in place but he and this visualization do indeed keep returning to the beginning doing another pass another pass and another pass so if we think ahead to the analysis of this algorithm it sort of invites us to consider well how many total comparisons are there this time it would seem that the very first time through the bars or equivalently the very first time through the shelf brian in this visualization did like n minus one comparison so n minus one comparisons from left to right out of n elements you can compare n minus 1 adjacencies after that it was n minus 2 n minus 3 n minus 4 and minus 5 until just 2 or 1 remains and at that point you're done so even though this algorithm fundamentally took a different approach and achieved the same goal it sorted the elements successfully let's consider how it was implemented in code and whether it's actually a little faster or a little slower and let's set one final bar in fact two earlier we considered only the upper bound on selection sort just so that we have something to compare this against let's also consider for a moment what the running time is of selection sort in terms of a lower bound best case scenario with selection sort if you have n elements and you keep looking for the next smallest element again and again and again it turns out that selection sort is not really our friend here's for instance the chart of where we left off in terms of omega and notation before linear search and binary search could very well get lucky and take just one step if you happen to open a door and voila the number you're looking for is already there but with selection sort as we've implemented it both with brian and with the visualization unfortunately it's none so good with the lower bound why well brian pretty naively every time he searched for a number started the left and went all the way to the right started the left one all the way to the right to be fair he did ignore the numbers that were already in place so we didn't keep looking at the one he didn't keep looking at the two once they were in place but he did keep repeating himself again and again touching those numbers multiple times each so again even though you and i the humans could look at those numbers and be like obviously there's the one obviously there's the two obviously there's the three brian had to do it much more methodically and in fact even if that list of numbers were perfectly sorted he would have wasted just as much time in fact brian if you don't mind could you quickly sort all eight numbers again brian if we start with a sorted list this is kind of a nice perversion to consider if you will algorithmically when analyzing an algorithm sometimes you want to consider best cases and worst cases and there would seem to be nothing better than heck the list is already sorted you got lucky there's really no work to be done the worst case is the list is maybe completely backwards and that's a huge amount of work to be done unfortunately selection sort doesn't really optimize for that lucky case where they're already sorted so brian i see you've resorted the numbers for us from left to right if we were to re-execute selection sort as before how would you go about finding the smallest number so we decided earlier that to find the smallest number i need to look at all the numbers from left to right in the array and each time check to see if i found something smaller so i would start with the one that's the smallest thing i've seen so far but i would have to keep looking because maybe there's a zero or a negative number later on i need to check to see if there's anything smaller so i would check the two is bigger the three four five six seven 8 they're all bigger so it turns out i was right all along the 1 was the smallest number and it's already in place so now that number is in place and then to find the next smallest number what would you have done i would do the same thing 2 is the smallest number i've found so far and then i would look through all the rest to see if there's anything smaller than the two and i would look at three four five six seven eight nothing smaller than the two so i'd go back to the two and say okay that number must now be in its sorted position indeed and that story would be the same for the three for the four the for the five like nowhere in selection sort pseudo code or actual code is there any sort of intelligence of if the numbers are already sorted quit like there was no opportunity to short circuit and abort that algorithm earlier brian would literally be doing the same work whether they're all sorted from the get-go or completely unsorted and even backwards and so selection sort doesn't really perform very highly so now we're hoping bubble sort indeed does so toward that end let's take a look at some proposed pseudo code for bubble sort assuming that the input is is anything whether sorted or unsorted the pseudo code is always going to look like this report repeat until sorted for i from 0 to n minus 2 now what does this mean 0 to n minus 1 goes from the first element to the last so 0 to n minus 2 goes from the first element to the second to last why am i doing that we'll see in just a moment the condition inside of this loop is if the i and the i plus 1 elements are out of order swap them so this is me being a little clever if you think about all of these numbers as being in an array or behind doors if you iterate from zero to n minus two that's like going from the first door to the second to last door but that's good because my condition is checking door i and i plus 1. so if i start at the beginning here and i only iterate up to this door that's a good thing because when i compare door i and i plus 1 at the very end i'm going to compare door i and i plus 1. what i don't want to do is compare this door i against door i plus 1 which doesn't even exist and indeed that's going to be an error that probably all of you make at some point going beyond the boundary of an array touching memory that is going one or more spaces too far in the array even though you didn't allocate memory for it so this hedges against that possibility so this would seem to be a pretty smart algorithm but as written it's not actually as performant as might be ideal with bubble sort suppose the list were entirely sorted brian not to make you uh sort and resort numbers too many times do you mind giving us a sorted list one more time real quick in a moment i want to see if we consider that same sorted list as before this time with bubble sort can we do fundamentally better i have this code saying repeat until sorted so how might this change so brian you've got the sorted numbers again this should be a good case but selection sort did not benefit from this in input even though we could have gotten lucky bubble sort what would your thought process be here so the thought process for bubble sort was to go through each of the pairs one at a time and see if i need to make a swap for that particular pair so i'd look at the one and the two if those two are okay i don't need to swap them the two and the three are okay i don't need to make a swap there the three and the four are okay the four and the five are okay same with the five and the six and the six and the seven and the seven and the eight so i made it way my way through all the entire array and i never needed to make any swap because every pair that i looked at they were already in the correct order relative to each other indeed and so it would be foolish and so obvious this time if brian literally retraced those steps and did it again with n minus one elements and then did it again with n minus two elements i mean if he didn't do any work any swaps the first pass he's literally wasting his own time by even doing another pass or another pass and so that's kind of implicit in the pseudocode this repeat until sorted even though it doesn't translate perfectly into a for loop or a while loop in c it kind of says intuitively what he should do repeat until sorted brian has already identified the fact by nature of him not having made any swaps that this list is sorted therefore he can just stop and this loop does not have to continue again and again we can map this to c light code a little more explicitly we can by default say do the following n minus 1 times because among n elements you can look at n minus 1 total pairs from left to right without going too far but notice i can add an additional line of code here which might say if no swaps quit from the algorithm altogether so so long as brian is keeping track of how many swaps he made or didn't make through one pass as with a variable called counter or whatever he can simply abort this algorithm early and certainly then save us some time so with that said let's consider for just a moment what the running time of bubble sort might be in terms of an upper bound in the worst case if you will well in the case of bubble sort notice with the pseudo code where we're doing something n minus 1 times and inside of that we're doing something n minus 1 time so again repeat n minus 1 times literally says do the following n minus 1 times the for loop here which is just a different way in pseudocode of expressing a similar idea but giving us a variable this time for i from 0 to n minus 1 n minus 2 is a total number of n minus 1 comparisons so this is an n minus 1 thing inside the repeat and an n minus 1 outside the repeat so i think what that gives me is n minus 1 things times n minus 1 times so now if i just kind of foil this sort of in high school or middle school math n squared minus 1n minus 1n plus 1. we can combine like terms n squared minus 2n plus 1. but per our discussion earlier this is really getting into the weeds who cares about the 2n or the 1 the dominant factor as n gets large is definitely going to be the n squared so it would seem that bubble sword if you actually do out the math and the formulas is going to have an upper bound of n squared or rather on the order of n squared steps so in that sense it is equivalent to selection sort it is no better fundamentally it's what we would say asymptotically equivalent that is as n gets really large this formula is for all intents and purposes equivalent to the selection sort formula even though they differed slightly in in terms of their lower order terms for all intents and purposes ah they're on the order of n squared both but if we consider a lower bound perhaps even though bubble sort has the same upper bound running time if we consider a lower bound as with this smarter code where brian might actually have the wherewithal to notice wait a minute i didn't do any swaps i'm just going to exit out of this looping premature early not even prematurely but early because it would be fruitless to keep doing more and more work we can then whittle down this running time i think not quite as good as omega of one which was constant time like you cannot conclude definitively that an array is sorted unless you minimally look at all of the elements once so constant time is completely naive and unrealistic you can't look at one element or two or three and say yes this is sorted you've got to obviously look at all of the elements at least once so this would seem to suggest that the omega notation for that is the lower bound on bubble sorts running time if we're clever and don't retrace our steps unnecessarily is in omega of n or technically it's n minus one steps right because if you've got n elements and you compare these two these two these two these two that's n minus one total comparisons but who cares about the minus one it's on the order of n or omega of n notation here so to recap selection sort selects the next smallest element again and again and again unfortunately based on how it's implemented in pseudocode and actual code it's in big o of n squared but it's also an omega of n squared which means it's always going to take the same amount of time asymptotically that is as n gets large unfortunately two bubble sort is no better it would seem uh in terms of the upper bound it's going to take as many as n squared steps too but it's at least marginally better when it comes to using something like an input that's already sorted it can self short circuit and not waste time but honestly n squared is bad like n squared is really going to add up quickly if you've got n squared and n is a million or n is a billion i mean my god that's a lot of zeros that's a lot of steps in the total running time of your algorithm can we do better can we do better and it turns out we can and we'll consider one final algorithm today that does fundamentally better just like in week zero we sort of latched on to binary search and again today is just fundamentally better than linear search by an order of magnitude so to speak its picture representation was fundamentally different i think we can do fundamentally better than bubble sort and selection sort and so while both bubble sort and selection sort might be the sort of thing that i was using in grad school just to rip up the code quickly and then go to sleep it's not going to work well for very large data sets and frankly it wouldn't have worked well if i didn't want to just sleep through the problem rather we want to do things as efficiently as we can from the get-go and let me propose that we leverage a technique and this is a technique that you can use in almost any programming language c among them known as recursion and recursion quite simply is the ability for a function to call itself up until now we have not seen any examples of this we've seen functions calling other functions maine keeps calling printf maine has started to call sterling maine called stir comp compare earlier today but we've never seen maine called maine and people don't do that so that's not going to solve a problem but we can implement our own functions and have our own functions call themselves now this would seem to be a bad idea in principle if a function calls itself my god where does it end it would seem to just do something forever and then something bad probably happens and it could and that's the danger of using recursion you can screw it up easily but it's also a very powerful technique because it allows us to think about potential solutions to problems in a very interesting and dare say elegant way so we're not only going to be able to achieve correctness but also better design because of better efficiency it would seem here so let me propose this recall this code from week zero which was the pseudo code for finding someone in a phone book and recall that among the features of this pseudocode where these lines here go back to line three and we describe those in week zero as being representative of loops uh a programming construct that has something happen again and again but you know what there's a missed opportunity here in this pseudocode to use a technique known as recursion this implementation is what we do call iterative it is purely loop-based it tells me literally go back to this line go back to this line go back to this line there's no calling yourself but what if i changed week 0 pseudo code to be a little more like this let me go ahead and get rid of not just that one line but two lines in both of those conditions and let me quite simply say instead of open to the middle of the left half of the book and then go back to line three or open to the middle of the right half of the book and then go back to line three why don't i just more elegantly say search left half of book search right half of book now immediately i can shorten the code a little bit but i claim that by just saying search left half of book and search right half of book i claim that this is enough information to implement the very same algorithm but it's not using a loop per se it's going to induce me the human or me the computer to do something again and again but there's other ways to do things again and again not by way of a for loop or a while loop or a do while loop or a repeat block or a forever block you can actually use recursion and recursion again is this technique where a function can call itself and if we consider after all the pseudo code we are looking at is the pseudo code for searching and on line seven and nine now i am literally saying search left half of book and search right half of book this is already even in pseudocode form an example of recursion here i have in 11 lines of code an algorithm or a function that searches a phone book in line seven and nine i have a lines of code that literally say search a phone book but more specifically search half of the phone book and that's where if recursion really works its magic it would be foolish and incorrect and completely counterproductive to just have a function call itself with the same input with the same input with the same input because you'd have to be kind of crazy to expect different output if the input is constantly the same but that's not what we did in week zero and that's not what we're doing now if you use the same function or equivalently algorithm but change the input to be smaller and smaller and smaller it's probably okay that a function is calling itself so long as you have at least one line of code in there that very intelligently says if you're out of doors if you're out of phone book pages quit you need to have a so-called base case you need some line of code that's going to notice wait a minute there's no more problem to be solved quit now and so how can we map this to actual code well let's consider something very familiar from week one recall when you reconstructed one of mario's pyramids looked a little something like this and let's consider that this is a pyramid of blocks of bricks that's of height four y4 well there's uh one then two then three then four bricks from top to bottom so the total height here is four but let me ask the question a little naively how do you go about creating or how do you go about printing a pyramid of height four well it turns out that this simple mario pyramid that's ever more clear if we get rid of the unnecessary background is a recursive structure of some sort it's a recursive physical structure why well notice that this structure this brick this pyramid is kind of defined in terms of itself why well how do you make a pyramid of height four i would argue a little obnoxiously a little circularly well you create a pyramid of height three and then you add an additional row of bricks all right well let's continue that logic all right fine how do you build a pyramid of height three well you sort of smile and say well you build a pyramid of height too and then you add one more layer all right fine how do you build a pyramid of height two well you build a pyramid of height one and then you add one more layer well how do you build a pyramid of height one well you just put the stupid like brick down you have a base case where you sort of state the obvious and just do something once you hard code the logic but notice what's kind of mind-bending or kind of obnoxious in a human interaction like you're just defining the answer in terms of itself i keep saying the same thing but that's okay because the pyramid keeps getting smaller and smaller and smaller until i can handle that one special case and so we can do this just for fun with these little cardboard bricks here for instance if i want to build a pyramid of height four how do i do it well i can build a pyramid of height three all right let me go ahead and build a pyramid of height three uh how do i build a pyramid of height three all right well i build a pyramid of height two and then i add to it well okay how do i build a pyramid of height two all right well you build a pyramid of height one how do i do that well you just put the brick down and so here's where things kind of bottom out and it's no longer a cyclical argument you eventually just do some actual work but in my mind i have to remember all of the instructions you just gave me or i gave myself i had to build a pyramid of height four no three nope two nope one now i'm actually doing that so here's the pyramid of height one how do i now build the pyramid of height two well rewind in the story to build a pyramid of height two you build a pyramid of height one and then you add one more layer so i think to add one more layer i essentially need to do this all right now i have a pyramid of height two but wait a minute the story began with how do i build a pyramid of height 3 well you take a pyramid of pipe 2 which i have here and you add an additional layer so i've got to build this additional layer i'm going to go ahead and give myself the layer the layer the layer and then i'm going to put the original pyramid of height 2 on top of it and voila it's a pyramid of height 3 now well how did i get here well let me keep rewinding in the story the very first question i asked myself was how do you build a pyramid of height 4 well the answer was build a pyramid of height three great that's done then add one additional layer and if i had more hands i could do this a little more elegantly but let me go ahead and just lay this out here's the new level of height three and now i'm going to go of with four now i'm gonna go and put the pyramid of height three on top of it until voila i have this form here of mario's pyramid so it's a bit cyclical in that every time i ask myself to build a pyramid of a certain height i kind of punted and said no build a pyramid of this height no build a pyramid of this height no build a pyramid of this height but the magic of that algorithm was that there was constantly this do a little more work build a layer do a little more work build a layer and it's in that implicit building of layer after layer after layer that the pyramid itself the end goal actually emerges so you could implement the same thing with a for loop or a while loop and frankly you did it was a slightly different shape for problem set one but you did the same thing using a loop and you kind of had to do it that way at least as we prescribed it because with printf you have to print from the top of the screen to the bottom like we haven't shown you a technique yet to sort of print a layer and then go back on top so i'm kind of taking some real world liberties here by lifting these things up and moving them around you would have to be a little more clever in code but the idea is the same and so even physical objects like this can have some recursive definition to them and so we present this sort of goofy example because this notion of recursion is sort of a fundamental programming technique that you can leverage now to solve problems in a fundamentally different way and i think for this we need one final visualization of merge sort with both brian's help and the computers and merge sort is going to be an algorithm whose pseudo code is dare say the simplest we've seen thus far but deceptively simple the pseudo code for merge sort quite simply is this sort the left half of numbers sort the right half of numbers merge the sorted halves and notice even at first glance this feels kind of unfair like here's an algorithm for sorting and yet i'm literally using the word sort in my algorithm for sorting it's like in english if you're asked to define a word and you literally use the word in the definition like that rarely flies because you're just sort of making a circular argument but in code it's okay so long as there's one special step that's doing something a little differently and so long as the problem keeps getting smaller and smaller and indeed it is this pseudo code is not saying sort the numbers sort the numbers sort the numbers no it's dividing the problem in half and then solving the other half as well so it's shrinking the problem on each iteration now i will disclaim we're going to need that so-called base case again i'm going to have to do something stupid but necessary and say if there's only one number quit it's sorted that's the so-called base case the recursive case is where the function calls itself but this is indeed our third and final sorting algorithm called merge sort and we'll focus here really on the juiciest pieces one this notion of merging so in fact brian can we cut over to you just so we can define before we look at the merge sort algorithm itself what do we even mean when we say merge sorted have so for instance brian has on his shelf here two arrays of size four in the first array on the left are four integers three five six eight and in the right side in another array of size four is our four numbers two one two four seven notice both the left is sorted and the right is sorted but now brian i would like you to merge these sorted halves tell us what that means sure so if i have a left half that's sorted from smallest to largest and have a right half that's also sorted from smallest to largest i want to merge them into a new list that has all of the same numbers also from smallest to largest and i guess where i could start here is that the smallest number of the combined array needs to begin with either the smallest number of the left half or the smallest number of the right half because on the left the smallest number is the three and on the right the smallest number is the one one of those two has got to be the smallest number for the entire array and between the three and the one the one is smaller so i would take that one and that's going to be the first number the smallest number of the merged two halves and then i guess i would repeat the process again on the left side the smallest number is the three on on the right side the smallest number is the two and between the three and the two the two is smaller so i would take the two and that's going to be the next number so i'm slowly building up this sorted array that is the result of combining these two now i'm comparing the three on the left to the four on the right between the three and the four the three is smaller so we'll take the three and we'll put that one into position now i'm comparing the five on the left with the four on the right between the five and the four the four is smaller so that one goes into position and now i'm comparing the five on the left with the seven on the right the five is smaller so the five goes next next i'm comparing the six on the left with the seven on the right the six is still smaller so that one is going to go next now i'm comparing the eight and the seven the only two numbers left the seven is the smaller between the two so i'll take the seven and put that into place and now i'm only left with one number that hasn't been put into the merging of the two halves and that's the number eight so that number is going to take up the final position and now i've taken these two halves each of which was originally sorted and made one complete array that has all of those numbers in sorted order indeed and consider what we've done we've essentially verbally and physically kind of defined a helper function our own custom function if you will whereby brian has defined what does it mean to merge two arrays specifically merge to sorted arrays because why well that's a building block that i think we're going to want in this merge sort algorithm so just like in actual c code you might have defined a function that does some small task so have we now verbally and physically defined the notion of merging the mind bending part here is that sort left half of numbers and sort right half of numbers is kind of already implemented there's nothing more for brian or me to define all that remains is for us to execute this algorithm focusing especially on these three highlighted lines of code and let me disclaim that of the algorithms we've looked at thus far odds are this will be the one that doesn't really sink in as quickly as the others even if the others might have taken you a moment a day a week to settle in or maybe you're still not quite there yet that's fine merge sort is a bit of a mind-bending one because it seems to sort of work magically but it really just works more intelligently and you'll begin to get more comfortable with harnessing these kinds of primitives so that we can ultimately indeed solve problems more efficiently so brian has kindly put the numbers again on the top shelf and he has put them into their original unsorted order just like for selection sort and bubble sore and brian i'd like to propose now that we execute this merge sort algorithm and if you don't mind all recite allowed at first the few steps so here is one array of size 8 with unsorted numbers the goal is to sort these numbers using merge sort and recall that merge sort essentially is just three steps sort left half short right half merge sorted halves so brian looking at those numbers there could you go ahead and sort the left half of numbers all right so there are eight numbers the left half would be these four numbers so i will sort those except i'm not really sure how do i now sort these four numbers yeah so granted we've seen selection sort we've seen bubble sort but we want to regress to those older slower algorithms brian i can kind of be a little clever here well i'm giving you a sorting algorithm so now you effectively have a smaller problem an array of size four and i'm pretty sure we can use the same algorithm merge sort by sorting left half sorting right half and then merging the sorting hat sorted half so could you go ahead and sort the left half of these four numbers all right so i have these four numbers i want to sort the left half that's these two numbers so now i need to figure out how to sort two numbers all right now us with human intuition might obviously know what we have to do here but again let's apply the algorithm sort left half sort right half merge sorted halves brian could you sort the right half of this array of size two so i got the array of two so i'll first sort the left half of the array of two which is the six and this is where the base case in white on the slide comes into play if only one number quit so brian i can let you off the hook that list of size one with the number six is sorted so that's step one of three done brian could you sort the right half of that array of size two the right half is the number three that's also just one number so that one is done good so think about where we are in the story we've sorted the left half and we've sorted the right half even though it looks like neither brian nor i have done any useful work yet but now the magic happens brian you now have two arrays of size one could you merge them together all right so i'm going gonna merge these two together between the six and the three the three is smaller so that one i'll put there first and then i'll take the six and that one goes next and now i have a sorted array of size two that is now done all right and this is where you now need to start remembering step by step sort of in your brain as the things pile up how did we get to this point we started with a list of size eight we then looked at the left half which was an array of size four we then looked at the left half of that which was an array of size two then two arrays of size one then we merge those two sorted halves so i think now if i rewind in that story brian you need to sort the right half of the left half of the original numbers all right so the left half was these four the right half of the left half is now going to be these two numbers and so now to sort those two i guess i would repeat the process again look at numbers individually i would look at the left half of these two which is the eight that one's done and the five that one's done as well all right so step three of three then is merge those two sorted halves all right so between the eight and the five the five is smaller so that one will go in first and then the eight will go after that and now i have a second array of size two that is also now sorted indeed so here's where you're again you have to remind rewind in your mind's eye i've we've just now sorted the left half and we've sorted the left half and the right half of the left half so i think the third and final step at this part of the story is brian to merge those sorted halves each of which now is of size two all right i have two arrays of size two each of which is sorted that i need to merge so i'm gonna compare the smallest numbers from each i'm gonna compare the three and the five the three is smaller so that one will go in first now between these two arrays i have a six and a five to compare the five is smaller so that one i go next between the six and the eight the six is smaller and i'm left with just the eight so if we go back to the original story of eight numbers that i was sorting i think i have now sorted the left half of the left four numbers from that original array indeed so if you're playing along at home think about you've got all these thoughts probably kind of piling up in your mind that's indeed supposed to be the case and admittedly it's hard to keep track of all of that so we'll let brian now execute this all together doing the same thing now by sorting the right half all the way to completion brian if you could all right so the right half we got four numbers i'm gonna start by sorting the left half of the right half which is these two numbers here to do that i'll repeat the same process sort the left half of these two numbers which is just the two that one's done it's only one number same thing with the right half the seven is only one number so it's done and now i'll merge the sorted halves together between the two and the seven the two is smaller and then the seven so here now is the left half of the right half an array of size two that is sorted and i'll do the same thing with the right half of the right half starting with the left half which is four that's done the one is done and now to merge these two together i'll compare them and say the one is smaller so i'll put the one down and then the four so now i have two sorted arrays each of size two then i now need to backtrack and now merge together to form an array of size four so i'll compare the two and the one between those two the one is smaller then i'll compare the two with the four the two is smaller then i'll compare the seven with the four the four is smaller and then finally i'll just take the seven the last number and put that in the final spot and so now from the original array of eight numbers i've now sorted the left half and i've sorted the right half and now that's brings us to our third and very final step could you brian merge the sorted halves yeah and i think this is actually an example we've seen already and what i'm going to do in order to sort these two halves is just take the smaller number from each half and compare them again and again so between the three and the one the one that's the smallest number so that goes into place then between the three and the two the two is smaller so we'll take that and put that into place now i'm comparing the three with the four so the three that goes next next i'm comparing the 5 with the 4 the 4 is smaller so the 4 goes into place next now i'm comparing the 5 with the 7 the 5 is smaller so that one goes into place i'm next comparing the 6 with the seven so the six is smaller that goes next and now i'm left with two numbers the eight and the seven the seven is the smaller of the two so that one goes next and at this point i only have one number left which is the eight and so that one's going to go into its sorted position at the end of the array indeed so even though it felt like we weren't really doing anything at several points in that story it all sort of come came together when we started merging and merging and merging these lists and it's not an accident that brian was using multiple shelves moving the numbers from top to bottom to make clear just how many times he was effectively dividing that list up we started with a list of eight and we essentially took it to two lists of size four four lists of size two eight lists of size one and while it wasn't exactly in that order if you rewind and analyze all of the steps that's indeed what he did he went from eight to two fours to four twos to eight ones and that's why he moved those numbers from the top shelf down three times from eights to fours to twos to ones so how many times did he move the numbers he moved them three times total and on each of those shelves how many numbers did he have to merge together on each of those shelves he ultimately touched all eight numbers he first inserted the smallest number then the second smallest then the third smallest but unlike selection sort he had smartly already sorted those halves so he was just plucking them off one at a time he wasn't going back and forth back and forth he was constantly taking from the beginning of each of those half lists so on every shelf he was doing let's say n steps because he was merging in all n elements of that shelf but how many times did he merge n elements together well he did that three total times but if you think about binary search and really the process of divide and conquer more generally any time you divide something in half and half in half as he was doing from eights to fours to twos to ones that's a logarithm that's log base two and indeed that is wonderfully the height of this shelf if you have eight elements on the shelf the number of additional shelves brian used three is exactly what you get by doing the math log base two of eight which is to say brian did n things log n times and again with the wave of the hand computer scientist don't bother mentioning the bass uh with big o notation it's suffices just to say log n brian did n things log n times and so if we consider then the asymptotic complexity of this algorithm that is to say the running time of this algorithm in terms of big o notation notice that it performs strictly better than selection sort and bubble sort n times log n and even again if you're a little rusty on logarithms log n we have seen as of week zero in binary search is definitely faster than n steps so n squared is n times n n log n is n times log n which is indeed mathematically better than n squared as with merge sort though if we consider the lower bound notice that bubble sort yes got us as low as omega of n turns out merge sort is a little bit like selection sort in that it doesn't optimize itself and get your out of the algorithm early it's always n log n so it's lower bound omega of n log n and that might not be acceptable sometimes you might have certain data inputs where maybe it tends to be sorted and you don't want to waste time so maybe you'd be okay with bubble sore but honestly as n gets large the probability that the input to your sorting algorithm is just by chance going to be sorted is probably so so low that you're just better off in the general case using an algorithm like merge sort that's n log n always we can see this visually using our bars too and notice just as brian was dividing and conquering the problem in half and half and half and then reconstituting the array by merging those halves you can kind of see that visually here there's a lot more going on and it's going to seem in a moment that everything just kind of magically worked but you can see in the faded purple bars that indeed this is sorting things in halves and then merging those halves together and this visualization was a little different it did not have the luxury of three shelves it just moved top to bottom top to bottom and honestly brian could have been a little more optimal there we wanted to make clear how many total shelves there were but honestly there's no reason he couldn't have just moved the numbers down then back up then back down then back up and indeed that's the price you pay with merge sort even though n log n is better than n squared and ergo merge sort is arguably better than selection sort and bubble sort you pay a price and this speaks to the trade-off i mentioned earlier almost always when you do something better in code or solve a problem more intelligently you have paid a price maybe you spent more time as the human writing the code because it was harder and took more sophistication that is a cost maybe you had to use actually more space brian had to have at least one extra shelf in order to implement merge sort if implementing merge sort in code in c you will need at least a second array to temporarily put the numbers into as you merge things back and forth if you want to be extravagant you can have three separate arrays or four separate arrays but it suffices per the graphical representation of merge sort to just use a second array now that might not seem like such a big deal but implicitly you need twice as much space and that might be a big deal if you've got a million things to sort and you now need two arrays that's two million chunks of memory that you need and maybe that's not tenable so there too there's going to be a trade-off and maybe while slower selection sort of bubble sort maybe it's better because it's a little more efficient with space it's going to depend on what you care about and what you want to optimize for and honestly money is sometimes a factor in the real world maybe it's better to write slightly slower code so that you don't have to buy twice as many servers or twice as much memory for your computer it depends there on what resource is more important your time the computer's time your your your wallet or some other resource all together so we'll continue to see these kinds of trade-offs but perhaps the most mind-blowing thing we can do as we wrap up here share a few visualizations of how these algorithms actually compare and one last piece of jargon is this one final greek symbol theta it turns out that thanks to selection sort and merge sort we can actually apply one more term of art here this theta notation anytime an algorithm has both the same upper bound as its lower bound running time you can actually describe it in just one sentence instead of two in terms of theta notation so because selection sort was in both big o of n squared and omega of n squared you can actually just say ah it's in theta of n squared it's always n squared either in the upper bound or in the lower bound same thing for merge sort it's in theta of n log n we cannot use theta for bubble sort or for binary search or for linear search because they had different upper and lower bounds but let me go ahead now and prepare a final demonstration this time using some random inputs so you'll see here a video comparing selection sort bubble sort and merge sort all together all three of them start with random data but let's just see what it means for an algorithm to be an n squared in the worst case or an n log n in this case instead selection starts on the top bubble sorts on the bottom merge sorts in the middle and would you believe it merge sort is already [Music] done and meanwhile we have some very trendy music we can listen to which is really just there to distract us from the fact at how slow n squared actually is in practice and notice there's not that many bars here there's maybe like a hundred or so bars like n is a hundred that's not even a big value when we're talking about the twitters the facebooks the googles of the world these are trivial sizes and yet my god we're still waiting for selection sort and bubble sort to finish and so you can see here that it really matters when you exercise a little bit more cleverness and you leverage a more efficient algorithm and finally selection sword is done bubble sort's still taking a little longer here and this is going to depend on the input sometimes you can get lucky or unlucky but i think it's convincing that merge sort has won in this case [Music] [Music] [Music] you

Channel: CS50

Views: 204,785

Rating: 4.979599 out of 5

Keywords: cs50, harvard, computer, science, david, j., malan

Id: gR6nycuZKlM

Length: 145min 26sec (8726 seconds)

Published: Thu Dec 31 2020