CS50x 2025 - Lecture 3 - Algorithms

[MUSIC PLAYING] DAVID MALAN: All right, this is CS50, and this is already week 3, our fourth.

And this week's focus is going to be pretty much entirely on algorithms, which is exactly where we started the course, recall back in week 0.

But in one of those algorithms, recall, involved a certain phone book, first physically and then virtually and, indeed, in a phone book, of course, you have all of these names and all of these numbers, presumably alphabetized by first name or last name.

And we looked for someone back then, namely John Harvard, some of whom-- and some of you might have called or texted even perhaps that number at the time.

But recall that among the goals of having that whole conversation about finding John Harvard or anyone in a phone book, digital or otherwise, was to talk about just how good the algorithm was.

It sort of went without saying in week 0 that the algorithm has to be correct.

Otherwise, what's the point of writing it or implementing it in the first place.

But we also talked about design and can you make a better algorithm by thinking a little harder about it, maybe harnessing some of your intuition, and actually speeding things up as we discussed?

So the first algorithm, recall in week 0, one page at a time was perfectly correct, but super slow.

And we described its slope with this straight line here.

And if that phone book had, say, n pages, where n just means number, it was a one-to-one relationship because if you add more pages, you need more steps.

The second algorithm, recall, where I went two pages at a time was twice as fast, so surely better.

Potentially incorrect, though, if John Harvard got sandwiched between two pages, but we proposed to solve that by just doubling back one page if need be if you pass the J section, maybe hit the K section, and therefore, need to go back at least one page.

And that algorithm was fundamentally better.

Its line was fundamentally lower than the first algorithm's one because, of course, it takes half as much time to implement that second algorithm plus one extra step just to double back.

But the third and final algorithm in our very first week together, recall, was that so-called divide and conquer.

And today, we'll give it a name again, binary search-- bi- implying two because we were dividing in half, in half, in half, again and again.

And we got this fundamentally different shape, whereby even if we double the size of the phone book next year-- I proposed maybe Cambridge and Alston here in Massachusetts merging together.

So you go from 1,000 pages to 2,000 pages.

One of you observed that that's not a big deal because you need just one more tear of the phone book to actually take a big bite out of that problem and go from 2,000 to 1,000, then to 500, then to 250, and so forth pages in the phone book.

So this week is really going to be about implementing algorithms, not only correctly but also efficiently and really focusing on design.

There won't be much new syntax in C. We'll

give you a couple of building blocks that solve concrete problems. But this week is really about taking a breather after the past two weeks of fairly new, fairly intensive C code and just solve some new, more sophisticated problems together.

So let's consider how we can go about solving problems involving data.

Case in point, phone books are a good example insofar as they represent a decent-sized data set that ideally is, in fact, sorted alphabetically or otherwise.

And in the real world, we are searching for-- we are sorting information all of the time.

Odds are, within the past hour or so, all of us have used Google or some search engine in some form.

How does Google get us search results like that?

Well, they've probably used some kind of very clever layout in their servers' memory to get us answers really quickly.

So we'll begin to think about, especially when data gets big, how we can use this kind of hardware but use-- and on top of which, we'll write software to solve actual problems. So here, again, is a little black chip on top of what's otherwise called a circuit board or a logic board inside of our Macs, PCs, and phones.

If, though, we abstract this away and just assume that if this big chip here represents like one gigabyte of memory, 1 billion bytes or eight billion bits, well surely we can just arbitrarily but consistently number them, like this is byte 0, this is byte 1, byte 2, dot, dot, dot, byte 1 billion all the way down here in the bottom.

So we can address our memory in this way.

So let's forget about the actual hardware there and now talk about what really is going on inside of the computer's memory, borrowing ideas from last week.

So if this is just a canvas of memory, each of whose squares represents 1 byte of memory, how can we go about laying out information, be it names or numbers or web pages or anything else?

Well, recall that we divvied this memory up into chunks last time, and we call this an array.

And what was key about an array was that it was just a bunch of values back to back to back in memory, so-called contiguous.

And it wasn't a huge deal last week that these things were contiguous in memory back to back to back.

But this week, it's actually going to really matter because of that layout and because of last week's, week 2, that we can actually solve problems efficiently in this week 3.

So, for instance, here are a whole bunch of numbers, and these numbers are stored in an array.

And this array is of size 7, it would seem, because there's 1, 2, 3, 4, 5, 6, 7 numbers in this here array.

And, of course, you and I can see all of these numbers at a glance, with a bird's eye view.

But the catch is that computers technically can only look at one location in memory at a time.

Now that's a bit of a white lie because computers are getting so darn sophisticated nowadays that different types, fancier computers can maybe do multiple things at a time.

But for our model, today, we'll assume that a computer can indeed only look at one location at a time.

So, for instance, if you're searching for the number 50 among all of these values here, well, all of us in a split second can kind of spot it over there, third from the right.

But a computer is going to have to look for it a little more methodically, more algorithmically, if you will, step by step, in order to solve that problem.

So a good mental model to have when it comes to what's going on inside of your computer is that these numbers are, yes, in an array, but they might as well be locked up behind closed doors, whereby in order to see each of those values and find one of them, the computer is metaphorically going to have to open up each of those doors one

at a time, looking, looking, looking for the number that we actually care about.

Now it turns out we can treat this array of closed doors, gym lockers, if you will, much like an array.

So this might be location 0, location 1, location 2, dot, dot, dot, location 6.

To be clear, there's seven doors total, but as always, if you start counting from 0, it's n minus 1, which refers to the rightmost or the last door, so 6 instead of 7.

But there's indeed a total of seven doors here.

Just for parity with the lockers we were able to buy online, you might as well think of these as red doors, behind which are all of those numbers.

So if the goal at hand now is to mimic what's going on inside of a computer, I bet we could figure out how to find information among these doors.

And this is just a problem to be solved in the world of computing.

This is the problem of searching, not surprisingly.

And what does that really mean?

Well, if we go back again to week 0, where this is computer science, this is problem solving, what's the input to this problem?

Well, we have an array of seven doors that might as well be locked up behind these doors.

And we want to get as output a Boolean value, like true or false.

Yes, the number 50 is here or no, it is not.

So true or false respectively will get the job done.

And inside of this, of course, is going to be, as always, some kind of algorithm, step by step instructions for actually solving this problem.

So how, then, would a computer concretely go about searching for numbers behind this door?

Well, maybe just for fun, we went ahead here and printed out some monopoly money, some large versions thereof.

And suppose we want to find very specifically the number or the dollar amount 50 behind one of these doors.

Could we get maybe one, maybe two volunteers to come on up?

I saw your hand go up first, second on the end there.

And let me look over here-- over here, behind the camera, number two, come on down.

OK, come on over.

Maybe a round of applause to break the ice for these two.

[APPLAUSE] Come on up.

And we've got two algorithms ahead of you.

But come on over here.

If you want to introduce yourself to the world-- maybe a quick something about each of you.

STUDENT: Hi, I'm Jonathan.

I'm a sophomore in Cabot House studying economics.

DAVID MALAN: Wonderful.

Nice to meet you.

And-- STUDENT: Hi, I'm Claire.

I'm a junior in Elliott, studying economics and TDM.

DAVID MALAN: All right, nice, wonderful.

Glad to have you both here.

So behind you are seven doors.

And which of you would like to go first?

OK, so first, if you want to come on over here, behind these seven doors are now dollar amounts, namely all of the available monopoly dollar amounts.

And if you want, we want you to find the number 50.

You can go about this in a bunch of ways.

Like, you could go about just opening random doors, but that's not necessarily very repeatable.

That's not very algorithmic step, by step.

So let me propose that you do something super simple.

Start at the left door and work your way to the right.

And just so everyone knows what's going on, go ahead and show the world what number you've pulled out of each of these lockers.

And the first locker is-- STUDENT: 20.

DAVID MALAN: 20.

That is correct-- not 50.

STUDENT: 500.

DAVID MALAN: So incorrect.

STUDENT: 10.

DAVID MALAN: 10.

Not correct.

STUDENT: 5.

DAVID MALAN: Not correct.

STUDENT: 100.

DAVID MALAN: 100.

Not correct.

STUDENT: 1.

DAVID MALAN: 1.

Not correct.

Hopefully last door-- and round of applause, if we could, for finding the number.

[APPLAUSE] So if you don't mind, before we transition to a better algorithm-- because, frankly, that was pretty bad-- but it wasn't incorrect in the sense that he was doing anything wrong.

He sort of just had some bad luck.

And, frankly, if I hadn't sort of led him to that path from left to right, I could have proposed more cleverly that you maybe start from the right and then, boom, the problem would have been solved.

But, in general, if data isn't necessarily cleanly laid out by us humans in this very manipulative approach-- like maybe it's going to be at the beginning of the array.

Maybe it's going to be at the end of the array-- you really don't know.

So you might as well have one methodical approach, step by step, and just do it again and again.

So I think, even though that felt increasingly awkward because you didn't find the 50 till the end, that was kind of as good as you could have done in general.

And let me propose, before we try a second algorithm, if we take a look at some pseudocode here, I daresay what you implemented, with my sort of encouragement, was something called linear search-- literally walking in a line from left to right.

And if we take the fun out of searching for money behind doors, we can make this more algorithmic with pseudocode-- English-like code, but written in very terse language.

He did, for each door from left to right, if 50 is behind the door, ideally, then you would have returned true.

And that's when everyone applauded, of course.

Else, if not, you might return false at the very end of this code.

So we got lucky.

50 was there.

But if you hadn't, you might have decreed, oh, no, there's no 50, so I returned false.

But notice the indentation here, just to highlight a key detail.

I'm only returning false once I'm done with that loop.

For instance, if I had poorly implemented this pseudocode like this, indenting that return false and only doing it conditionally if 50 is not behind the door-- I know we're putting you on the spot here, but do you want to conjecture why this would be bad if you spot the mistake?

STUDENT: If you put false right after else, that means once we search the first door and we don't find 50, it'll just return false and the program will finish.

DAVID MALAN: Exactly.

So this code would indeed be a bad implementation-- incorrect because only if the 50 is behind the first door would it ever work correctly.

We would otherwise bail out and return false prematurely.

So this version here is indeed correct.

But can we do better.

Well, the numbers that were behind the doors for you, were they in any particular order?

STUDENT: No, they were randomized.

DAVID MALAN: So we kind of set you up for failure in that sense.

So if you don't mind, let's go ahead and pass the mic over.

And secretly, behind me a moment ago, Yuliia was kindly sorting all of those same dollar amounts behind the doors.

And the question at hand now for you is going to be find the number 50.

But let's do this a bit like the phone book in week 0, where let's start in the middle.

And if you recall from week 0, then let's go left or right accordingly.

So what's behind the middle door?

And we have-- STUDENT: It's 20.

DAVID MALAN: 20, so not correct.

But what do we now know?

50 is in which direction?

STUDENT: To the right.

DAVID MALAN: All right, so to the right-- so go to the middle of the right.

So that leaves you with these three lockers in that middle door now.

STUDENT: It's 100.

DAVID MALAN: 100, so too big.

So what do you now know?

STUDENT: It's going to be to the left.

DAVID MALAN: Has to be, logically, if it's there at all, in between those two.

And now we get your round of applause much faster than before.

[APPLAUSE] So this, then, if I can step over here before we give you a parting gift, this is where we left things off a moment ago.

And in linear search, line from left to right, we checked each door.

But just to make things a little geekier now and a bit more quantitative in nature, that really is the same thing as slapping numbers on this problem, whereby the first door we're going to call 0.

The last door, we're going to call n minus 1 if we start to treat these lockers not as physical objects, but as arrays instead.

So, in that same spirit, let me propose that when we found the number 50 this time, we took a fundamentally different approach, just like week 0, when we did divide and conquer, a.k.a.

binary search-- binary implying we split the problem in 2 and 2 and 2, by going left or right each time.

And the pseudocode that you might have arguably just implemented looks a little something like this.

If 50 is behind the middle door, well, we got lucky, and we can simply return true right away.

But if it's not, if 50 is less than the value at the middle door, we could have gone left, even though you didn't need to.

Else, if 50 is greater than that of the middle door, we could search right, and you did do that.

But there's a fourth scenario here, and we talked a bit about this in week 0.

Do you spot what other scenario I might want to consider?

If it's either in the middle or to the left or to the right, what else might happen?

So what else might happen?

It was that fourth scenario.

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: So it might not be there at all.

I could have really set you up for failure by not putting the 50 there.

And in code, though, we need to handle that because I conjectured in week 0, when you don't handle all possible scenarios, that's when the computer crashes or freezes or just something goes awry.

So if there are no doors left, you sort of run out of possibilities.

Logically, we had better make sure we return false.

So before we give you both maybe one final round of applause, wonderfully, Monopoly makes its own Harvard edition for Cambridge.

So we have a nice parting gift for both of you today.

Thank you both for coming on up.

[APPLAUSE] All right, so just to now make that algorithm a bit more quantitative, instead of just saying middle, middle, middle, let's use a bit of array syntax here now too.

So this is the same exact pseudocode for that algorithm binary search.

And so the first condition is the same.

If no door is left, just return false.

But if 50 is behind doors bracket middle-- and, again, I'm sort of stealing some syntax from last week, where we introduced square brackets for arrays, but I'm still using pseudocode.

So this isn't C per se, but by doors, I mean the array known as doors.

Bracket middle I mean whatever the middle index is, go there.

If you found it behind the doors bracket middle, return true.

Else, as we enacted a moment ago, if 50 is less than the middle door, then go ahead and search what?

Well, instead of saying search to the left and search to the right, let's make this, again, more precise today.

Search the array of doors from location 0 all the way through location middle minus 1.

So what do I mean by that?

Here was the middle door.

And even though this is not what we did a moment ago, if we were to go left, here's bracket 0, the first door.

Here is middle minus 1 because if this is middle, minus 1 is immediately to the left.

And this is why this algorithm would indeed have a searching the left half.

Equivalently, if 50 is greater than doors bracket middle, then search doors middle plus 1 through doors n minus 1.

Well, the end of an array, if 0 indexed-- that is, you start counting at 0-- this is always n minus 1.

If this is middle, middle plus 1 is here.

And this is exactly what you just did, searching the right half of those doors.

So we have this translation then from of the intuitive pseudocode from week 0 into now the more technical expression of arrays and array syntax here this week.

And that's something now we'll begin to build on over the course of writing and implementing some of these problems here today.

So if we now have algorithms that both solve the same problem, just like in week 0, which of those algorithms was better-- the first one, which we called linear search, or the second one, which we called binary search?

They're both correct, I would claim.

So which is better?

Which is better design?

Two.

And why do you say that?

STUDENT: It's more efficient.

DAVID MALAN: OK, so 2 is more efficient insofar as the second algorithm, if I'm thinking back, only took three steps.

You only had to open up three of the doors, whereas the first algorithm linear search actually took as many as seven steps.

And, in fact, we'll see some math underlying this.

But it would be nice now if we could really compare the design of the efficiency of algorithms a little more rigorously than just saying one is better than the other.

Let's see if we can slap not some numbers on it but maybe just some very simple arithmetic or algebraic formulas that allow us to compare two algorithms so that in the real world and in problem sets and in projects in the future, you can make a more quantitative claim as to which approach is indeed better.

So when we talk about running time, we literally mean that-- like, how much time does it take for a program to run.

But we don't necessarily count in terms of seconds or ticks of a clock more generally.

Instead, we'll try to count the number of operations that an algorithm takes.

So, for instance, this was a way of analyzing the running time of three algorithms way back in week 0.

And I did introduce a bit of jargon, whereby I was using expressions like n to represent n pages or n divided by 2 to represent half as many pages.

And even though I waved my hand at week 0, log base 2 of n is mathematically how you would represent the idea of dividing something in half in half in half if you start with n pages.

So those are three formulas.

But it turns out that at least two of these algorithms from week 0, they're pretty darn similar to one another.

Indeed, literally two of these are straight lines, even though the slope is slightly different.

The other one is fundamentally curved and, therefore, different and, indeed, we saw better.

But let's get out of the business of worrying about maybe constant values, like dividing by 2.

We really want to care about when algorithms are sort of fundamentally better than one or the other.

So case in point, here are those same two algorithms from week 0.

This was turning one page at a time.

This was turning two pages at a time.

Honestly, if I wanted to speed things up by a factor of 2, why don't I just use a faster Mac, a faster PC?

Nowadays, I could literally wait one year, and next year's computer will be practically twice as fast, it would seem, than the first.

And so if we start to try to compare the efficiency of algorithms, it would be nice if they're sort of resilient, those comparisons, to what computer you use to run the code.

We want to take a step back and approach things a little more mathematically, but fairly lightweight nonetheless.

And so the way a computer scientist typically describes the running time of an algorithm is by using a capital O as a letter and using it to imply on the order of this many steps.

And I actually keep saying as a turn of phrase, wave my hand at a problem.

This is the mathematical equivalent of I don't really care about the very precise mathematical formula.

It is roughly on the order of this fast or this slow.

So what this means is that if you want to describe the running time of this algorithm, this one, or this one, syntactically, you literally write on a piece of paper or an essay or the like, big O, and then, in parentheses, a little mathematical formula that describes how the running time relates to the size of the problem, just like this xy grid.

But it turns out, and I'll claim, we rarely care about denominators if they're just constants, like 2 or 3 or 4.

All we care about really is the highest order term.

So whatever the biggest mathematical component is in the expression, the one that really matters as n gets big, that's the one we care about because, frankly, if n is, like, 2 billion pages, 2 billion in size, well, 1 billion still feels pretty darn slow.

If it's going to take that many steps, they might as well be just as slow as each other.

But this one here, similarly, if you remember your logarithms, even the base doesn't matter because you can actually multiply 1 logarithm by a constant to change the base.

And so here, too, we're going to get rid of the specific constant like 2.

And here then is how we would describe the running time.

And, in fact, if you zoom out in your mind's eye and assume that the y-axis is bigger and the x-axis is bigger, if you keep zooming out, zooming out, zooming out, these two lines are actually going to pretty much look the same once you've zoomed out far enough.

And that's what I mean by they're essentially themselves algorithmically the same.

As n gets big, big, big, these might as well be the same algorithms, but this one is clearly not.

And we claimed in week 0 that this one was better.

I claim again today that this one is better.

And now we'll begin to slap some formulas on the evaluation of these algorithms so that we have a better sense of what algorithm is better than someone else's.

And, indeed, in the real world, when you talk about what makes someone a good programmer, what makes someone a good engineer is having an intuitive sense, with practice and with time, of how you should write your code so that it maybe has a better running time than some other algorithm.

Because when you start working at Google or Microsoft or working in medical data sets or financial data sets and the data is really big, n is really big, you probably want to be as efficient as possible.

So this [INAUDIBLE] capital O is generally called big O notation-- not particularly technical, but that's indeed what it's called.

And here, for instance, is a little chart of very common runtimes.

You can use any mathematical expression, but almost always, in the context of computing, at least introductory-type algorithms, this is the list of possibilities, even though there's infinitely many more.

So among the algorithms we've considered thus far, what is the running time of linear search?

Well, it's on the order of n because if there's n doors, like those behind me, in the worst case, consider how many steps might it take me or take you?

It will take n steps, specifically 7, but n in the general case.

And so big O is very commonly used when you do want to think about the worst case because, honestly, who really cares if you got lucky and the first door you opened had the number you're looking for?

That doesn't really generalize.

And that's not a good argument within Google-- well, hey, once in a while, someone will get lucky and we'll really return them a search result quickly.

You want the general case to be fast.

And so linear search, really in the worst case-- like, which customer is going to be the least happy with our Google code?

Linear search describes that-- an upper bound, so to speak, on how many steps it might take.

What about, though, best case running times or lower bounds on how fast an algorithm might be?

Sorry, I should have not spoiled this.

What's the running time of binary search?

If the running time of linear search is big O of n, well, the running time of binary search, by contrast, is going to be log base 2 of n or, more generally, log of n.

She could have gotten lucky, our volunteer, by just opening the middle door and, voila, maybe 50 was there.

It wasn't.

But in the worst case, she only had to look at big O of log n doors in total.

And that gave us roughly three doors in this case.

What if we want to talk about best case running times, just because it would be nice that, in certain situations, how fast can our code actually run?

How good is our algorithm?

Well, in computing, computer scientists use a capital omega symbol to represent a lower bound.

So big O is upper bound.

Big omega is lower bound, and you can use the same kind of mathematical formula.

So here's that little cheat sheet again, but with an omega prefix, which again means lower bound.

And same question-- in linear search, where you look at the doors left to right, in the best case, how few steps might it take to find a number?

I'm seeing just one because we could get lucky, and because we go from left to right, could be that we find the number right away.

So that's in big omega of 1, in this case, one step.

Otherwise, how about binary search?

What's the lower bound on how quickly we might find a value?

Same thing, right, because we could just get lucky because, by starting in the middle, it might happen to be right there.

So the lower bound on binary search, too, also happens to be in big O of 1 because we just simply get lucky.

What if those two are one and the same?

One last piece of Greek symbology here-- capital theta here is used when big O and omega are exactly the same thing, which won't always apply, but sometimes, an algorithm performs at this rate as well as at this rate, and they're one and the same depending on the algorithm itself.

So here's a little cheat sheet here.

And how about linear search?

So linear search, in the best case, takes only one step-- in the worst case, takes as many as n steps.

So those are not really one and the same.

So theta is really inapplicable here.

And binary search, too, this is sort of inapplicable because in the best case, it might take me one step, hence the big omega of 1.

But in the worst case, and it's not even that bad, it might take me big O of log n.

So theta doesn't apply here.

But we'll keep an eye out today and see if there aren't certain algorithms that we'll look at that might actually have those values being one and the same.

And all of this symbology-- and that's it really for definitions for now-- is what's generally called asymptotic notation.

It's notation that you use when talking about the running time of algorithms over time.

As the input gets larger and larger and larger, how do these algorithms perform?

How can you measure their efficiency?

Any questions on big O, omega, or anything prior?

We'll come back to theta before long.

Any questions?

Yeah, have in front.

STUDENT: [INAUDIBLE] DAVID MALAN: Sorry, say again.

STUDENT: [INAUDIBLE] DAVID MALAN: Is binary search efficient with respect to-- STUDENT: When searching [INAUDIBLE] DAVID MALAN: Oh, really good question-- is binary search efficient when searching random data as was the case with our first set of doors?

And, indeed, those numbers were all over the place.

They were not sorted from smallest to largest or largest to smallest.

So what is the answer to that?

Is binary search efficient when the data is random?

STUDENT: It doesn't work at all.

DAVID MALAN: It doesn't work at all.

And so that was the hidden cost of the two algorithms that we acted out.

And, literally, I had Yuliia come up and help me.

She did more work to enable us to use binary search because only for the second exercise with the lockers was the data actually sorted.

So binary search just does not work if the data is random because you would open a door, see a number, like the number 20, and now you would make a decision whether to go left or right based on the number you've seen.

So you simply cannot use binary search when the data is unsorted, a.k.a.

random.

In that case, then, how do you sort the data-- that's going to be one of the problems we solve ultimately today-- get the data sorted, help Googles of the world, sort their data first so that we can find web pages and other things more quickly.

Yeah, in back-- oh, any questions?

No?

All right, so let's actually translate some of this to a little bit of code here.

How can we go about implementing something like linear search?

Well, let me do this.

Let me go over to VS Code here.

Let me propose to create a new program called search.c.

So I'm going to do code search.c.

And in here, I'm going to use the CS50 library at the top so I can get input.

I'm going to use stdio.h so I can print stuff out on the screen.

I'm going to use int main(void) because, for today, I don't really care about command line arguments for this particular program.

And let me start with an array of values.

Suppose I want to implement, in code, the idea of these lockers containing those random values initially and implement, in C, the very first algorithm we enacted with our volunteers, which was searching from left to right.

Well, it turns out, in C, I can create an array, recall, by saying I want integers, I want the array to be called numbers, and then, inside of square brackets, I can specify how many elements I want.

Maybe I want three, like last week.

But, in this case, I think I want seven this week to represent each of these lockers.

But it turns out, you can initialize an array.

Without even using get_int or the like, you can just specify an empty square brackets that whole array should equal the following inside of curly braces.

So this is one new use of curly braces, but it's a handy trick when you want to create an array that has specific values, like 20, 500, 10, 5, 100, 1, and 50, which just happens to be the exact order in which the dollar amounts previously were behind those lockers.

So what does this line 6 do at the moment?

It creates for me an array of size 7 and initializes it to that sequence of values from left to right.

It is not strictly necessary to bother putting 7 there, and it's probably best not to because the computer, specifically the compiler, will figure out how big the array should be based on what you typed inside of those curly braces, and you're just inviting a mistake if you put a number over here that's supposed to match the total over here.

At some point, you're probably going to error.

So if that gives me then an array of size 7.

Let me go ahead and ask the user, what number do you want to search for, much like I verbalized before?

So int n equals get_int, and I'll prompt the human for a number as with this kind of prompt.

How do I now implement linear search?

Well, based on the constructs we explored in week 0 and week 1, we had conditionals and loops and variables and Boolean expressions and the like.

What is probably the feature of a programming language that we're going to need to search from left to right to implement linear search?

STUDENT: A for loop.

DAVID MALAN: A for loop, probably, or a while loop, but a loop in general.

Why?

Because I could use, like, seven conditionals, and I could say, if the numbers bracket 0 equals equals this value, then return true.

Else, if numbers bracket 1 equals equals this number, then return true.

But that's not very general purpose.

If we're going to have all of these conditionals, let's just have one that asks the same question by just changing some variable.

And a for loop is often the paradigm.

So for int i equals 0, i is less than 7, i plus plus, and this code alone sort of sets me up to implement what our first volunteer did from left to right with the lockers.

What's the question I want to ask?

Well, does the array of numbers at the current location i equal equal the number n that we're actually looking for?

So does the number behind the first door, second door, third door actually equal 50, for instance, or whatever's typed in?

And, if so, let's go ahead and print out something clear, like "Found" backslash n-- else, I don't think I want to do this-- printf "Not found."

So let me, for a moment, sort of poorly implement this.

What have I done wrong with this code?

Yeah, in the back.

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, I don't want the-- I want the if inside for loop but not the else inside for loop.

Why?

Because that would be the equivalent of starting at i equals 0, opening the door, and then concluding I have found or not found the number without even allowing us a chance to keep going because we're going to spit out, unilaterally, "Not found," even though we just haven't found it yet.

So I don't think I want to do that.

But I think what I can do, for instance, is as per the slide a bit ago, if I, at the end of my loop, get all this way, then I think I can print not found.

But I think, logically, even this might be imperfect.

So let me go ahead here and do make search Enter.

Seems to have compiled OK, so no syntax errors.

Dot slash search Enter-- what number do I want to search for?

I'm going to go ahead type 50 and hit Enter.

And still, I have a logical bug.

It's saying "Found" but also "Not found."

Why?

Even though I moved that line of code outside the loop, which is correct, but there's still something wrong here.

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, the iteration still ends up leading us to this final line.

Why?

Because we're going to go all the way from 0 to the end of the array again and again and again, hopefully printing out found when we find it.

But there's nothing stopping us from then executing line 16 before the program actually ends.

But recall, last week, we had a solution to this.

Even main can return a value.

And even though, in week 1, it was sort of secretly returning the number 0, unbeknownst to us, it turns out, we now had the ability, as of week 2, to explicitly return a value anywhere in main that we want.

And the convention, a little paradoxically, is to return 0 upon success, because that means all is well, and then return anything other than 0, like a positive integer, if anything has gone wrong.

And we use positive integers because it could be this thing that goes wrong, this thing, this other thing.

Lots more can go wrong than can go right when writing code.

So I think what I could do here is, after printing "Found," I could return 0 to signal success, even though the human's not going to see anything different.

And down here, I could actually return 1 to signify failure.

And recall, with the little command trick, I could do dollar sign, question mark, and actually see what that value is.

But, for our purposes, what we really care about is that main returns when we are done solving this problem, either inside of the loop or ultimately outside.

So let me try this again-- make search dot slash search.

Let's search for, again, the number 50, Enter, and indeed, it is "Found" and only "Found."

Let's do this again-- dot slash search.

Let's search for the number 2, which is not in that array.

And I should see and only see "Not found" in this case.

So this then would be the code for linear search.

Any questions on what we just did here?

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: A really good question-- what if we don't initialize the array?

Honestly, in programming, a very good answer to that question is just try it out and see what happens.

So let me create an array of size 7 with no values inside of it.

Let me reopen my terminal window, do make search, and the compiler doesn't seem to mind that.

If I go ahead and now do dot slash search, Enter, I'll be prompted for a number.

I'm going to presume to search for 50, even though I don't know what's in there.

Enter, and at least it was not found here.

Let me go ahead and try again.

Let me search for the number 2-- not actually found.

Search for the number 1-- not actually found.

And I can poke around all day long, but it turns out I'm probably just getting lucky here.

Why?

Well, this loop, no matter what, is going to check seven locations.

But I have not put anything in any of those seven locations.

But recall, from last week, we sometimes saw those garbage values, sort of remnants of memory that, of course, exist, but maybe had been used for some other value previously.

At the moment, I think I'm just getting lucky that among the first seven locations in the computer's memory, I just didn't end up with a garbage value 50 or 2 or 1.

But if we played this game for a while, I bet I could come up with a number that actually works.

And let's see, at the risk of a demo not going according to plan, let me do dot slash search.

Let's search for 0-- still not there.

Let's search for 3, 4-- we're going to have to do this all day long to actually find the values.

There's four billion possibilities, but at some point, we would get lucky, and it would say "Found," but only by chance.

So, in short, do not do that, since it is wrong.

Other questions on the code that we've just written?

So let's transition then to maybe a better version of this.

What if the numbers are actually sorted?

And, frankly, what if they're not actually numbers at all?

Let me go back into this code.

Let me throw away the contents of main, and let's do something maybe now with strings instead, just so it's more like searching an actual phonebook.

So I'm going to create an array of strings called strings for lack of a better name, and much like a certain game with which you might now be familiar, we might have a string for battleship and boot and cannon and iron and thimble and top hat, though this does vary by country based on which version of Monopoly you actually have.

Then let's go ahead and prompt the user for a string s, using get_string, and ask them for a string to search for.

And then let's do a for loop again for int i equals 0, i less than 1, 2, 3, 4, 5, 6 values.

I'm hardcoding 6, and I don't like that, but we'll come back to that idea in general of figuring out what the length of that array might be.

But for now, I'm just going to hardcode it.

But that's not, indeed, good practice-- i plus plus inside of the for loop.

Now let me go ahead and do this.

If the i-th string, or the strings at location i, equals equals s, then let me go ahead and print out, as before, "Found."

Let me not make the same mistake as before.

So let me immediately return 0 to signal success.

But if we don't find it anywhere in that array, let's go ahead and print out "Not found."

And then let's go ahead and return 1, just as before.

So the only thing that's different now is I'm using strings instead of integers, but I'm otherwise looking for the i-th string that might very well have the same value as s, what I have typed in.

Let me go ahead and open my terminal again, run make search again-- so far, so good.

Dot slash search-- let's search for maybe the thimble-- Enter.

Huh, it's not found.

All right, maybe it's too far away.

Let's search for again-- battleship Enter.

Not found.

How about the top hat, Enter.

Not found.

And I could do this three more times, but I'll claim that it's never going to find any of these strings.

Does anyone have a suspicion as to why?

Or how we might solve-- why is this not working?

Yeah?

STUDENT: [INAUDIBLE] doesn't work [INAUDIBLE] DAVID MALAN: Yeah, well said.

So it turns out-- and this is super subtle-- equals equals is not how you can compare strings.

And we'll see why, in fact, in greater detail next week.

But for now, equals equals works fine for integers, for longs, for chars, and a bunch of other data types as well.

But it doesn't actually work for strings.

And for today's purposes, it's really because strings can be different lengths, and equals equals is only going to compare two values.

But a string might be three characters, four characters, five characters, depending on how many characters I have typed in.

Equals equals is not powerful enough or wise enough to actually solve that problem.

However, this is such a common thing to do, like in our phones and on Google and the like, to compare strings that humans have typed in that there is, in fact, a solution for this.

And so, in fact, we'll introduce today another function from the string.h header file that we introduced last time.

Recall that inside of string.h was the declaration for strlen, S-T-R-L-E-N, which would figure out the length of a string based on the null character and everything we talked about last week.

But within the same library, as per CS50's documentation, there's another function called str compare, or strcmp for short.

And if you were to pull up the documentation for that particular function, you will see that its prototype actually takes two strings as input called s1 and s2.

So we could call those any two things.

But what's noteworthy about this function is that its return value is sort of ternary.

It can return one of three different things to us.

The function can return an int less than 0 if s2 comes before-- sorry, if s1 comes before s2.

It will return 0 if s1 is the same as s2.

And it will return an int greater than 0 if s1 comes after s2.

So strcmp is more powerful than just saying yes or no, these strings are equal.

It can actually be used to alphabetize strings as well because what it's essentially saying is, alphabetically, s1 comes before s2 or s1 and s2 are the same or s1 comes after s2 alphabetically.

And alphabetically is a bit of a white lie.

It's technically ASCII-betically because what's being used is the ASCII values.

So lowercase characters are going to be treated different from uppercase characters.

So we say ASCII-betically because it's literally comparing the ASCII codes.

But for now, I'm going to avoid that problem by just using lowercase everywhere.

But if I want to use this function, let me go back over to my code here.

And instead of doing equals equals, I have to use a function here called strcmp passing in one string, like strings bracket i.

And then the second argument, a.k.a.

s2, is going to be the string I want to compare against.

But I want to check the return value of that function.

And, again, what value should I check for if I want these things to be equal?

So 0 was the operative return value.

So what I want to do is this.

So this looks, at a glance, way more complicated than it really needs to be.

But all it's doing is calling a function called strcmp, passing in two strings as input, generally known as s1 and s2, comparing them, and if they are exactly the same character for character, left to right, strcmp, per its documentation, will return 0.

I don't care about less than 0 or greater than 0 because I'm not trying to anything, I'm just trying to return true or false, yes or no, we Have found this string.

So to use that function, just like strlen, I need to include string.h at the top.

Let me open my terminal window.

Let me rerun make search-- so far, so good-- dot slash search.

Now let me search for thimble in the exact same array, crossing my fingers, and voila, now we Have found thimble.

And just for kicks, I'll do it twice more.

Battleship, which failed previously, but this time not.

Top hat failed previously but not.

This time, I'll search for something like a car, which is not in the array.

Enter, and that is in fact not found.

So a subtlety because strings, as we'll soon see all the more, are indeed a bit different from just comparing simple values like integers, chars and the like.

Questions on what we just did with strcmp or searching for this thing linearly in this way?

All right, well, why don't we graduate to more of a actual phone book?

Right now, I'm just kind of searching for arbitrary strings.

Let's make something that's a little more involved but uses these exact same ideas.

Let me go ahead and code up a file called phonebook.c.

At the top of the file, I'm going to include those exact same files-- so include cs50.h, include stdio.h, include proactively this time string.h.

include cs50.h, include stdio.h, include proactively this time string.h.

I'm going to create my main function, no need for command line arguments today.

Inside of main, I'm going to give myself now two arrays just so we actually have both names and numbers.

So, for instance, I'm going to do this-- an array of string called names.

And in that array, I'm going to have three of us.

So inside of curly braces, I'll have Yuliia, who kindly volunteered earlier as well, me, and how about John Harvard, as always, whose number we'll search for.

Then let me go ahead and keep track of not just the names in this phone book, but also the numbers, so string numbers and then equals.

And then the numbers I'm going to put here are going to be, for instance, how about plus +1-617-495-1000.

and I will have the same Harvard directory number, so +1-617-495-1000.

And then John Harvard will have his old number, +1-949-468-2750, which just for an Easter egg, you're welcome to text or call sometime.

So now I have two parallel arrays, if you will, from left to right, that are both mapping names in one array to numbers in the second array.

And, actually, if I want to keep this thing sorted, that's kind of on me, and I don't really care about that for now.

But if I want to this, notice that I'm actually going to need to move Yuliia's name there and move Yuliia's number to the end here.

But otherwise, we still have an array of size 3 for each of names and numbers.

Let's go ahead now and search for someone's name and, therefore, find their number.

So let's prompt the user for a string called name using get_string and ask them, what name do you want to search for in this phone book?

Just like before, let's use linear search to keep it simple.

For int i equals 0 I less than 3 this time, because there's three people involved, i plus plus.

Then, inside of this for loop, let's do the same correct technique as before.

If the return value of strcmp, passing in two values-- what are the two values I want to pass into strcmp here in order to check if we have found a person's name?

What could the first one be?

Feel free to shout it out.

What am I searching for?

The user's typed in name.

But I want to compare it against?

Yeah, I think names bracket i.

So if the i-th name is the same thing as the name the human typed in, and I know that because strcmp will return 0 for me, then I can go ahead and say, just as before, "Found."

And just for kicks now, let's go ahead and actually print out what that person's number is rather than just say, found, quote unquote, by outputting numbers bracket i.

So this is to say, if we find in names bracket i the person's name that we're searching for, then go ahead and print out that same person i's number.

And so that we don't accidentally say not found later, let's return 0 immediately.

Otherwise, down here, let's say not found with no number, of course, and then return 1 to signify error.

So if I hide my terminal window, this is a simple implementation of a phone book on an iPhone or on an Android phone when you're searching for your contacts, top to bottom or left to right.

So let me go ahead and run this in my terminal.

I'll do make phonebook, Enter.

So far, so good.

Dot slash phonebook, and if I search for John by his name, properly capitalized, Enter, I indeed found John Harvard's number to be +1-949-468-2750.

This, then, is correct.

What, though, is arguably poorly designed about this program, even if you yourself are still newish to programming?

What's bad about this design here, might you say?

Any instincts?

What's bad?

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: Good.

So I don't like that.

The fact that I'm using this so-called magic number, which means just hardcoding a value that you're trusting is not going to change or that you'll remember to change it, I don't like this.

So that's a really good observation.

What else might you not like instinctively, even if, again, these concepts are new and often-- yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, we're again on the honor system here that we have these two arrays and the onus is on me, the programmer, to make sure that they line up.

And case in point, when I manually went back a moment ago and moved Yuliia to the end of the names array, I had to remember to move her number to the end of the numbers array, and that just strikes me as very fragile, so to speak.

It's just too easy for me or a colleague to screw up this code by forgetting that sort of lower-level detail.

We're just trusting that names and numbers do stay aligned and they have the exact same number of people in them and the exact same numbers of numbers-- exact same number of numbers in them as well.

So we have an opportunity now to do better than this.

And besides arrays, which we've already seen do solve a lot of problems by letting us use one variable to store bunches of things, wouldn't it be nice if there was another type of variable that's not int, that's not string, that's not char, that's not float or any of those that we've seen already?

Wouldn't it be nice if there's a person data type in C, where I can actually create a person in my code and a person in this world shall have a name and a number.

Heck, if we were implementing students, maybe a student could have a name, a number, an email address, a Harvard ID number, or Yale ID number or the like.

You could imagine encapsulating, so to speak, a bunch of different types of data inside of one larger data type.

And, generally, when we talk about data structures, we mean exactly that, some kind of container for multiple types of data-- so a custom data type, if you will.

So, for instance, if I wanted to create an array of people, wouldn't it be nice if there's a data type called person.

So I could use code like this.

Give me an array of people-- and I don't know how many yet, but give me an array of people, each of which is of type person.

So instead of string, instead of int, I'm saying person.

And in English, I'm pluralizing the name of the array as, obviously, people instead.

But that doesn't exist with C. There are no student data types.

There are no people data types.

There are no professor data types.

Any of these things that you might imagine in the real world don't come with C. All you get are strings and ints and floats and those lower-level features.

But if we know a person, for our purposes, we'll have a name and a number.

Well, why don't we just give them a name and a number, but somehow encapsulate this name in number in a bit of new syntax?

And so the new syntax we will introduce today is that of creating your own type that is a structure specifically.

And we'll see more of these over the course of the term.

And even though this looks a bit cryptic, what this chunk of code here is saying is define a type that is itself a structure inside of which is both a name and a number, which are both strings in this case, and call that whole new structure person.

So as soon as the compiler gets to the semicolon, a person data type does now exist.

And inside of that data type is two things, a name and a number.

Now, as an aside, I deliberately use string here for both name and number.

I use string in my code a moment ago for those phone numbers.

Why did I use a string instead of an int or even a long for my phone numbers?

It wasn't actually a mistake.

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, like the hyphen, the country code, maybe parentheses if you format your number differently.

And so a good rule of thumb, actually, is that even though you and I in the real world might call certain thing numbers, like Social Security number in the United States or phone number or ID number, if there might potentially be other punctuation or symbols in that number-- and, frankly, more generally, if it would make no intuitive sense to perform math on something you call a number, and I

can't think of a scenario where you'd want to perform math on a phone number, you probably should store it instead as a string instead, and use actual integers, actual longs for things that mathematically or computationally make sense to be treated as literal numbers instead.

So if I now have this new feature whereby I can define a custom data type in my phone for my phone book, I think I can implement a brand new version of this program that's going to be a bit more verbose, but it's going to allow me to solve this problem better.

So let me go back to VS Code here, and you'll see in this code, where we left off, I'm going to go ahead and delete all of this just for now, and I'm going to whip up a slightly better version.

I will claim, outside of my main function, I'm going to do exactly what we just saw on the slide.

I'm going to define a structure inside of which is a name of type string and a number of type string.

And I'm going to call that whole thing a person.

It turns out style50 and, particularly, the program we're using underneath the hood prefers, weirdly, that you put person on the same line as the curly brace.

So just FYI, if you run style50 and you see that it moves as such.

Inside of main, I'm going to now give myself an array of type person called people of size 3.

So, still, I'm not going to solve all of today's problems. I still don't like the fact that I'm hardcoding a 3.

But I just want to demonstrate for today's purposes how we can use this here feature.

So I now have an array of three people, and each of those people is, by definition, a person.

And a person, we now know, contains a name and a number.

So how do I initialize this array?

It's not as simple as just using get_string once.

I clearly need to use it twice, but I won't even do that.

I'll just hardcode the values for demonstration sake now.

Let us update the first person in the people array-- so this is week 2 syntax-- and set the name of that first person equal to, quote unquote, "David," semicolon.

Then, in that same person structure, go into their number field and set that equal to +1-617-495-1000 semicolon.

So what here is new?

Well, of course, people bracket 0 isn't really new.

We did that last week.

If the array is called people and you want the first element, you use bracket 0.

But what is new today is this dot operator.

Once you've created a structure inside of the computer's memory, if you to go inside it and access the things that compose it, like name and number, you just use a dot like this.

And that means go inside the first person and access their name, set it equal to, quote unquote, "David," and do the same thing.

Now for their number.

So even though, yes, this stuff is new here, the only new operator, so to speak, today is really that same dot.

Let's go ahead and initialize the other two people, just so we have an array completely defined.

People bracket 1 dot name will be John, as before.

People bracket 1 dot number will be John's number, which was a little different-- +1-949-468-2750.

And then, lastly, people bracket 2 dot name equals, quote unquote, "Yuliia."

And then people bracket 2 dot number equals the same as mine, +1-617-495-1000.

So now, even though this is more of a mouthful-- and let your mind wander to the reality that we could just use a loop to do this a little more cleanly and use get_string and make it interactive, but I really just want to demonstrate the typedef and the struct and this new dot operator-- let's now search for someone's number.

So let's ask the user for a string called name, using get_string as before, prompting for that name.

Then, inside of a for loop, for int i equals 0 i less than 3-- again, don't love that, but we're focusing on one problem at a time, not this other one-- i plus plus.

Inside of the for loop now, same as before, if the return value of strcmp passing in the current person's name and the name that the human just typed in returns a value of 0, then, inside of that, let's go ahead and print out Found person s, backslash n and plug in people bracket i.

But I want to see their number, so I do dot number instead.

Now I can return 0 for success.

Down here, I can print out "Not found" to indicate failure.

And down here, I will return 1.

So the only new stuff in this program really is the fact that I have now invented a new data type called person that we can now use in our code.

And I'm accessing the individual fields or attributes of that new structure by using this new dot operator, which goes inside of that custom structure.

If I didn't screw up, let me go ahead and make this phone book.

So far, so good-- dot slash phonebook, Enter, and now, if I type in John, Enter, I have in fact, found John's number.

And if I go ahead and search for someone else, for instance, like Brian, who's not in the phone book, he, in fact, is not found.

Questions then on any of this feature via which we've now implemented really something closer to the phone book, albeit using linear search and not binary search?

Question?

Yeah, in front.

STUDENT: [INAUDIBLE] DAVID MALAN: Can you say that a little louder?

STUDENT: [INAUDIBLE] DAVID MALAN: Ah, what if two people have the same name-- a corner case, if you will?

This code will not work necessarily correctly because it will return to me or print for me who's number?

Only the first one that it actually finds.

So that would be a mistake.

And I think we'd need to address that with a bit more complicated code-- so solvable, but not for now.

A good observation.

Other questions on this here code?

All right, well, let's then tee up an actual solution to this problem.

Namely, if I want to use binary search, I can't yet, unless I manually sort those arrays, just as Yuliia came up earlier and kindly sorted the dollar amounts that were inside of these lockers.

Now she and I kind of coordinated in advance so she knew exactly what to put in what.

But if she were just handed a list of numbers or a stack of papers, each of which was a different denomination of bill, there's not necessarily obvious how we would go about solving this problem, sorting the values.

And, after all, even though the phone book that I tore in half in week 0 and the phone book I keep referring to on my phone and yours is presumably sorted by first name or last name, so you can find names and numbers quickly, well, how much effort is required in sorting those names and numbers?

So case in point, if, for instance, I handed you all of these sheets of paper on which are these different dollar amounts, and they weren't necessarily in any particular order-- instead, I simply hand you a stack of $7 of various denominations like this and say, find me the number 50, and they're sort of randomly organized, what's the algorithm for finding the number 50?

Well, you could just kind of sift through them one at a time, a.k.a. linear search, and you'd eventually find it correctly.

Or you could take a moment, sort them all, and then much more quickly get me the answer I'm looking for.

But would anyone in this room, realistically, whether it's seven pieces of paper or 700 pieces of paper, would you bother sorting them only then to find me the answer?

Yes?

No?

Would anyone sort them?

I mean, I'm kind of setting you up for contradiction.

No, it'd be stupid to them.

Why?

Because if you're only being asked one question, find me the 50, why are you wasting time sorting those values in order to find a number that you might as well just sift through quickly and find it by big O of n running time the first place?

But suppose I hand you those bills, or suppose I hand you a big database of names and numbers, and I expect that you're going to want to search for someone again and again and again, like your phone.

Apple or Google probably are sorting all of those names and numbers.

Why?

Because you're not going to look up one person's number in the lifetime of your phone.

You're probably going to maintain the thing sorted the whole time so that every time you look up someone's name and number, that operation is, in fact, quite fast.

And so that invites the question, then, just how efficiently can we actually sort values?

And what does it then mean to actually these values?

Well, the problem of sorting looks like this.

If our input and output paradigm is to be believed, the input to the problem would be unsorted data, so randomly ordered bills or randomly ordered names and numbers.

The output, though, we want to be sorted.

Specifically, then, if we deal with an array-- here's an array of numbers from 0 through 7, completely unsorted, so same idea as the dollar bills, but I used smaller numbers because it's a bit easier.

The goal at hand is to get them from 0 to 7 in increasing order.

But for that, we need some algorithm to actually do the sorting, the step-by-step instructions.

And it turns out there's going to be bunches of ways we can do that.

But maybe just to set the stage before we take a break and have the most delicious Hello, Panda chocolate biscuits today, could we get 8 volunteers to come on up, and I can offer you an extra snack in the form of these little Mario mushrooms?

How about one, two, three, four, five, how about six?

Yes, you, who just put your hand down, seven on the end there, and let me find somebody-- how about eight in the Harvard sweatshirt?

All right, come on down.

Come on down.

And if you eight volunteers, before we do hellos, if you want to grab a number from Yuliia on the side of the stage-- those of you with numbers come on over to the middle of the stage here and line yourself up in this order, from left to right.

So hopefully we have 1, 2, 3, 4, 5, 6, 7, 8 volunteers.

Good.

Line yourselves up from left to right in the order you see above you.

And Yuliia has your numbers for you.

All right, line up here.

Line up over here.

Number five, you're over here.

OK 7 2 5 4 1 6 0 3.

How about some quick introductions from right to left?

STUDENT: Hi.

Hi, I'm Becca.

DAVID MALAN: There we go.

STUDENT: Hi, I'm Becca.

I'm studying electrical engineering, and I live in Wigglesworth.

STUDENT: Hi, I'm [INAUDIBLE], and I just graduated from Northeastern in masters in information systems. STUDENT: Uh-huh.

Hi, I'm Owen.

I live in [INAUDIBLE] Hall, and I'm wanting to study CS.

DAVID MALAN: Nice.

STUDENT: Hi, I'm [INAUDIBLE], I live in [INAUDIBLE], and I'm planning to study biomedical engineering.

DAVID MALAN: Nice.

STUDENT: Hi, my name is Abdul.

I'm in Wigglesworth, and I'm planning to study economics and CS.

STUDENT: Hello, I'm [INAUDIBLE].

I'm from India.

I'm studying computer science at Clark University.

DAVID MALAN: Nice.

Next.

STUDENT: Hi, I'm Jasmine.

I'm from Shanghai.

I live in Thayer, and I plan on studying CS and econ.

DAVID MALAN: Nice.

And?

STUDENT: Hi.

I'm [INAUDIBLE] from China, Shenzhen.

I live in Deng.

DAVID MALAN: Wonderful.

We have three attempts here to sort these numbers.

Go ahead-- sort yourselves from 0 to 7.

Go.

One of you had it easy.

All right, correct.

What was their algorithm?

What was the algorithm?

Could someone explain step by step, yes, what they just did?

STUDENT: [INAUDIBLE] DAVID MALAN: So to summarize, those of you who had small numbers generally came this way.

Those of you with big numbers generally came that way.

And step three was "and then they generally figured it out."

So that's correct.

And that seems to have been a fairly organic process.

But let's take a more of a methodical approach here.

Can you reset yourself to match that same order?

So unsort yourselves again.

And let me propose that we try a couple of different approaches step by step.

So here, we have some data that is unsorted, and there's a few different ways I think I could wrap my mind around this.

If I want to get the smallest numbers on the left, the biggest numbers on the right, what I think I want to do is maybe do exactly that-- let me find the smallest number.

So 7 at the moment is the smallest number.

But wait a minute, 2 is now the smallest.

So I'm going to remember that-- not 5, not 4.

1 is now the smallest number.

I'm going to remember that.

6-- 0 is now the smallest number, and 3.

So I think, so long as I'm using at least one variable in my mind to keep track of what the smallest number is that I have seen, I can select number 0.

And if you don't mind following me here, we can put number 0 at the beginning of this array.

But before you move, we could have everyone scooch to the left by taking a step.

But that's kind of wasteful, I think.

That means a lot of work for a lot of people just to make room for number 0.

What would be smarter if I want to put 0 on the left here?

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, maybe I can just swap with number 7.

You're in the wrong place anyway, so could you please go over there instead where number 0 was and number 0 come on over here?

And now we have begun to the list.

I haven't solved the problem entirely, but to use the vernacular of week 0, I have taken a bite out of the problem.

And, frankly, the problem is now smaller because if 0 is in the right place now, I have only seven problems remaining instead of eight.

So maybe I can do this same algorithm again a la our familiar loops and select the next smallest number.

So two at the moment is the smallest.

So I'm going to remember that.

5, 4, 1 is now the smallest.

I'm going to remember that.

6, 7, 3-- so 1 is now the smallest.

So if you don't mind joining me here, we're not going to move you all, but I think we're going to evict number 2 now and have you go over there instead, thereby swapping the values.

Let's do this once more.

So I can ignore 0 and 1, so the problem is now size 5.

Sorry, I'm off by 1.

The problem is now size 6 because we have eight volunteers and not seven, my apologies.

5 is now the smallest.

4 is now the smallest.

2 is now the smallest, so I'm going to remember that.

But I am still going to keep going because at least for the moment, I'm assuming-- sort of small brain here, I only have one variable with which I'm keeping track of numbers.

And even though everyone in the audience, with your bird's eye view, remembers that 2 is obviously now the smallest number, the only way I would remember if 2 is now the smallest is if I were using multiple variables.

But I'm keeping it simple.

So I'm only using one variable in this story to keep track of the then smallest value.

Now that I know it's 2, let's pull you back out, even though we're undoing something here.

5, lets you move you here so that you two effectively swap.

Now I'm going to do it a little faster.

So 3, come on out and swap with 4.

Now let's go ahead and do 4.

Let's go ahead and swap you with 5, selecting the now smallest element.

Let's now go ahead and select 5 and swap you with 6.

And even though I'm kind of making a bit of a mess here, I'm doing the exact same thing again and again.

I just got a little unlucky here.

And now 6 and 7-- let's go ahead and swap you.

And now 7-- I'm all done.

So I think, now, they are sorted.

And that clearly took way longer.

But I think if we just did it like this, like this, like this, it would be not only correct, it would be step by step and replicable, and there would be no more sort of magical figuring it out at the end.

But let's take one final stab at this before we break.

If you could go ahead and unsort yourselves to look exactly like that one final time.

And as you do this here, we now have the exact same order as before.

So why don't I take different types of bites out of this problem?

Because maybe I just think about the problem a little differently.

And as we've said since week 0, there are often multiple ways to solve the same problem.

And you might think differently for me.

So here's maybe how you would think about it.

Instead of going back and forth and back and forth, looking for the next smallest element, let's just solve the problem in front of me literally.

7 and 2 are the first two elements of this list, but they are clearly out of order.

So what could I do?

Let's just swap 7 and 2.

I have fixed at least one problem now.

Now let's look at 7 and 5.

They are out of order, so let's swap those two.

7 and 4, you are out of order.

Let's swap you two.

7 and 1, you are out of order.

Let's swap you two.

7 and 6 out of order-- swap you two.

7 and 0 out of order-- swap you two.

7 and 3 out of order-- swap you two.

Now I have improved the situation.

What's the most glaring improvement?

Who is in the right place?

7 is in the right place.

So even though my algorithm was fundamentally different, I looked at pairs of people adjacently, and I swapped them if and only if they were out of order.

I did take a bite out of this problem.

I have solved the problem of seven.

And so now if I do this again, I can essentially ignore everyone at this end of the list because the biggest number thus far has sort of bubbled up to the top.

So I bet I can do the same exact thing by just taking these small bites out of the problem.

2 and 5, you're good.

5 and 4, swap.

5 and 1, swap.

5 and 6, good.

6 and 0, swap.

6 and 3, out of order-- swap.

I don't have to even look at 7 because I already solved that problem.

Now I've taken a second bite out of the problem.

Now even though I'm going back and forth, back and forth in a different way, I'm focusing more locally on pairs of problems. 2 and 4 you're good.

4 and 1-- swap.

4 and 5-- good.

5 and 0-- swap.

5 and 3-- swap.

Don't have to touch 6 or 7 anymore.

So I'm nearing the end here.

2 and 1, swap.

2 and 4, stay.

4 and 0, swap.

4 and 3, swap.

Don't have to look at 5, 6, 7 anymore.

Now back here-- 1, 2, you're good.

2, 0-- Swap.

2, 3-- stay the same.

Don't have to look at 4 or 5, 6, or 7 anymore.

Down over here, 1, 0-- swap.

Now I could just stop, but again, I don't have, as the computer, this luxury of this bird's eye view.

I only know if I'm done by going through the full algorithm.

1 and 2-- good.

2 and 3-- good.

3 and 4-- good.

4 and 5-- good.

5 and 6-- good.

6 and 7-- good.

But I'm going to do one last pass because I previously made a swap, and I think what I could do is stop if and only if I make no further swaps.

So let's do this again.

0 1 1 2 2 3 3, 4 4 5 5 6 6 7.

Now, I would be crazy to repeat that process because why bother going back and forth across the list if I've done no work?

So I think I can conclude that the lists are now sorted.

So it turns out that what we have just done is implement two different algorithms, two of many different algorithms via which you can actually sort values on the screen.

After our 10-minute break, complete with cookies, we'll come back, translate this to code, and something more algorithmic.

But finally, a big round of applause for our volunteers, and come on over this way.

[APPLAUSE] See you in 10.

All right, we are back.

So let's slap some names on the two algorithms that we just did with our volunteers-- the second and the third algorithm in particular that were much more formulaic.

The first of which we're going to call selection sort.

And I very deliberately was using language like, let me select the smallest element and select the next smallest element.

Selection sort does exactly that.

And let's make it a little more rigorous now in the context of these same doors.

So recall that any time we've talked about the lockers for searching for information, the leftmost door is going to be bracket 0.

The rightmost door is going to be bracket n minus 1, where again, n is the number of doors.

And if we start counting at 0, as always, n minus 1 is the end, which means, mathematically, this is n minus 2 and so forth from right to left.

So those numbers, 0 and n minus 1, should generally stick in your mind any time we talk about arrays.

So how might we implement in pseudocode what I walked our volunteers through more methodically for that second algorithm?

Well, one way would be this-- for i from 0 to n minus 1.

In other words, initialize a variable or a finger, if you will, and point at the first person first, and then, generally, work your way through the list from left to right in order to get it sorted.

What do I want to do on each of those passes?

Well, I want to do exactly what I did as with our volunteers-- find the smallest number between numbers bracket i, starting at 0, and numbers bracket n minus 1.

So in other words, if you start counting i at 0, like any old for loop in C, you're going to compare everything between bracket 0 and bracket n minus 1.

Then, the next time around, you're going to compare everything in bracket 1 through n minus 1, then bracket 2 through n minus 1.

And that's why, in the first algorithm, I was able to ignore everyone I had sorted behind me already.

I was constantly shrinking the problem, and as soon as I found the smallest element, recall, with our volunteers, I swapped that smallest number that I was remembering in my mental variable with numbers bracket i.

And, again, if you start at 0, that's why we evicted the first person, then the second person to make room instead of creating a whole bunch of work for ourselves and all of our volunteers by having everyone shift over each time.

We try to at least do a little more efficiently than that.

So what really was happening maybe at a slower pace with selection sort if we had numbers like this?

Well, if we consider this leftmost element initially to be bracket i in general-- but, of course, it's still 0 and then 1 and then 2-- and the end of this list is n minus 1, what did I do on my first pass with that first algorithm that we're now calling selection sort?

Well, I first kept track in my mind of the smallest element I have yet seen from left to right.

And the first element is going to be, by definition, the smallest element if I've looked at no others.

So I'm going to highlight 7 as being equivalent to remembering 7 in my mind.

But then I found 2, so I updated the variable.

5 is not smaller.

4 is not smaller.

I eventually found 1, which is smaller, so I remembered that number instead.

6 is not smaller.

0 is smaller, so I remembered that instead.

3 is not smaller.

And then that's why the next step, recall, was to ask 7 to move, move the 0 to the leftmost place, and then put 7 back where 0 once was.

We could shift everyone over.

But I was trying to make the point, especially with our array, that we only have a fixed amount of space.

So you can't just make room for someone.

We only had eight locations in total on stage.

However, we could have shifted everyone, but it felt like undue work.

The reality is it's not going to make a huge difference to the analysis of the running time of this algorithm, but it did feel like unnecessary work at the time.

After I've done one pass of selection sort, I've really only taken one big bite out of it.

I still had another 7 and then 6 and then 5 bites to go.

So the next iteration of this algorithm would indeed update i so that now we're looking at i through n minus 1 here, and we would do the exact same thing again and again and again until we're all done with that problem.

To see this a little more visually give me just a moment here to pull up an animation thereof.

I'll flip over to this screen in just a moment.

But for selection sort, let me propose that we visualize this as follows.

I'm going to go ahead and pull up on my screen here the following comparison sorting algorithms, which is a nice visualization that some friends of ours at another university made.

And this array here represents numbers.

Small bar are small number-- big bar is big number.

It just gives us more of a graphical representation of the same.

So, ultimately, I want all the small bars over here, all the big bars over there, and notice that there's clearly more than eight of these, and they happen to be randomly sorted.

What I'm going to do at the bottom of my screen here, there's some little playback controls.

I'm going to go ahead and speed up the animation a little bit, and I'm going to go ahead on the top now and click Selection Sort.

And what's going to happen iteratively from left to right is that they are using pink, just as I was using my mind to remember, which is the then smallest element.

And you'll see that it sort of fixates in pink, which the then smallest is, and then moves it to the left, moves it to the left, moves it to the left.

And this just goes on and on again and again.

But you can really see, perhaps, visually now how much time we're wasting.

I mean, just like I was going back and forth and back and forth across all of our volunteers, look at how many times the same bars go from blue to pink, from blue to pink because we're touching-- that is, we're looking at the same elements again and again and again until we're finally done.

So selection sort, as algorithms go, it's actually not very efficient.

It's not very efficient.

It doesn't have a very fast running time really because of all of those extra comparisons.

So, in fact, we can generalize this here, if I go back to where we left things off, and we originally had this array of numbers, well, if I've got eight numbers to begin with, each pass is going to take-- the first pass is going to take n minus 1 steps.

If I've got n elements, but I want to compare looking for the then smallest element, I have to compare one against n minus 1 other elements.

So if I want to do some back of the envelope calculations here as to how many steps or more specifically how many comparisons selection sort has me make, I would say that, on the first pass from left to right, I did n minus 1 comparisons.

Why?

Because I started over here with our eight humans, and I looked for the smallest, smallest, smallest element, and I did so by comparing them, n elements a total of n minus 1 times to compare them ultimately.

So that's n minus 1 steps the first time.

But that got me to having 0 in the right place.

So then I had seven steps and then six steps and then five steps and so forth.

So if I generalize this with n, instead of worrying about the specific number of human volunteers we had, that's like saying n minus 1 steps the first time plus n minus 2 steps the second time plus n minus 3 steps the third time plus dot, dot, dot, plus, finally, one step when I'm all done solving the problem.

So how can I work this out?

Well, if you remember the cheat sheet at the back of your math book, a series like this actually sums to n times n minus 1, all divided by 2.

And trust me or take that on faith, but that's what it equals.

Now we can apply some high school-style multiplication.

So we've got n squared minus n by distributing the n all divided by 2.

And if I divide that out, I've got n squared divided by 2 minus n over 2.

But here's where asymptotic notation is our friend.

I don't really care, at the end of the day, precisely how many steps selection sort takes.

I want to on the order of how many steps it takes.

Why?

Because, again, I might have a fast computer, a slow computer.

What I really care about is when n gets really big, what really impacts the performance of this algorithm?

And I dare say that if you take a really big number and square it, that's a way bigger deal than just dividing by 2 or dividing by 2.

In other words, the highest-ordered mathematical term here is the n squared.

That's the one that's really going to matter when we're talking n equals a million, a billion, a trillion.

That's going to dominate all of the other characters.

So if I use my asymptotic notation to describe the upper bound on the running time of selection sort, it's on the order of n squared.

I don't really care about the precision when it comes to describing running times.

So n squared-- it's a lot.

And you can see it visually with that visualization, all of the pink, all of the pink, all of the pink is because we were doing so many darn comparisons again and again.

So is there a categorization we can do here?

Well, with selection sort, it would seem that in the worst case, that algorithm might take us as many as, indeed, n squared steps.

But what about the best case?

What about the best case here when it comes to selection sort?

Well, could it be omega of 1?

Could we get away and just get lucky with one step to the thing?

Would it have to be more using this same code?

Well, consider, then, these doors here as being again representative of exactly what's been sorted.

Could we get away with omega of 1 or would it have to be something more?

Well, here's that same cheat sheet as before.

Does anyone want to conjecture other than the person with whom I had a chat during the break with as to what the lower bound on the running time of selection sort might be?

STUDENT: Maybe n squared.

DAVID MALAN: Maybe n squared.

Why do you say that?

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, really well said.

Even in the best case, where the numbers just happen to start sorted, which could happen in some perverse scenario, the source code doesn't take into account that being possible.

In my pseudocode here, there is no allowance for hey, by the way, if array is already sorted, exit or quit early.

Instead, it is going to blindly do this n minus 1 times, and then do this and then do this blindly.

So, literally, if I had eight volunteers come up and they sorted themselves in advance, 0 through 7, I would have taken the same number of steps, even though nothing interesting would have been happening, at least according to the source code.

We could clearly come up with better source code that is written in pseudocode to solve that problem better.

But at least as written, it does not do any better than that.

So we would say that selection sort is in big omega of n squared.

And now just to bring in the other Greek term, the capital theta, if we have upper bound of n squared and lower bound of n squared, you can also now conveniently say that selection sort is in theta of n squared because they're one and the same.

It's just a third term we can whip out.

What about the second algorithm now?

Clearly, if it was the second algorithm I proposed, maybe it is, in fact, better in some way, and not just because it might be a different way of thinking about the problem.

Maybe it's better design.

Well, bubble sort similarly treats our volunteers as this array from elements 0 to n minus 1.

And here might be the pseudocode with which we could capture what we just did.

Though I'm going to simplify a little bit for the sake of discussion, and I'm going to tolerate some of the unnecessary footwork of going back and forth simply to keep the pseudocode simple.

But I'll stipulate that even if we were to optimize it a little bit vis-a-vis this version, turns out that asymptotically, it's still going to be in big O of the same thing.

But we can do a little better on our lower bound.

Repeat the following n times, just like Scratch, for i from 0 to n minus 2.

So, in other words, if you think of our human volunteers, i might be my left-hand, pointing at location 0 first.

And then I want to compare each pairwise person.

So I want to compare person i to person i plus 1.

And that's what's really going on here.

If numbers bracket i and numbers bracket i plus 1-- so if the person my left hand is pointing at and the person my right hand is pointing at are out of order, then go ahead and swap them.

But I do this a whole bunch of times, it would seem.

I repeat this n times.

And then, inside of this loop, I also iterate from 0 to n minus 2.

Well, why is that?

Well, n minus 2-- we don't normally talk about n minus 2.

But if I'm comparing my eight humans and sort of walking down the array, like I was, I want to make sure that my left hand does not go to n minus 1 because n minus 1 is always the last person.

So where would my right hand be pointing at?

Empty space.

So I need to be careful.

And if I'm comparing things side by side, I want i, my left hand, to go up to n minus 2, the second to last person or second to last element of the array, so my right hand doesn't go over the end of the array itself.

So subtlety, but that's why I tried to call out earlier the n minus 1, n minus 2, just to give you a mental model for that.

So technically speaking, we can optimize this a little bit.

And if we really get into the weeds, I only have to repeat this n minus 1 times.

Why?

Because once I get to the end of it, the last person is sort of naturally sorted already.

I don't have to worry about fixing one person.

They will have bubbled to the right location.

So if we have this list of numbers, just as we had our array of volunteers, how can we think about this visually.

Well, left hand is I in the story.

Hand is I plus 1.

And what did I do.

Again and again and again I compared them.

And if 7 and 2 are out of order, I swap them.

7 and 5-- swap them.

7 and 4, swap them.

7 and 1-- swap them.

7 and 6-- swap them.

7 and 0-- swap them.

7 and 3-- swap them.

And notice, just as with our humans, 7 bubbled their way up all the way to the end, leaving me with seven more problems to solve.

But at least I took a bite out of the problem.

And, in fact, on the next iteration, we would come back and start over.

But strictly speaking, we don't have to go all the way to the end this time.

So bubble sort fundamentally sorts the array, but does it do it any faster?

Well, here is how again, we might write pseudocode like this.

And let me propose two ways of thinking about the bubble sort running time.

It turns out, when you have pseudocode in front of you or, in the future, actual C code or actual Python code, once you have an eye for it, you can literally look at your code or someone else's and reason through how many steps each line of code should take.

So, for instance, how many steps will this first line take, where you're repeating something n minus 1 times.

This one's kind of a gimme.

It literally will take n minus 1 steps because it's just saying what it is.

What about the loop inside of this loop?

Technically, in C, you could use two for loops.

You could use two while loops.

I'm just using English vernacular that is kind of simple as possible here.

But what about this-- for i from 0 to n minus 2?

Well, this is technically a total of n minus 1 steps because if you start at 0 and then 1 and then 2 and then 3, dot, dot, dot, all the way to n minus 2, you have counted a total of n minus 1 times.

So the outer loop by this analysis is going to take n minus 1 steps, but every one of those interior steps is going to take n minus 1 steps.

So there's some multiplication going on here.

Do this inner loop this many times, but do that this many times too.

And now how many steps does it take to check if two numbers are out of order?

Well, that's just like comparing two numbers, left hand and right hand.

So that's one step.

And, sometimes, I swap them and swapping them means, like, this person has to come out, this person has to come out, then they have to swap.

So that's another three steps.

So maybe this is like one step if we just keep things simple, maybe it's four steps.

I don't really care.

It's a constant number of steps.

No matter how big this array is, I'll claim that you can swap people in constant time.

It might be one step, might be four steps, but it has nothing to do with the length of the array.

It's only going to take the same number of steps to do that kind of swapping.

So now you can multiply this out. n minus 1 times n minus 1 times, to keep it simple, 1 or 4 or whatever.

I'm going to ignore that factor.

We can then figure out how many steps this whole algorithm takes.

In fact, if I write this out as before, n minus 1 steps times n minus 1 times.

That gives me, if I do FOIL or whatnot, n squared minus 1n minus 1n plus 1-- combine like terms-- n squared minus 2n plus 1.

And here, too, I don't really care about this level of precision.

If I wave my hand out, the details, ah, this is on the order of n squared also.

So to be clear, if we compared selection sort and bubble sort, technically, they're going to be slightly different numbers of steps.

But the reality is if you run these algorithms long enough with big enough values of n, they're both going to be super darn slow because the dominating factor is still n squared.

Now I can do one optimization, in fact, but let's first consider what the upper bound is.

In bubble sort, the upper bound apparently is on the order of n squared steps.

But as written too, it would seem that this algorithm as written also is going to be omega of n squared because it's never taking into account, hey, wait a minute, is the array already sorted, in which case stop sooner.

We don't have any language for that here.

But what if I add a super simple conditional here?

I could, after every iteration from left to right, just ask myself, did I make any swaps on that pass through the volunteers.

If so, there might still be work to be done.

But if not, why am I going to crazily repeat myself because if I didn't make any swaps one time, I'm definitely not going to make any swaps the next time.

It's going to be stuck in some loop.

So I can short circuit my logic by just saying, hey, if no swaps on one of those passes quit.

You are done.

And if I do this now, such that now I do maximally one pass if the list is already sorted to notice that the list is sorted, what could you say bubble sort's lower bound is using omega notation.

STUDENT: Omega of n.

DAVID MALAN: Omega of n.

It has to take you at least n steps logically to figure out if the array is sorted.

It cannot be omega of 1.

Like, if you're looking at eight elements, let alone n elements, there is no way logically to take one step and conclude that all n elements are sorted.

That makes sort of no sense.

But it is indeed an omega of n because you just need one pass to conclude that everything is indeed in order.

So it seems that bubble sort is actually a little bit better.

Let's see how it actually plays out visually.

Let me go ahead and go back to my visualization from before.

I've rerandomized it, and I'm going to click this time bubble sort.

And you'll see that it's going to solve the problem with fundamentally the same outcome.

But notice that the work it's doing is a little different.

The pink indicates now which two pairs of elements are being compared again and again.

It's sort of nonobvious what's happening over here.

But clearly, the biggest numbers are bubbling their way up to the end of the array, just as our human volunteers.

We had number 7 and then a 6 and then 5 and then 4.

But again here, too, you can see visually how many times we are retracing our steps to ask a different question but again, touching or looking at the same elements in memory again and again and again.

And this isn't even this many elements.

What are there, like 100 or so elements here?

Like, my god, this is taking forever to this many elements.

Maybe this is why, then, if you just need to answer a question once, you just sift through the papers, find me the number 50, and don't bother sorting altogether.

But if you it once, and then you have millions of customers, like Google, searching and searching and searching, maybe it's worth spending that time up front and then amortizing it, so-to-speak, over the lifetime of the data itself.

OK, I don't have to keep stalling because now that algorithm has concluded.

So, to be clear, with that optimization in bubble sort, we can make it sort of better than selection sort, but ultimately, it's going to be still on the order of n squared steps.

Questions on selection or bubble sort or sorting more generally?

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: Good question.

What if happens if I press bubble sort now, knowing that it is already sorted?

Let's see if this visualizations implementation is the smart version, with that additional conditional, or if it just goes back and forth and back and forth.

Ooh, not well-implemented.

Notice that they are just blindly doing the first version of my code, where there's no additional check, did I do any swaps?

Because even though you're seeing pairs of pink, none of those bars are actually moving.

So this is both big O of n squared and omega of n squared, a.k.a. theta of n squared, a.k.a.

squared, a.k.a. theta of n squared, a.k.a.

Poorly implemented in this case.

Missed opportunity for them to have done this.

I don't know if you need to be convinced that it's not going to do anything, but it'd be like holding in a sneeze if we don't go to the end.

Almost done.

Almost done.

Almost done.

And no useful work was done.

But it's now indeed sorted.

Can we do better than selection sort?

Can we do better than bubble sort?

Yes.

And there are dozens, hundreds, I mean, maybe thousands of different sorting algorithms out there.

And, in fact, bubble sort and selection sort can be useful in the real world.

I mean, I have actually, in research projects, quickly whipped up in code an implementation of one or the other because it's just so relatively easy.

First time through it, you're going to make mistakes, you're going to have buggy code, but they're relatively easy algorithms that you don't have to think hard about.

And, in fact, sometimes it's faster to whip up a bad algorithm and just let the code run then spend more time writing a better algorithm only for it to be done like this.

It's kind of a wash sometimes in the real world.

But in practice, what we're going to find is you and I, except for something like a homework assignment, are not going to be in the habit of writing sorting algorithms anyway.

We're going to use a library, like a lot of those other functions.

But you'll understand what algorithms are actually doing for you underneath the hood.

So what is a technique we can bring to bear on this problem that might help us think about the problem a little bit differently and maybe help us solve the problem better?

And by better, I mean, let's stop repeating ourselves by touching those elements again and again and again.

Let's really try to minimize the number of comparisons we're doing because that's what was getting computationally expensive in terms of time.

So here, for instance, is an algorithm that we've seen before, namely searching for things behind doors.

So this was binary search, same as before, whereby instead of looking for 50, I'm more generally looking for a number behind the middle door or to the left of the middle door or to the right of the middle door.

Even though I didn't call it this earlier, it turns out that this algorithm, as we used earlier today, is an example of what's called a recursive algorithm.

A recursive algorithm is one that calls itself or, put more plainly, in the world of C and, frankly, in the world of mathematics, a function is recursive if it calls itself.

Now, we've used main in C code, and we've called get_int.

We've used main and we've called get_string.

What if main called main, for instance?

That would be an example of recursion.

But generally frowned upon to have main called main.

But we could certainly have another function that we write that maybe does call itself toward a useful end.

So why is that?

Well, notice that in this algorithm from earlier, binary search, it's already implicit that this search algorithm is using a search algorithm because I left it unstated.

Well, what does it mean to search the left half?

Well, implicitly to search the left half means shorten the list by half and then do all this again, logically, just apply the same logic to a smaller data set.

And because when we went left or right or left or right, both this week and in week 0 because we kept shrinking the problem, it's OK if you keep doing the same algorithm again and again.

The problem is getting smaller.

So, eventually, you're going to have no doors left, or, eventually, you're going to find the number you're looking for.

So these cases here, where you have very specific cases, like there are zero doors left or if I've found the number I'm looking for, those are generally what are called base cases, where the thing sort of bottoms out logically and you get back an answer at that point no matter what.

These two lines that I've highlighted are generally called recursive cases, whereby you don't get an answer yet.

You have to do more work by generally shrinking the size of the problem and doing the same logic again.

So a recursive algorithm or a recursive function is one that calls itself, that uses itself, but hopefully on a smaller and smaller size problem.

So with that said, here is the same pseudocode from week 0, when I was searching the physical phone book, looking for John Harvard, for instance, trying to call them if the number is there.

Notice that, in week 0, I actually used, very deliberately, a loop.

It was not called that per se, until we slapped some terminology on this algorithm.

But I literally said, go back to line 3, go back to line 3.

And then we said you can call these things loops.

And it means visually you're going back and back and back.

But this could be rewritten, this algorithm from week 0.

We could do something like this.

Instead of saying open to the middle of the left half of the book and then go back to line 3, which really just means search the left half or search the right half, why don't we just say that?

So let's collapse these two pairs of lines from week 0 and just say search the left half of the book, search the right half of the book.

I can now get rid of the blank lines and kind of tighten the algorithm up, and now it's a shorter chunk of pseudocode, even though it's sort of left unsaid-- well, what do you mean search the left half?

What do you mean, search the right half?

Well, who cares.

I don't need to tell you how to search half of a book.

I've told you how to search a whole book.

So just use the same logic to search half as many pages, half as many pages, half as many pages.

So whereas the previous version of this code here is an iterative version of our code, insofar as it uses loops, this version now is a recursive version of that same algorithm.

So, sometimes, you can solve problems with iteration-- that is, loops-- or with recursion.

And, sometimes, one problem is just better suited for one or the other.

And among our goals in the coming weeks is to help you identify when you might want to use one technique or another.

But, generally, iteration tends to be the more comfortable approach.

But let's see this in context.

There is, I've claimed, recursive algorithms, recursive code, as in here.

There's also recursive physical structures in the world.

Like, here's that pyramid from Mario, this one being pretty short and of height 4.

Let me get rid of the distractions of the background.

This physical structure is recursive in some sense.

Why?

Well, this pyramid of height 4 is really just a pyramid of height 3 plus 1 more layer of bricks.

Well, what's a pyramid of height 3?

A pyramid of height 3 is really a pyramid of height 2 with one more layer of bricks.

What's a pyramid of height 2?

It's really just a pyramid of height 1 with one more layer of bricks.

What's a pyramid of height 1?

Just a single brick.

So that last statement is sort of a base case.

At some point, I can't just keep dragging things out and telling you, telling you how one is based on the other.

At some point, I just have to say pyramid of height 1 is just a single brick-- stop.

But everything else can be recursively defined in terms of a pyramid of a smaller size.

So if, actually, I want to do this implementation, let me actually whip this up in two different ways.

Let me go back to VS Code here in just a moment.

And in VS Code here, let's go ahead and make something called, say, iteration.c,

just to make clear what kind of technique it is.

So in VS Code, I'm going to go ahead and say iteration.c.

And in this program, I'm going to write code that prints out a pyramid like this, of height 4, for instance, or anything else.

So let me go ahead and, at the top of this file, include cs50.h so I can ask the user how big it should be.

include cs50.h so I can ask the user how big it should be.

Include stdio.h so I can actually use printf.

Let me go ahead and, in int main void, just tee up the beginning of a program that's going to ask the user for a height of a pyramid using our friend get_int.

And then I'm going to assume for the moment that there is a function called draw whose purpose in life is to draw a pyramid.

I'm going to pass in that height.

Done.

So this now invites the question, well, how do you implement the draw function?

Well, a couple of different ways.

Let me do it iteratively with a loop.

So let me go ahead and define a function that doesn't return anything because I just need to have side effects printing on the screen.

I'll call it draw.

It takes as input a value like n for the height that I want it to draw.

And then, inside of draw, what am I going to do?

Well, this is easier than problem set 1 was because of the direction that the pyramid is heading.

So this I can do fairly quickly as 4.

int i is 0.

i is less than n, i plus plus, and then, inside of that loop-- so that's going to give me row, row, row, row-- I want to print out the number of bricks for a given row.

Well, I claim, with a quick glance, int j equals 0.

j is less than i plus 1, j plus plus, and then, in here, I'm going to go ahead and print out a single hash.

Then, out here, I'm going to go ahead and print a new line.

So I did this super quick, but let me convince you that it probably is correct here.

I'm iterating from 0 up to but not through n.

So if I want a pyramid of height 4, this is like giving me the first row, the second row, the third row, and the fourth from top to bottom because that's how the screen scrolls.

But then, inside of each of those rows, how many bricks do I want?

Well, on the very first topmost row of a pyramid, no matter its height, how many bricks do I want there?

The very top.

I just want one, like the single brick.

Well, if I start counting i at 0, I don't want to print zero bricks, so I need to do a bit of arithmetic here.

I need to do i plus 1.

So 0 plus 1 ensures that this inner loop, j, gives me one brick and then two bricks and then three bricks and then four.

So I just need to be a little clever and think about the arithmetic, but I think that gets the job done.

That prints out hash, hash, hash, hash, one at a time.

But at the end of each row, I move the cursor to the next line.

So even though I did this pretty quickly, and it might have taken you much longer to do problem set 1 as expected, I think this will give me what I want so long as I avoid making a past mistake.

I need to put the prototype of this helper function at the top.

So let me open my terminal window, make iteration, Enter-- so far so good-- dot slash iteration, Enter.

Let's do a pyramid of height 4.

And it seems to, in fact, work.

And I can do this even bigger.

Let me do a pyramid, for instance, of height, maybe 12, Enter.

And it seems to be working indeed with iteration.

Well, what if I instead want to use recursion as a technique instead?

I bet I can actually do that because, again, what is a pyramid of height 4?

Well, it's like saying print a pyramid of height 3, and then add one more row.

Well, what's a pyramid of height 3?

Well, print a pyramid of height 2, and then add one more row.

What's a pyramid of height 2?

Well, print a pyramid of height 1, and then add one more row.

The only problem that's interesting is how do you print a pyramid of height 1?

Well, just print a single brick.

So, curiously, that kind of thinking will actually give us a fundamentally different solution.

So let me do this.

Let me shrink my terminal window and close iteration.c.

Let me open a file called recursion.c, just

to make clear what technique I'm using.

Let me include cs50.h at the top.

Let me include stdio.h at the top, int main void again, and in here, again, int height equals get_int.

And then ask the human for the height.

Then go ahead and call an imaginary draw function passing in that height, which doesn't yet exist.

But now let's make it exist.

This function will again return no value because it's just going to print some side effects to the screen.

It's called draw, and it takes in the height, call it n or whatever you'd like.

Inside of this function, let's go ahead and consider what our base case is.

And I could say, if the pyramid is of height 1, go ahead and print one brick.

But you know what, even easier?

How do you print a pyramid of height 0.

You do nothing.

So I bet I can be even more clever here and just say if n equals equals 0, then go ahead and just return.

Don't return a value because it's void.

Don't print anything.

If you want a pyramid of height 0, you got it.

I don't have to do any work whatsoever.

If I really want to be careful, I can say if you somehow do something crazy, like give me a negative number, I'm also not going to do anything because that makes no logical sense.

But that's just more of a finer detail.

How now do I print a pyramid of height n according to my logic from earlier?

What would you have me print first as a pyramid of height n?

It's kind of circular logic, but how can I print a pyramid of height n?

I think I can draw a pyramid of height n minus 1, which doesn't even seem logical because I haven't even solved the problem yet, it would seem.

But if, again, you believe me that a pyramid of height 4 is really just a pyramid of height 3 plus one more row, that is what I've expressed thus far.

Print a pyramid of height 3, but now I have to print one more row.

Well, the one more row is actually trivial.

Why?

Because when I have a pyramid of height 4, what should the width be of the bottommost row 4.

So it's nice n equals n.

It's exactly what we want.

So I can do this pretty mindlessly in code for int i equals 0 i less than n i plus plus.

And then in this for loop, I think-- in this for loop, I can just print out a single hash mark, and then, at the bottom of that, I can print out a new line.

So, weirdly-- and let me add my prototype up here, void draw int n semicolon.

Let's focus on the draw function here-- I feel like I haven't even solved the problem that you asked me to solve.

One, I plucked off this arbitrary problem.

Like, if you want no pyramid, fine.

No pyramid it is.

Return without doing anything.

Then I'm sort of cyclically saying, well, if you want a pyramid of height n, we'll just go draw it yourself as a pyramid of height n minus 1.

But then the last thing I'm doing-- and this is where the magic actually happens-- I am also saying, once you're done doing that other thing recursively, give me one final row.

And where this works out logically, if you reason through this in your mind, suppose you want to print a pyramid of height 4, initially.

Well, this does not apply because 4 is bigger than 0.

This does apply, so you print a pyramid of height 3.

That puts you logically back in this function.

How do you print a pyramid of height 3?

Not applicable.

Well, you print a pyramid of height 2.

Then we get back here.

Doesn't apply.

How do you print a pyramid of height 2.

Well, you print a pyramid of height 1.

OK, let's go back here.

Doesn't apply.

How do you print a pyramid of height 1?

Well, you print a pyramid of height 0 that gets us back into here.

Now this applies, and I do nothing.

So it rewinds logically in your mind, if following along, and I just said to print a pyramid of height 1, I first print a pyramid of height 0.

Did that, didn't require much effort-- what do I then do?

Then draw one more row.

And if n, at this point in the story, is indeed 1, this for loop is designed to print one hash.

Then the function will end.

And if you rewind in your mind's eye, how did we get there, well, I asked to print a pyramid of height 2, but I first asked to print a pyramid of height 1.

But all I have on the screen is a single hash, but I add another row to that.

And if n equals 2 now, that gives me two hashes.

Then this finishes.

Now we rewind again.

Now I print another row-- three hashes.

Now this finishes and rewinds.

Now I print the fourth row.

So in this weird mind-bending way, by not answering the question, but sort of kicking the can down the road by saying, no, you go do this, so long as you take one bite out of the problem, one row, it logically all just kind of works out in the end.

So if I haven't made any typos, let me open my terminal window here, make recursion, dot slash recursion, let's do height 4, it actually does work.

Let me make my terminal window even bigger and do it again.

Dot slash recursion 12-- it does actually work.

So which is better?

Well, in some cases of solving problems, it just helps to write code recursively when what you are trying to do itself is recursive in nature.

And even though you probably haven't thought about any of the pyramids in Mario as being recursive, they actually now are because, again, a pyramid of height 4 is just a pyramid of height 3.

It's just a pyramid of height 2.

It's just a pyramid of height 1.

It's just a pyramid of height 0 plus one more row, plus one more row, plus one more row, plus one more row.

We'll see future problems wherein the data structures we're using in the computer's memory are sort of laid out two-dimensionally.

Those kinds of problems, too, may very well lend themselves to recursion, even if you can also use iteration or for loops as well.

Recursion is such a common technique but a challenging technique in the real world that there's even little Easter eggs out there.

In fact, let me go ahead and give me just a moment to pull up a browser, and then I'll switch screens.

If I pull up, say, Google here, any old Google window, and you want to learn more about recursion-- so recursion, Enter-- you'll notice this little Easter egg that the geeks at Google have had latent in google.com for years.

Does anyone see the CS joke at hand?

Yeah?

STUDENT: [INAUDIBLE] DAVID MALAN: What's that?

STUDENT: [INAUDIBLE] DAVID MALAN: Yeah, it's asking you, did you mean recursion?

Well, I'm pretty sure that's what I typed, so ha-ha-ha, let's click recursion.

Now we're in night mode for some reason.

But did you mean recursion?

Haha, I mean, that's maybe the kind of laughter it warrants.

But this is a joke.

It's recursion in the sense that Google is telling you to Google recursion again and again.

But, of course, the second and third results or whatnot are actually real results.

But you can try that at home by simply searching for recursion.

So, again, all it means for a function or an algorithm to be recursive is that if it uses or calls itself.

But so that you don't get into some infinite loop like Google, which ironically is sort of buggy in that it will never stop, you have a base case where you just pluck off the easiest of the problems-- height 0, height 1, whatever it is-- so that the interesting work is left to the recursive calls, where you call yourself again and again.

All right, any questions, though, on recursion versus iteration?

OK, we've got one algorithm to go because I don't like selection sort or bubble sort yet.

Even though bubble sort seemed to be a little better with that optimization.

My God, even just a sort 100 elements.

That code felt very slow on the screen when visualized.

Well, let's introduce one other algorithm for sorting, even though there's many more out there.

But merge sort is an algorithm that I claim is going to be faster, even though it, too, will probably, by design, bend your mind a little bit.

It's a little hard to wrap your mind around at first glance, but among its ingredients are going to be recursion.

So the algorithm for merge sort is essentially this three lines of pseudo code which in and of itself sort of hints at the mind-bending.

Sort the left half of the numbers, then sort the right half of numbers, then merge the sorted halves.

So that is literally merge sort.

If you are handed a whole bunch of numbers, an array of numbers, like we were earlier before the break, how do I go about sorting all of them?

Well, first sort the left half, then sort the right half, then merge the sorted halves.

And the first two lines here feel kind of obnoxious.

I ask you to sort n numbers, and you say, well, you go sort these numbers and then sort these numbers.

Like, I haven't actually given you a solution to the problem, but there's some magic in this last step-- merge the sorted halves.

So what do I mean by that?

Well, first, let's consider the base case.

If I give you nothing to sort, you can pluck that one off trivially.

Just quit.

If there's only one number or, heck, zero numbers, you're done.

And so that case is easy.

But the recursion is clearly manifested in these two lines because this is an algorithm called merge sort.

And if I'm telling you to sort the left and sort the right, well, you're probably going to use the merge sort algorithm to do that.

But the problem is going to get smaller and smaller.

So let's focus on what it means to merge two sorted halves.

So wonderfully, during the break, we replace the lockers with these here shelves.

And on these shelves are two sorted lists of size four.

The whole list is not sorted because, notice, I got 1, 3, 4, 6, but I've got 0, 2, 5, 7 over here.

Suppose, though, I want to merge these two sorted lists together, each of size four, into one bigger list of size eight.

How can I go about doing that?

Well, this is what it means to merge two sorted lists.

You point at the first element of the first list, maybe with your left hand.

You point at the first element of the right list, maybe with your right hand.

And you compare those two values.

And, obviously, if I'm pointing at 1 over here and 0 over here, which is the smaller of the two?

Well, of course, 0.

So what do I do?

I take it physically here.

I'll light it up for dramatic's sake, and I'm going to put it into its appropriate location up here.

Now my left hand is still pointing at the one on this list.

My right hand is going to move to the right and point at the two.

Same thing-- how do I merge these two sorted lists, one of size 4, one of size 3.

Well, I compare what I'm pointing at, the one and the two.

Let me go ahead now and pluck the one off and put the one at the very top there.

Now my left hand and right hand are pointing at 3 and 2 respectively.

I compare.

2, of course, is smaller.

So I grab this, light it up, and put it up there.

Now I'm pointing at 3 and 5.

3, of course, comes next.

I turn its light on, and I put it in its right spot up here.

Now I'm pointing at 4 and 5.

4 comes next.

So I do this.

Now I'm pointing at 6 and 5.

5 comes next, so I turn this on and plop it up here.

6 and 7-- notice I'm down to one element in each list.

I'm almost done merging.

I pluck off 6.

Now I don't have to do any more work to do with my left hand.

My right hand finishes here, and I have merged the two lists together.

How many steps did that take?

Well, there's eight elements total, 0 through 7.

And every time I made a comparison, I moved my left hand or the right hand.

So, ultimately, I moved each of the eight elements once and only once.

So that's n steps to merge two lists of size n over 2 plus size n over 2.

And that's it.

So that's what I mean to merge two sorted lists.

But there is something subtle about what I did here.

That was pretty straightforward.

Seems pretty easy to merge two already sorted lists, but why am I using shelves all of a sudden?

This is very intentional.

I didn't just use a single table, like where we had the lockers a moment ago.

Yeah?

STUDENT: You're not shuffling [INAUDIBLE] DAVID MALAN: Yes, I'm not shuffling the numbers around.

I'm not swapping things around in the same memory as our eight humans were.

I'm kind of cheating and using some extra space, if you will-- literally twice as much space.

I started here, and then I used sort of a separate array that was blank for me.

It was sort of allocated but not used to store that.

And this speaks to a fundamental trade-off we're going to start to see.

Almost always, in computing, if you want to improve the running time of something, you've got to spend some resource.

You have to increase the amount of space, maybe, that your algorithm uses.

You have to increase the amount of time that you, the human developer, put into figuring out the problem.

Case in point, when I said earlier, sometimes, I take shortcuts, and I'll whip up a very stupid, simple sorting algorithm.

Why?

Because my time, I'd argue, is valuable when I'm trying to solve a problem, and I'd rather spend time on other things.

So I don't spend much developer time.

But that means my code is going to be slower as a result.

So space, time, development time, money, any kind of physical resource energy nowadays is something that you can either increase or decrease and have an impact on these other measures as well.

So that's only how we go about merging two lists.

How do we go about sorting left and right?

Well, for this, let me ask Yuliia to join us up here on stage so that I'll act things out digitally on the screen very cleanly-- we'll also mimic what we just did here physically with the physical numbers in order to sort an actual list of values that starts off completely unsorted.

So the list we're going to do is this, arbitrarily, 6, 3, 4, 1, 5, 2, 7, 0.

We're going to start with them all on the top shelf, ultimately.

And we'll see, by acting this out, how we can go about sorting eight elements that start off completely unsorted.

And the three steps we're going to use are these-- sort the left half, sort the right half, and then merge the sorted halves together.

So those numbers again that Yuliia is putting in place are 6, 3, 4, 1, then 5, 2, 7, 0.

We've not rehearsed this, so we will see how well we both do together at this.

All right, so here is the array of numbers at the top, physically represented here.

You can look at whichever demonstration you prefer.

Let me make clear that this is really an array.

And, indeed, there's only so much shelf space.

Yuliia can't just kind of steal space over here to the right or over to the left.

We are limited in space, but she does have extra space here and technically here and here if she really wants it.

All right, how do I go about sorting a list of size 8?

Well, what was step one?

Sort the left half.

Step two, sort the right half.

Step three, merge the sorted halves.

That's all you have to remember.

So here's the original list.

How do I go about sorting the left half-- sorry, how do I go about sorting the original list?

I go ahead and I sort the left half.

So Yuliia's kindly going to act this out by just using some additional space.

I'll do it digitally here.

This now is a list of size 4.

How do I sort a list of size 4?

Well, I've got an algorithm for that.

Sort left half, sort right half, merge the sorted halves.

So let's do this.

Let's go ahead and sort the left half of this list of size 4.

And now how do I sort this thing.

Well, this is now a list of size 2.

How do I sort a list of size 2?

Sort the left half, sort the right half, merge the two halves.

This is where things get kind of stupid temporarily.

OK, done sorting the left half, done sorting the right half.

But what's the magical third step?

Merge the two together.

How do I do that?

Left hand, right hand trick-- 6 and 3 are being compared.

3, of course, comes first and then 6.

So I have merged those two together.

And so now we have a sorted list of size 2, but this is still unsorted.

That's still unsorted.

So what came next?

How did I get to this point/ I sorted the left half.

I sorted the left half.

I sorted the left half, right half, I merged.

So what step comes next?

Sort the right half of that original half.

This is where it's hard to keep track of.

But if you take on faith, now I'm going to the right half.

How do I do that?

Sort the left half of that right half-- done, easy.

Sort the right half of that right half-- done.

That was easy.

Let's now merge together.

Left hand, right hand, which comes first?

1 obviously.

So I sort the 1 or I merge in the 1.

Now I merge in the 4.

Now, at this point in the story, I've got a sorted left half, I've got a sorted half.

What comes next?

Merge the sorted halves?

How do I do that?

Left hand, right hand-- 1 comes first.

So I merge that in.

3 and 4-- 3 comes first.

I merge that in.

6 and 4-- 4 comes first.

Now no more right hand, so I merge in the 6.

And now, not coincidentally, you see that we have sorted the left half, just like the short demo I did earlier.

That was a lot of work, a lot of talking.

We still have another half to go, but I'll do it more quickly.

Let's see how quickly we can do this.

How do I sort now the right half of the original list after sorting the left half?

Well, what do I do?

I go ahead and sort the right half.

All right, well, what does it mean to the right half?

I'm going to go ahead and sort the left half of the right half.

What does that then mean?

Sort the left half-- done.

Sort the right half-- done.

Merge the two halves.

2 and then-- 2?

OK, good, and then 5-- OK good.

And now the left half of the right half is sorted.

Now I sort the right half of the right half.

So I got the 7, 0, and I sort the 7-- done.

0-- done.

Now I've got to do the merge step pointing at left hand and right hand.

The 0 comes first, then the 7.

Now I have sorted the right half of the right half.

What's the third step?

Merge those two halves.

So I point left and right-- 0 comes first, then 2, then 5, then 7, and now I've sorted the right half.

This is like a really difficult price is right thing here.

So now we've got the sorted-- we've sorted the left half, we've sorted the right half.

What's the final, final step?

Merge the two halves.

And this is exactly what I did before.

So dramatically, as the lights come on with each of them, pointing at left and right, 0 comes first, then 1.

What comes next?

2 comes next, then 3, then 4, then 5, then 6, and a huge round of applause for Yuliia if we can once we hit, and 7.

[APPLAUSE] Thank you.

So she and I will debrief as to whether we need both of these visuals moving forward, but hopefully, it makes clear that all we're doing is this mindless, fairly bite-sized problem solving of sort left half, sort right half, merge the two halves.

And if we now consider just how much faster or slower that is than an algorithm like selection sort or bubble sort, let's see if we can't analyze this just a little bit.

We ended up having an entirely sorted array, but how did we actually get there?

Well, if we consider what the possible buckets are for asymptotic running times here, let's consider of breadcrumbs we might have left along the way if I didn't keep deleting things as I went.

So we started with these numbers up here, and at one point or another, we did all of this work that's pictured on the screen, even though it only was up on the screen briefly.

So, in other words, we started with one list, and then how many times did we divide it in half?

One time, two times, three times.

So sort of we did this dividing and conquering of the entire list three different times so we could get to these leaves, if you will.

And even though we won't-- we'll talk about this more in future weeks, if you've ever drawn a family tree, where you might have grandma and grandpa and then parents and then children and so forth, it's sort of like an upside down tree whose branches grow downward, where the leaves, so to speak, like the descendants, are at the very bottom of the tree.

And that's terminology we'll come back to in the coming weeks.

But how many times could we chop up this original array into smaller and smaller pieces?

Three times for each of these elements here.

Moreover, how many steps did it take to merge those lists back together?

Well, that's going to be the operative question.

It turns out that the number of times we were able to divide the original list in half and half and half to get to those very single stupid problems of single numbers was log base x2 of n.

You can do a bit of a sanity check here, whereby if you just do the mental math, if we had eight elements originally, and the answer to this question is 3, well, that actually kind of works out because log base 2 of 8 actually is 3, which describes exactly how many times we chop the problem up into smaller and smaller pieces.

But, again, there were some merging going on, whereby we actually wanted to merge those then-sorted lists together.

So how did we go about doing that?

Well, every time we merged, we only looked at or physically touched the number once before putting it into its place.

So my hands were constantly working their way through this list such that when we had the singletons-- done.

1 2, 3, 4, 5, 6, 7, 8-- work was done.

When we did this work, it was 1, 2, and then 3, 4, and then 5, 6, and then 7, 8 steps as well to merge those together.

Then it was 1, 2, 3, 4, 5, 6, 7, 8.

In other words, no matter what conceptual layer of this tree we are in, it was taking me n steps, or 8 specifically, to do that merging.

So what that then invites is what's the total amount of running time involved here?

Well, if you're doing n things log base 2n times, the total math works out to be n times log of n So that is to say, merge sort, unlike selection sort, unlike bubble sort, is in big O of n log n, which even if you vaguely remember your logarithms, log n is smaller than n.

So n times log n is definitely better that is smaller than n squared.

So if we consider our cheat sheet here of the possible running times that are common, merge sort is in big O of log n.

However, nothing I or Yuliia did took into account whether the list was already sorted or not.

So it's fair to say that the lower bound on merge sort's running time, even if the darn thing is already sorted, is also n log n.

Now that's not as good as n, but at least, in general, it's way better than n squared.

But here, again, is a trade-off.

If you want to have this nice, recursive solution using merge sort, you might not get a lower bound running time unless we go in and add more pseudocode that maybe does something silly, like check the list first.

If already sorted, quit.

And you just kind of special case it with a conditional.

But that's sort of a lower-level refinement that we won't bother with today.

But merge sort then is in n log n, as are, frankly, a lot of sorting algorithms that you would use in the real world or use in a library.

And so as our final flourish today, what we thought we would do is compare these three algorithms that we focused on-- selection sort, bubble sort, and merge sort.

In particular, what you're about to see is a visualization of some random data three different times.

The top chunk of data is going to be sorted with selection sort.

The bottom data is going to be sorted with bubble sort.

And the middle data is going to be sorted with merge sort.

And the goal here will be to actually assess and feel and hear what the difference is when you put a little more time, a little more thought, a little more effort into designing your code not only correctly but well and thus efficiently in order to solve problems more efficiently.

So if we could dramatically dim the lights, we will hit Play on this final flourish.

[MUSIC PLAYING] All right, the music just makes sorting fun, but that's it for CS50.

We'll see you next time.

[APPLAUSE] [MUSIC PLAYING]