>> JASON HIRSCHHORN: Welcome to week three, everyone.
We have a busy but exciting section ahead of us.
So first, because we have made some headway with the course but we still
have a lot of learning left to do, I'm going to show you guys some resources
that should prove to be incredibly helpful as you not only approach your
problem sets, but also digest all of the material we give you guys in
lectures and shorts and section.
>> Then we're going to spend the first 20 to 25 minutes of section going over
GDB, which you may or may not have used at this point, but it is an
incredibly helpful tool that will help you debug your programs.
A lot of you may have used printf in the middle of your program to figure
out what a variable equaled.
GDB is even better than printf and doesn't screw up your code because you
run it on an executable file.
So we'll go over the 10 most helpful commands you need for GDB, and we're
going to go on an exercise together so in problem set three and beyond, you
can use GDB to help debug your programs.
And finally, we're going to go over some sorting and searching algorithms
that you saw in lecture, and we are going to actually code, not just
pseudocode, but code binary search, bubble sort, and selection sort.
>> So first, I want to go over the resources.
This is an extensive list, and it's smaller font because I had a lot to
fit on here.
But these will not only help you, again, with the problem sets and
digesting information you learned, but definitely, come quiz time, these will
be incredibly helpful.
So first, the lecture notes.
If you go to cs50.net/lectures and scroll to the specific week and day,
you'll see that there are notes for each lecture, which is not simply a
transcript, but an edited version of what was covered in lecture with code
snippets and other helpful tidbits.
I highly recommend going over those.
And then as well, there's source code available from each lecture.
And again, these slides will also be available online at cs50.net/sections
this evening.
>> So second are the shorts each week that cover topics, usually 5 to 15
minutes in length.
And those hopefully will give you a great primer on different topics.
Third--
and this is brand new this year-- is study.cs50.net.
If you have not checked it out, I highly recommend that you do so.
You get to pick a topic.
We have dozens of topics on there.
So for example, you pick Functions.
It gives you some slides and notes on functions.
Those are actually the slides that TFs are encouraged to use during our
presentations in section.
There's also tips and tricks for dealing with functions, and there's
practice problems that help you work with functions.
We also give you links to the short on functions and the times that functions
have come up in lecture.
So study.cs50.net, brand new this year, a fantastic resource.
>> Next, I have man, which is the manual command that you can run at the
command line.
So if you have any questions about a command, for example, rand, which we
encountered last week during section and you have likely encountered in
your problem set when going through the generate code, but if you type man
rand, you'll get the page that tells you all about rand.
It gives you what it takes, the parameters it takes, as well as return
type and a brief description of that function.
>> So check out rand.
It can be a little wordy and confusing, so sometimes I find that
simply Googling what I want to know is the best way to find the answer.
So practice with Google.
Get good at Google.
It will become your best friend.
>> As well as Google, if you can't find it on Google, cs50.net/discuss, it's
the discussion forum.
Chances are if you have a question, one of your 700+ peers also has that
question and may have asked it already in the discuss
forums and have it answered.
So if you have a common question or you have a question that you think
maybe other people might have run into, check out cs50.net/discuss.
>> Finally, the last two, if you want to talk to a real human being, office
hours Monday through Friday.
There's also online office hours for extension students.
And last but certainly not least, me, exclamation point.
You all have my contact information.
If you need anything, please never hesitate to contact me.
Always feel free to do so.
Very few of you have added me on Gchat, so that has been disappointing,
but hopefully that'll change between this and next section.
Any questions so far on the resources?
Great.
>> Finally, another plug for feedback, sayat.me/cs50.
You can give me anonymous feedback on how I'm doing.
That was really helpful last week.
I got a couple of comments from you guys right after section, plus from
other students who watched it during the week, and it
was incredibly helpful.
I am going to try and limit my use of the word "sweet," but I will show my
enthusiasm and excitement in other ways.
But there were other additional substantive feedbacks,
both pluses and delta.
So please, I give you guys feedback on your problem sets.
Feel free to give me feedback on my teaching.
I'm here for you guys.
>> Great.
That is all I have for the first section.
Does anybody have any questions so far?
And I have a note for the control center.
Extension students have messaged me saying they're not getting any audio,
but that is out of my power to fix.
So hopefully, that gets resolved shortly.
If you're watching online, hi, but you can't hear me.
>> So first, we are going to go through GDB.
GDB, as I hinted at earlier, is a debugging tool
much better than printf.
So to get started with GDB, you guys, if you want to open up your appliance
and take the file that I emailed to you earlier-- this file will also be
available online in a bit--
and run GDB./ the name of the file.
First, of course, you have to compile file because GDB only works on
executable files.
>> But if you ever want to start GDB, the first thing you do,
you run GDB./ Caesar.
So that's the name of the program we're going to go with it right now.
So I'm going to write make Caesar, which will give me an executable file
here highlighted in green.
And then I'm going to run GDB./ Cesar.
>> And there you go.
You see we have some text telling me about the version of GDB, giving me
some warranty information, and then we have the GDP prompt, which looks sort
of like our command line prompt, but you see it's open
paren, GDB, close paren.
Before we continue and debug this file that I sent to you all, let's look at
some useful commands so we have a sense of what we are going to cover.
>> These commands are listed here in the order in which I generally use them.
So I start my program by running GBD./ name of the program,
in this case, Caesar.
And then the first thing I do 99.9% of the time is type break mean.
That sets a break point at main.
Essentially, what you're doing there is the program is going to stop at
main so you can start examining it line by line, rather than running all
the way through.
You can break at different points in your code, but main is generally a
good place to start.
>> The next command I run is run.
That starts the program running, and if you need to enter command line
arguments, you run it that command.
Run with the arguments.
So since we are going over a version of C, which is the program you guys
wrote for pset two--
this one, of course, has some bugs in it that hopefully we'll find--
we're going to run run with some command line arguments because Caesar,
as you guys know per the problem set spec, takes some
command line arguments.
>> The next couple of commands, the next one is actually called next.
That one takes you line by line through your program.
So hitting n then Enter takes you to the next line, executing
the previous line.
Step not only takes you to the next line, but it
takes you inside functions.
So if you have written a function in your code or if you want to explore a
to i, for example, you can hit s, and rather than going to the next line of
the file that you're going through right now, you'll actually step into
this function and see its code.
>> List shows you, in very user friendly format, the 10 or so lines around
where you currently are in your code so you can actually see the file
rather than having to swap back and forth between different views.
Print is like printf, as its name implies.
That shows you what a variable equals.
>> Info locals is really helpful.
This is a special version of print.
Info locals shows you all of the local variables, prints them all out for you
that are currently available.
So I generally, rather than having to print out the four variables that I'm
curious about if I'm in a for loop, for example, I just write info locals,
and it'll show me what my counter i equals, as well as the array that I'm
working on equals.
>> Finally, continue.
Typing break stops you at the break point.
You can walk through line by line with next and step.
Continue runs the program to your next break point or until completion if
there are no more break points.
Disable removes break points if you decided the break at main was
inappropriate, you want to set it somewhere else.
And finally q, quit, gets out of GDB.
>> So this program, ./ Caesar, we are going to look through right now and we
are going to use GDB to find the bugs in this program.
I ran this program earlier with Check 50, and I got one frown.
Everything it existed, it compiled, it passed a lot of the tests, but for
some reason, it did not pass the fifth test, turning BARFOO, all caps, into
E-D-U-I-R-R, all caps, using three as a key.
I got pretty close.
I got off by one letter.
So there's some small mistake in here.
I've looked through my code.
I couldn't figure it out.
Hopefully, you guys can help me figure out what this bug is.
>> So that's the error we're searching for.
Let's move into GDB.
Again, I've run GDB ./ Caesar, so now we're in GDB.
And what is the first thing I should do?
I've just entered GDB.
Somebody give me a good command to enter.
>> STUDENT: Break main.
>> JASON HIRSCHHORN: Break main.
Fantastic.
Let's type that in.
You guys can watch up here or follow along on your computers.
Break main, and you'll see a break point was set at--
it gives me some weird memory address, and it also gives me the line number.
If I were to look back at this file, I would realize that main
happened on line 21.
What should I run next?
Is my program running?
No.
So what should I run next?
>> STUDENT: Run.
>> JASON HIRSCHHORN: Run.
Should I just run run, or should I add some other things in?
>> STUDENT: Run with the argument.
>> JASON HIRSCHHORN: Run with the command arguments.
And since I'm debugging a very specific case, I should enter that
command line argument.
So I'll do run three, which is, again, the output I got from Check 50.
Starting program.
We go through a couple of lines.
You'll now see that we're on line 21.
How do I know that we're on line 21?
Because if you look to the left of my terminal window, there
it says line 21.
And that gives me, actually, the code that is at line 21.
So I misspoke earlier.
Main is not actually at line 21.
Main is a couple of lines above 21.
But at line 21, that's where we're breaking.
This line of code has not yet executed.
That's important.
The line you see has not been executed yet.
That's the next line of code you're about to execute.
>> So the next line, as you guys are probably familiar with, is this
condition checking to see if I have entered a command line argument.
And a to i, what is the second part of that doing?
What is a to i?
>> STUDENT: Changing it to an integer.
>> JASON HIRSCHHORN: Sorry?
>> STUDENT: It's changing the argument to an integer.
>> JASON HIRSCHHORN: So a to i changes arg v1 from a string to an integer.
And then what's it checking?
>> STUDENT: If there is a second command line argument, aside
from running the program.
>> JASON HIRSCHHORN: And what's the second half of this
Boolean expression checking?
This part over here, a to i?
>> STUDENT: If it's negative.
>> JASON HIRSCHHORN: Making sure what?
>> STUDENT: Making sure it is, in fact, positive.
>> JASON HIRSCHHORN: Exactly.
This is checking to see if it's negative, and if it is negative, I
have a feeling the next line might be me yelling at the user.
So let's hit end to execute this line.
We don't see that line that you guys maybe expected to see yelling at the
user and then returning, because this line did not execute.
I entered 3.
So I did, in fact, enter two command line arguments, and 3 is
greater than zero.
So we saw that line, we executed, but we did not step
inside the if condition.
>> So now, next, I see I'm setting int key equals a to i arg v1.
So that is me creating a variable key.
So if I print out key right now, because that allows you to see the
value inside the variable, key equals 47.
That's weird, but of course, that's because I haven't
executed that line yet.
So now if I hit n, execute that line, and do print key, key will equal 3,
which is what we expect it to equal.
>> So again, in GDB, the line you see you haven't executed yet.
You have to hit n or s or a number of other commands to actually
execute that line.
Print key.
Key's at 3.
So far, so good.
String is plain text.
Let's execute that line.
I'm getting a string from user.
>> Let's see in my Check 50, I enter BARFOO all caps, so
that's what I'll enter.
If I now print plain text.
You'll see it equals a string.
It gives me some other weird hexadecimal number, but it does in
fact say that my string is BARFOO.
If I wanted to see what key equaled at this point, how could I check key?
>> STUDENT: Print key.
>> JASON HIRSCHHORN: Print key, exactly.
And actually, there's a shortcut.
If you get tired of typing print, you can just type p.
So p key does the same exact thing.
And again, I see it equals 3.
>> If I wanted to find out what both key and BARFOO equaled at the same time
but I was tired of typing each one out individually, I
could type info locals.
That gives me key equals 3.
Plain text equals BARFOO.
It also gives me these two weird things at the top, this variable i and
this variable n.
>> Those are actually existing in my main program.
We haven't encountered them yet, but as a preview, those
exist in my for loop.
So right now, they equal some weird numbers because they haven't been
initialized yet, but they do still exist in memory, so they're just set
to some garbage value.
But we do see key in plain text right there.
>> So I'm going to execute this line, line 34, the for loop.
We're going to jump into the for loop by hitting n.
And we're inside the for loop.
We're at our first check.
And again, these should sort of look familiar to you because this was a
Caesar program that was written, but again, has some sort of bug.
>> And now if I do info locals, because I'm inside that for loop, you'll see
that i equals zero, as we expect.
That's what we set it to and initialized it to in the for loop.
n equals 6.
That also makes sense because we set it to the strlen of plain text.
So I like to do info locals or print to variable often to make sure that
everything is always what I expect it to equal.
In this case, everything is what I expect it to equal.
>> So let's start moving through this for loop.
The line I'm on is line 36, if plain text i is greater than a and plain
text i is less than or equal to z.
I know my problem is not with my first letter, it's with the second letter.
If we look back at Check 50, B goes to E fine.
I'm taking the A and leaving it as an A, not changing it to D. So
something's wrong with the second letter.
So I'm going to move there in a second.
>> But if I did want to check what plain text I equaled in this particular
case, I think it should be what?
What should plain text I equal in this first round through the for loop?
>> STUDENT: Zero?
>> JASON HIRSCHHORN: Plain text of I?
So it should be capital B. I, of course, equals zero, but plain text
bracket zero closed bracket equals B because strings, as we saw last week,
are array, so we're getting the first character from that.
So again, if I printed out plain text of I, I do, in fact, get the character
B. And that's neat, right?
I don't actually have plain text I. That's not one of the variables I set
or initialized, but you can print out a whole host of things
if you'd like to.
>> But let's move through.
If plain text I is greater than A and plain text I is less than or equal to
Z, that clearly is true because we have a capital B. I'm going to run
some command on it.
We saw that math last week, so we'll take it for granted that it works
right according to Check 50.
>> These curly braces, the first one showed that I was exiting the if
condition, the second one showed that I'm exiting the for loop.
And so now when I hit Next, we'll see we're back at the for loop again.
We're going through the for loop again.
Let's actually step into the second iteration of the for loop and type
info locals.
>> So we're in the second iteration of our for loop.
I equals 1, which we expect.
N equals 6, which we expect.
Key equals 3, which we expect.
And plain text, you'll see, equals EARFOO now, not BARFOO anymore because
in our previous iteration, the B was changed to a capital E. So we're about
to encounter the problem, so this is where we're going to
dive into the debugging.
But does anybody have any questions about what we've done so far?
Fantastic.
>> So we're about to execute this if condition, plain text bracket I closed
bracket greater than A and plain text I less than or equal to Z. But before
I go into that, because this is where I know my error is, I want to point
out plain text of I. So let's put print out.
It does equal the character A, so that seems so far, all is well and good.
>> So I expect this line per my logic, this line should be true.
It's a capital letter.
But if I hit n, we do realize that this line, in fact, did not execute.
I jumped down to the else if.
Why did that happen?
>> STUDENT: Because you have your condition of plain text is greater
than A, not equal or greater than.
>> JASON HIRSCHHORN: So I had my plain text I is greater than A, not greater
than or equal to.
So clearly, the capital A did not trigger this if condition, and we did
not step into it, and we did not do the necessary shift.
So that's it, actually.
I figured out my bug.
I could go back in my source file, change it, and update it and
run Check 50 again.
>> But we'll see, just for pedagogy's sake, if I keep going.
The else if doesn't execute either, but what instead equals is the command
that doesn't change.
So it's not changed at all, and if I print plain text here, we'll see going
through that for loop didn't, in fact, change that second character at all.
It's still a capital A.
>> So again, we debugged our error.
We realized that there was some logic missing.
And we debugged it ahead of time before actually executing that line,
but you would have noticed had we just hit Next and jump to that else if,
that means that that if condition was not true.
We did not, in fact, get the result we expected.
So then we could have been prompted, had we not been so astute, to look at
that if condition and check if, in fact, our condition should evaluate to
true in the current context.
>> That's all for debugging this program.
Does anybody have any questions?
What command could I hit to quit GDB?
Q. And then I'll be prompted, quit anyway?
Yes or no.
I'll hit yes, and I'll have quit GDB.
>> So that was a quick primer to GDB.
Actually, in a real scenario, I did this at office hours.
I GDBed this exact program at office hours with a student.
And if we go back to the commands we saw before, we used break main, first
thing we did.
We used run with command line arguments, second thing we did.
We used next a lot to move us through lines.
And again, the short version of next is n.
That's in the parentheses in gray on the slide.
>> We did not use step, but we didn't necessarily need to for this case.
But we might use it in a bit later on today if we are debugging, for
example, binary search when binary search is called in a separate
function but there's some error with it.
We're going to want to step into the call to binary search and
actually debug it.
List we didn't use either because we had a good sense of our code, but if I
did want to get a sense of what code I was around, I could just use list.
>> Print we used, info locals we used.
Continue we didn't need to use in this case, neither did we need to use
disable, but we did use quit.
Again, these 10 commands, practice them.
If you understand these 10 commands, you should be set for debugging any
issue with GDB.
>> So we're about to go on, again, to the crux of section today, going over
these sorting and searching algorithms.
Before we do so, again, any questions, comments, concerns for GDB?
So is everybody going to use GDB rather than printf?
So everybody, for perpetuity's sake, everybody is nodding their head right
now, so I will see you at office hours and all the TFs will see you and
they'll say, show me how to use GDB, and you'll be able
to show them, right?
Kind of?
Maybe hopefully.
Cool.
>> So we're going to move into sorting and searching.
You'll see I have a list already sorted for us, but that is not going
to be the case always.
So in the problem set specification for problem set three, you have shorts
that you can watch, and it actually asks you to watch those shorts.
Also in lecture last week, we went over a lot of these algorithms, so I'm
not going to spend time in class going over these algorithms again or drawing
pictures for how these algorithms work.
Again, that information you can re-watch lecture, or that information
is captured outstandingly on the shorts for these searches, all of
which are available at cs50.net.
>> So instead, what we're going to do is write these programs.
We have a sense, a mental model, of how they work, and so what we're going
to do is code them for real.
We're going to turn that mental model, that picture, if you will, into the
actual code.
And if you were a little confused or hazy on the mental model, I totally
understand.
>> We're not actually going to jump to code straightaway.
So while this prompt in this slide asks you to code binary search, and
actually, an iterative version of binary search, the first thing I
really want you to do is write some pseudocode.
So you have this mental model of how binary search works.
Take out a sheet of paper if you have one readily available, or open up a
text editor, and I'd like everybody to write.
Take four minutes to write the pseudocode for binary search.
>> Again, think about that mental model.
I'll come around if you have questions and we can draw the picture out.
But first, before we start programming, I'd like to write the
pseudocode for binary search so when we dive in, we have some direction as
to where we should head.
>> STUDENT: Can we assume the array of values we get is already sorted?
>> JASON HIRSCHHORN: So for binary search to work-- excellent question-- you
have to take in a sorted array of values.
So assume it will work.
We'll go back to this slide.
You'll see in purple the function declaration is bool binary_search int
value, int values, int n.
This should look familiar if you've already approached or gotten your
hands dirty with the problem set.
>> But that's your function declaration.
Again, shouldn't need to worry about that much at this moment.
What I really want you to do is take four minutes to pseudocode binary
search, and then we'll go over that as a group.
And I will come around.
If you have questions, feel free to raise your hand.
>> Why don't you take two more minutes to finish up the pseudocode?
I know this may seem ridiculous that we're spending so much time on
something that's not even actually in C, but especially for these more
challenging algorithms and problem sets that we have to figure out,
starting in pseudocode not worrying about the syntax, just worrying about
the logic, is incredibly helpful.
And that way, you're not solving two incredibly difficult problems at once.
You're just focusing on the logic, and then you move into the syntax.
>> OK.
Let's start going through the pseudocode.
I have written up here, binary search pseudocode.
We'll write this on the board together.
Or I'll write it and you'll give me the prompts I need.
So can anybody give me the first line of the pseudocode you
wrote for binary search?
Yes, Annie?
>> STUDENT: While the length of the list is greater than zero.
>> JASON HIRSCHHORN: While length of list greater than zero.
And again, we see some C-looking syntactical things on here.
But most of this is in English.
Did anybody have any line they put before this in their pseudo-code?
>> STUDENT: Get an array of sorted numbers.
>> JASON HIRSCHHORN: You wrote "get an array of sorted numbers." Per the
function declaration, we'll be passing an array of sorted numbers.
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: So we will have that.
But yes, if we didn't have that, we would need to sort our array of
numbers, because binary search only works on sorted arrays.
So while length of list equals zero, I'm going to put in some curly braces
to make it look a little bit more like C. But while, seems to map onto a
while loop, so inside this while loop what do we need to
do for binary search?
>> Someone else who has not given me an answer yet but who wrote this?
>> STUDENT: Go to the middle of the list.
>> JASON HIRSCHHORN: Tom.
Go to the middle of the list.
And the follow-up question, what do we do once we're at the
middle of the list?
>> STUDENT: Do a check whether that's the number you're looking for.
>> JASON HIRSCHHORN: Excellent.
Go the middle of the list and check if our value is there--
fantastic.
Did anybody have anything else that was different than this?
That's exactly right.
>> The first thing we do in binary search is go to the middle of the list and
check to see if our value is there.
So I assume if our value is there, what do we do?
>> STUDENT: We return zero [INAUDIBLE].
>> JASON HIRSCHHORN: Yeah, if our value is there, we found it.
So we can tell some way, however this function is defined, we tell the user
we found it.
If it's not there, though, that's where this gets tricky.
So if it's not there, somebody else who was working on binary search or
has an idea now, what do we do?
>> STUDENT: Question.
>> JASON HIRSCHHORN: Yes?
>> STUDENT: Is the array already sorted?
>> JASON HIRSCHHORN: Yes, we're assuming the array is already sorted.
>> STUDENT: So then you have to check if the value that you see is greater than
the value that you want, you can move to the middle of the other half.
>> JASON HIRSCHHORN: So if the middle of the list is greater than what we're
looking for, then we do what?
We move where?
>> STUDENT: You want to move to the half of the list with
numbers lower than that.
>> JASON HIRSCHHORN: So we'll call that the left.
So if middle is greater, we can search the left half of the list.
And then by search, what do I mean by search?
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: We go to the middle.
We actually repeat this thing.
We go back through our while loop.
I'll give you the last one--
else, if, middle is less than what we do, what do we do here?
>> STUDENT: Go to the right.
>> JASON HIRSCHHORN: Search the right.
This looks good, but does anybody have anything that we may be missing or
anything else that you put in your pseudo-code?
So this is what we have so far.
While the length of the list is greater than zero, we're going to go
to the middle of the list and check if our value is there.
>> If the middle is greater, we're going to search left, else if the middle is
less, we're going to search the right.
So we've all had some familiarity with the terms we use in computer science
and the tools we have.
But you'll already notice we were speaking in English, but we found a
lot of things that seemed to map on to tools we have in our coding tool kit.
So right off the bat, we're not going to actually code yet.
>> What do we see here in English that maps on to things we can write in C?
>> STUDENT: While.
>> JASON HIRSCHHORN: While.
So this while right here maps on to what?
>> STUDENT: A while loop.
>> JASON HIRSCHHORN: A while loop?
Or probably, more generally, a loop.
We want to do something over and over.
So we're going to code a loop.
And we already know, because we've done this a couple of times and we
have plenty of examples out there, how actually to write
this index for a loop.
So that should be pretty easy.
We should be able to get that started pretty quickly.
>> What else do we see in here?
What other structures syntaxes, things that we're familiar with in C, do we
already have a sense of based off of the words we used?
Yes, Anna?
[INAUDIBLE]
just kidding.
Anna, go ahead.
>> STUDENT: If and else.
>> JASON HIRSCHHORN: If and else-- right here.
So what do those look like?
>> STUDENT: An if else statement.
>> JASON HIRSCHHORN: Yeah, conditions, right?
So we'll probably need to write some conditions.
And again, though maybe confusing at first, we generally have a sense now
of how to write conditions and the syntax for conditions.
And if we don't, we just look up the syntax for conditions, cut and paste
that, because we know we need a condition here.
Any other things we see that map onto things we might need to do in C?
Yeah, Aleha?
>> STUDENT: This might be obvious, by just checking if a
value equals something.
>> JASON HIRSCHHORN: So how do we check and-- so go to the middle of the list
and check if our value is there?
How do we do that in C?
What's the syntax for that?
>> STUDENT: Equals, equals.
>> JASON HIRSCHHORN: Equals, equals.
So this check is probably going to be an equals, equals.
So we'll know we need that somewhere.
And actually, just in writing it, we see those other things.
We're going to have to do some comparison operators in there--
fantastic.
So it actually looks like, by and large, we haven't written a
word of C code yet.
But we got the mental model down via lectures and those shorts.
>> We wrote pseudo-code as a group.
And already, we have 80% if not 90% of what we need to do.
Now, we just need to code it, which again, is a
non-trivial problem to solve.
But at least we're stuck on the logic.
At least now when we go to office hours, I can say, I know what I need
to do, but can you remind me of the syntax?
Or even if office hours are crowded, you can Google for the syntax, rather
than being stuck on the logic.
>> And again, rather than trying to solve the logic and the syntax problems all
at once, it is often much better to break those two hard problems off into
two more manageable ones and do the pseudo-code first and then code in C.
So let's see what I did for the pseudo-code ahead of time.
>> While the length of the list is greater than zero, look at the middle
of the list.
If number found returned true, else if number higher, search left.
Else if number lower, search right, return false.
So that looks almost identical if not nearly identical to what we wrote.
Actually, Tom, what you said first, breaking the middle of the list and if
number found into two statements is actually what I did.
>> I combined them there.
I should have listened to you the first time.
So that is the pseudo-code we have.
If you want to now, sorry, go back to our initial problem.
Let's code binary.c.
So implement an iterative version of binary search using the following
function declaration.
>> And you don't need to copy it down just yet.
I'm actually going to open up right here binary.c.
So there is the function declaration in the middle of the screen.
And you'll see I took the pseudo-code from on my sides, but almost identical
to what we wrote, and put that in for you.
So now, let's take five minutes to code this function.
>> And again, if you have any questions, raise your hand, let me know, I'll
come around.
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: So I took the binary search definition at the
top, on line 12.
That's what I got for my slide.
And then all this pseudo-code I just copy and pasted from the slide,
pseudo-code slide.
I'm still not hearing [INAUDIBLE].
>> So if you have finished your implementation, I want to check it.
I emailed you the helpers.h file earlier in this class.
And it will be available online as well for download for people watching
this section time delayed.
And I just used the generic distribution code from pset3.
So I took find.C, use my helpers.h file rather than the helpers.h file
that's given in the distribution code.
>> And I had to make one other change in find.C rather than calling just simply
search, call binary_search.
So if you want to test your code, know that that is how to do it.
In fact, when we'll be running this code right now, I just made a copy of
my pset3 directory, again, swapped out the helpers files and then made that
change in find.C to call binary_search rather than simply search.
>> JASON HIRSCHHORN: Yes.
You have a question?
>> STUDENT: Nevermind.
>> JASON HIRSCHHORN: No worries.
Well, let's get started.
We will code this as a group.
One other note.
Again, this is, can easily be swapped in for Problem Set Three.
I have my helpers.h file which, rather than the helpers.h we're given,
declares binary search, bubble sort, and selection sort.
And in find.c you'll notice on line, what is that, line 68, we call binary
search rather than search.
So again, the code that is available online or the code that you are
creating right now can be easily swapped in for p set 3 to check it.
>> But first, let's code binary search.
Our function declaration, we return a bool.
We take an integer called value.
We take an array of integers called values, and we take n be
the size of the array.
On line 10, right here, I have sharp include stdbool.h.
Does anybody know why that's there?
So what does that line of code do?
>> STUDENT: It allows you to use a bool return type.
>> JASON HIRSCHHORN: Exactly.
>> STUDENT: Or it's a library that allows to use a bool return type.
>> JASON HIRSCHHORN: So the sharp include stdbool.h line gives me some
definitions and declarations for things that I am allowed to use in
this library.
So among those is saying that there's this type called bool, and it can be
true or false.
So that's what that line does.
And if I didn't have that line, I would get in trouble for writing this
word right here, bool, right there.
Exactly right.
So I need that in this code.
OK.
So this, again, is an iterative version, not a recursive one.
So let us get started.
>> Let's start with this first line of pseudo code.
And hopefully, we will-- or not hopefully.
We're going to go around the room.
We'll go line by line, and I will help you figure out the line that we need
to write first.
So while length of list is greater than zero.
Let's start in the front.
What line should I write here, in code?
>> STUDENT: While parenthesis n is greater than 0.
>> JASON HIRSCHHORN: While n is great than 0.
So n is the size of a list, and we're checking if--
>> [INTERPOSING VOICES]
>> JASON HIRSCHHORN: --sorry?
>> STUDENT: How do we know that n is the size of the list?
>> JASON HIRSCHHORN: Sorry.
Per the pset specification, the search and sort functions you need to write,
n is the size of the list.
I forgot to explain that here.
But yes. n is the size of the list, in this case.
So while n is greater than 0.
OK.
That may prove a bit problematic though, if things go on.
Because we will continue to know the size of the list throughout this
function, but say we start off with an array of 5 integers.
And we go through and we've now narrowed it down to
an array of 2 integers.
Which 2 integers is that?
The size is 2 now that we want to look at, but which 2 is that?
Does that make sense, that question?
>> OK.
I'll ask it again.
So we start off with this array of 5 integers, and n equals 5, right?
We'll run through here.
we'll probably change the size, right, as things go on.
Which is what we say we want to do.
We don't want to search the full thing again.
So say we change it to 2.
We take half the list that's odd.
So just pick 2.
So now n equals 2.
I apologize for the poor dry erase markers.
Right?
And we're searching through the list again with a list of size 2.
Well, our array is still of size 5.
We say we only want to search 2 spots in it.
So which 2 spots are those?
>> Does that make sense?
Are they the left 2 spots?
Are they the right 2 spots?
Are they the middle 2 spots?
We have broken the problem down, but we actually don't know which part of
the problem we're still looking at, just by having these 2 variables.
So we need a little bit more then, while n is greater than 0.
We need to know where that n is in our actual array.
>> So does anybody have a change to this line?
Most of this line is perfectly correct.
Is there another addition?
Can we swap something out for n to make this line a bit better?
Mm-hm?
>> STUDENT: Can you initialize a variable like length to n that'll then be used
later in the function?
>> JASON HIRSCHHORN: So initialize a variable length to n,
and we use that later?
But then we just update length and we still run into this problem where we
cut down the length of our problem, but we never know where, actually,
that length maps onto.
>> STUDENT: Isn't that going to happen later when you're saying, search left,
search right?
You're going to go to a different area of your--
>> JASON HIRSCHHORN: We're going to go to an area, but how do we know
which are to go to?
If we only have the array and this n, how do we know where to
go to in the array.
In the back, yes?
>> STUDENT: Do you have, like, a lower bound and an upper bound variable or
something like that?
>> JASON HIRSCHHORN: OK.
So this is another idea.
Rather than just keeping track of the size, we keep track of the lower and
upper bound variable.
So how do we calculate the size from a lower bound and upper bound?
>> [INTERPOSING VOICES]
>> JASON HIRSCHHORN: Subtraction.
And also keeping track of the lower bound and upper bound to let us know,
are we searching these two?
Are we searching these two over here?
Are we searching the middle two?
Probably not the middle two, because this, in fact, is binary search.
But now we'll be able to get the size, but also the limits of the array.
In essence, if we have our giant phone book, we rip it in half.
We now know where that smaller phone book is.
But we're not actually ripping the phone book in half.
We still need to know where the new bounds of our problem is.
Does anybody have any questions about that?
Yes?
>> STUDENT: Would it work by creating a variable, i, that you then just shift
the position of i relative to its current position, and the length, n?
>> JASON HIRSCHHORN: And what is i?
>> STUDENT: Like i being like sort of--
Like you would initialize i to be the middle position of the array.
And then, if the value at position i in the middle of the array in found to
be less than the value you need, i now becomes the length of the array, plus
the value of i divided by 2.
Like, see, you shift i--
>> JASON HIRSCHHORN: Right.
>> STUDENT: --up to the--
>> JASON HIRSCHHORN: So I am almost positive that will work.
But the point being, you need two pieces of information here.
You can do it with beginning and end, or you can do it with size, and then
some marker.
But you do need two pieces of information here.
You can't get by with just one.
Does that makes sense?
>> So we're going to go through, and we're going to do [INAUDIBLE]
and create some markers.
So what'd you write in your code?
>> STUDENT: I just said int bound one is equal to 0.
>> JASON HIRSCHHORN: Let's call that int, beginning.
>> STUDENT: OK.
>> JASON HIRSCHHORN: That makes more sense for me.
And?
>> STUDENT: I said, I guess, int ending.
>> JASON HIRSCHHORN: int ending.
>> STUDENT: I guess, n minus 1, or something like that.
Like, the last element.
>> JASON HIRSCHHORN: So you wrote, int beginning equals 0, semicolon, and int
ending equals n minus 1, semicolon.
So essentially, what we're doing here, 0 the first position.
And as we know in arrays, they don't go up to n, they go up to n minus 1.
So we have some bounds of our array.
And these initial bounds happen to be the initial bounds of our problem.
OK.
So that sounds good.
Then if we go back to this line, while length of list is greater than 0,
what, instead of n, should we put in here?
>> STUDENT: Write ending minus beginning.
>> JASON HIRSCHHORN: While ending minus beginning is greater than 0?
OK.
And we could, if we wanted to make that a bit nicer, what
else could we do?
If we wanted to clean this code up a bit?
How can we get rid of the 0?
This is just a style question.
It's correct right now.
>> STUDENT: Ending doesn't equal beginning?
>> JASON HIRSCHHORN: We can do what?
>> [INTERPOSING VOICES]
>> STUDENT: Ending is greater?
>> JASON HIRSCHHORN: Yeah.
We can just do while ending is greater than beginning.
Right.
We added beginning to the other side of that, and we got rid of the 0.
So this just looks a little bit cleaner.
OK.
So, while length of list is 0, we wrote that, while ending is greater
than beginning.
We're going to put in our necessary curly braces, and then the first thing
we want to do is look at them in a little list.
You?
Can you give me the--
>> STUDENT: If parenthesis value square bracket--
>> JASON HIRSCHHORN: If parentheses value square bracket.
>> STUDENT: Ending divided by 2.
>> JASON HIRSCHHORN: Ending?
>> STUDENT: I see a problem with your--
>> JASON HIRSCHHORN: OK.
Well, look at the middle.
How do we know what the middle is?
Yeah.
So let me delete that code.
How do we know what the middle is?
In anything, when you have the beginning and the end, how do you find
the middle?
>> STUDENT: You average.
>> STUDENT: You add them together and then--
>> JASON HIRSCHHORN: Add them together and then?
>> STUDENT: And you average.
Divide it by 2.
>> JASON HIRSCHHORN: Add them together and divide by 2.
So int middle equals?
Tom, you can give it to me?
>> STUDENT: Beginning plus ending--
>> JASON HIRSCHHORN: Beginning plus ending.
>> STUDENT: All, bracket, divided by 2.
>> JASON HIRSCHHORN: All, in parentheses, divided by 2.
So that gives me the middle of anything, correct?
>> STUDENT: You also need to round it up.
>> JASON HIRSCHHORN: What do you mean, I need to round it up?
>> [INTERPOSING VOICES]
>> STUDENT: Because if It's an odd number, then it's like--
>> JASON HIRSCHHORN: Well, OK.
So I could round it up.
But if it's an odd number, a 5, I can taking 1 away from the middle.
Or if it's an even number, rather, that's a better case.
If it's 4, we only have 4, I can take the first "middle", quote, unquote or
the second "middle" one.
Either would work for a binary search, so I don't actually need to round it.
But there is one other thing I need to look at this line.
We might not realize it yet, but we'll come back to it.
Because this line actually still needs one other thing.
>> But so far, we've written four lines of code.
We've got our beginning and ending markers.
We have our while loop, which maps on directly to our pseudocode.
We're looking at the middle that maps directly onto our pseudocode.
I would say this goes to the middle of the list, this line of code.
And then, once we go to the middle of the list, the next thing we need to do
is check if our value is there for the pseudocode we wrote earlier.
>> So how do we check if our value is at the middle of the list?
You.
Why don't you do this?
>> STUDENT: If our value's is at the middle is equal to
whatever we set the--
I mean equal equal to--
>> JASON HIRSCHHORN: It--
OK.
>> STUDENT: I'm not sure what the variable we're looking
for though, is because--
>> [INTERPOSING VOICES]
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: Exactly.
Per the function declaration, we're looking for a value.
So we're searching for a value in an array of values.
So you're exactly right.
You will do, if open paren value bracket middle closed bracket equals
equals value, and inside there what do we need to do?
If our value's there, what do we need to do?
>> [INTERPOSING VOICES]
>> STUDENT: Return zero.
>> JASON HIRSCHHORN: Return true.
>> STUDENT: Return true.
>> JASON HIRSCHHORN: Michael, what does this line do?
>> STUDENT: [INAUDIBLE] the program has run its course, and that is over, and
you've what you need to do?
>> JASON HIRSCHHORN: The program or what?
In this case?
>> STUDENT: The function.
>> JASON HIRSCHHORN: The function.
And so, to return to whatever called it and give it the value, true.
Exactly right.
Main.
What's the return type of main, Michael?
>> STUDENT: int, integer?
>> JASON HIRSCHHORN: int, exactly.
An integer.
That was just a question to make sure you guys have been on top of it.
What does it usually return, if all things are working well?
>> STUDENT: Zero.
>> JASON HIRSCHHORN: Zero.
Exactly right.
>> STUDENT: If this just returns true, there's no information being given
about what the--
Oh, this is just saying that that value's inside the array.
>> JASON HIRSCHHORN: Exactly.
This program is not giving information of where exactly the value is.
It's only saying, yes, we found it, or no, we did not find it.
So if number found, return true.
Well, actually we just did that really quickly with that one line of code.
So I'll move that line of pseudocode.
>> STUDENT: Don't we need to change the array?
It should be values, not value, right?
>> JASON HIRSCHHORN: Sorry.
Thank you.
>> STUDENT: Yeah.
>> JASON HIRSCHHORN: This line should be values.
Exactly right.
OK.
So we've looked at the middle list.
If number found return true.
Continuing on with our pseudocode, if middle is greater, search left.
So I had in here, if number higher, search left.
Constantine, can you give me this line of code?
>> STUDENT: If value of middle--
>> JASON HIRSCHHORN: So if value--
if open paren values bracket middle close bracket--
>> STUDENT: Is smaller than value?
>> JASON HIRSCHHORN: Is less than.
>> STUDENT: Less than value.
>> JASON HIRSCHHORN: Value.
Well, actually, you want to check if the number--
Sorry.
This is a little confusing.
But else if the number in the middle of list is greater.
>> STUDENT: Oh, OK.
>> JASON HIRSCHHORN: I'll change that.
Else if middle is higher, we want to search left, OK?
And what do we do inside this if condition?
>> STUDENT: Can I make a small change to the condition, change it to else if?
>> JASON HIRSCHHORN: Else if?
OK.
So this code will execute about the same.
But the nice thing about using if, else if, else if or if, else if, else
means that only one of those is going to be checked, not all three of them,
potentially.
And that makes it a little bit nicer on the computer that's
running your program.
>> So [? Constantine, ?]
we're inside this line, else if values, bracket middle close bracket
is greater than value.
What do we need to do?
We need to search the left.
How do we do that?
I'm going to give you a start.
>> We have these two things called beginning and ending.
So what needs to happen to the beginning?
If you want to search the left of the list, we get our current beginning.
What do we need to do it?
>> STUDENT: We set the beginning to middle plus 1.
>> JASON HIRSCHHORN: So if we're searching the left?
>> STUDENT: Sorry, middle minus--
so the ending would be middle minus 1 and beginning--
>> JASON HIRSCHHORN: And what happens to the beginning?
>> STUDENT: It stays the same.
>> JASON HIRSCHHORN: So the meaning stays the same.
If we're searching the left, we're using the same beginning--
exactly right.
And the ending?
Sorry, what does the ending equal again?
>> STUDENT: Middle minus 1.
>> JASON HIRSCHHORN: Middle minus 1.
Now, why minus 1, not just middle?
>> STUDENT: The middle is out of the picture already, because we had
checked that it's out?
>> JASON HIRSCHHORN: That's exactly right.
The middle is out of the picture.
We already checked the middle.
So we don't want "the middle," quote unquote, to continue to be in the
array that we're looking.
So this is fantastic.
>> Else if values bracket middle is greater than value ending equals
middle minus 1.
Jeff, what about this last line?
>> STUDENT: Else.
Values middle is less than value?
>> JASON HIRSCHHORN: We'll you're giving me else.
So if you don't give me--
>> STUDENT: So then beginning would be middle plus 1.
>> JASON HIRSCHHORN: Beginning equals middle plus 1, again, for the same
reason that Constantine gave us earlier.
And at the end, who hasn't given me a line of code yet?
Return false, Aleha, what do we write here?
>> STUDENT: Return false.
>> JASON HIRSCHHORN: Return false.
And we need to do that, because if we don't find it, we need to say we
didn't find it.
And we said we're going to return a bool, so we definitely have to return
a bool somewhere.
>> So let's run this code.
I'm actually going to--
so we're in the terminal.
We'll clear our window.
Let's Make All.
We found there's one error.
There's an error on line 15, expected semicolon at the end of the
declaration.
So what did I forget?
>> STUDENT: Semicolon.
>> JASON HIRSCHHORN: Semicolon right up here.
I think that was Tom's code.
So Tom, [INAUDIBLE].
Just kidding.
Let's do Make All again.
>> STUDENT: What Dropbox directory should we be in for this?
>> JASON HIRSCHHORN: So you can just watch for this bit.
But again, if you wanted to move this code into your pset3 directory to try
it out, that's what I did.
If you'll notice here-- sorry, good question.
>> [? LS, ?]
I have in here the find.c code from this week's distro code.
I have helpers.h.
I have a Make file that I actually edited a bit to include these new
files we're writing.
All of that code will be available, not the distribution code, but the new
Make file, the new helpers.h file will be available online for download.
Again, so those are the extra codes we have.
>> So make all, per this line, makes find, binary, bubble selection-- makes
all three of them and compiles into this executable code find.
So generally, we don't want to straight to check50.
We want to run some tests on our own.
But just so we can expedite this a bit, check50 2013 pset3.find will pass
in helpers.c-- my bad.
>> I don't have that right now.
So we're actually going to run the code for real.
Usage.find/, you know what that means?
>> STUDENT: You need a second command line on it.
>> JASON HIRSCHHORN: I need a second command line.
And per the specification, I need to enter what we're looking for.
So let's look for 42.
We'll keep it in sorted, because we haven't written a sort function yet--
42, 43, 44.
>> And Control D didn't find the needle in the haystack.
That's bad.
It's definitely there.
Let's try something else.
Maybe it's because I put it at the beginning.
>> Let's do 41, 42, 43.
There we go.
It found it.
Let's put it at the end now, just so we can be thorough--
40, 41, 42.
Didn't find the needle.
So I mentioned this earlier.
Unfortunately, I knew this was going to happen.
>> But for pedagogical purposes, it's good to explore it.
It doesn't work.
For some reason, it can't find it.
We know what's in there, but we aren't finding it.
So one thing we could do is go through GDB to find it, but does anybody,
without going through GDB, have a sense of where we screwed up?
[? Madu? ?]
>> STUDENT: I think it might be when ending is equal to beginning, and it's
just a one-element list.
Then it just ignores it instead of actually checking it.
>> JASON HIRSCHHORN: That's exactly right.
When ending equals beginning, do we still have an element in our list?
>> STUDENT: Yes.
>> JASON HIRSCHHORN: Yes, in fact, we have one and only one element.
And that will most likely happen when, per the code we tested, we are at the
front of the haystack or at the end of the haystack.
That's where beginning and ending is going to equal
one, with binary search.
So in those two cases it didn't work, because ending was equal to beginning.
>> But if ending is equal to beginning, does this while loop execute?
It doesn't.
And we could have checked that again through GDB.
So how can we fix this code, because when while ending is equal to
beginning, we also want this while loop to run.
>> So what fix can we make to line 18?
>> STUDENT: [INAUDIBLE] is greater than or equal to.
>> JASON HIRSCHHORN: Exactly right.
While ending is greater than or equal to beginning.
So now, we make sure to get that corner case at the end.
And let's see.
Let's run this one more time.
>> Let's make all.
Again, you'll have to just follow along here.
Find 41 this time.
Just keep it consistent.
>> Find 42.
Let's put it at the beginning--
42, 43, 44.
We found it.
So that was indeed the change we needed to make.
>> That was a lot of coding we just did, binary search.
Does anybody have any questions before I move on into lines we wrote in
binary search or how we figured out what we did figure out?
Before we move on, I also want to point out that by and large, we mapped
our pseudo-code one to one onto our code.
>> We did have that tricky thing to figure out with the
beginning and ending.
But had you not figured that out, you would have written pretty much the
identical code, save for those top two lines.
And then you would have realized when you made it in checks and cases that
you need something else.
So even if you had followed our pseudo-code line to line, you would've
gotten all but two lines of code you needed to write.
>> And I'd be willing to bet that you guys would have all figured that out
pretty quickly, that you needed to put some sort of marker in there to figure
out where you were.
That again, is the power of doing pseudo-code ahead of time.
So we can do the logic first, and then we can worry about the syntax.
>> Had we been confused about the logic while trying to write this code in C,
we would have gotten all messed up.
And then we'd be asking questions about logic and syntax and meshing
them all together.
And we would have gotten lost in what can quickly become a
very difficult problem.
So let's move on now to selection sort.
>> We have 20 minutes left.
So I have a feeling we won't be able to get through all of selection sort
and bubble sort.
But let us at least attempt to finish selection sort.
So implement selection sort using the following function declaration.
>> Again, this is taken from the problem set specification.
Int values is brackets, is an array of integers.
And int.n is the size of that array.
Selection sort is going to sort this array.
>> So per our mental model of selection sort, we pull the--
first, we go through the list the first time, find the smallest number,
put it at the beginning, find the second smallest number, put it in the
second position if we want to sort in ascending order.
I'm not forcing you to write pseudo-code right now.
>> But before we do the code as a class in five minutes, we are going to write
pseudo-code so we have some sense of where we're going.
So attempt to write pseudo-code on your own.
And then attempt to turn that pseudo-code into code.
We will do that as a group in five minutes.
>> And of course, let me know if you have any questions.
>> STUDENT: That it?
>> JASON HIRSCHHORN: See how far you can get in two more minutes.
I understand you won't be able to finish.
But we will go over this as a group.
>> You're all coding so [INAUDIBLE], so I'm sorry to pause what you're doing.
But let's go through this as a group.
And again, binary search, you all give me one if not more lines of code.
Thank you for that.
We're going to do the same thing here, code together as a group.
>> So selection sort-- let's write some quick pseudo-code.
Per mental model, can someone give me the first line of pseudo-code, please?
What do I want to do?
>> STUDENT: While the list is out of order.
>> JASON HIRSCHHORN: OK, while the list is out of order.
And what do you mean "out of order?"
>> STUDENT: While [INAUDIBLE]
hasn't been sorted.
>> JASON HIRSCHHORN: While the list is out of order, what do we do?
Give me the second line, please, Marcus.
>> STUDENT: So find the next smallest number.
This will be indented.
>> JASON HIRSCHHORN: So find the next smallest number.
And then somebody else?
Once we find the next smallest number, what do we do?
I'm going to say find the smallest number.
That's what we want to do.
>> So find the smallest number.
Then what do we do?
>> STUDENT: [INAUDIBLE] to beginning.
>> JASON HIRSCHHORN: Sorry?
>> STUDENT: Place it in the beginning of the list.
>> JASON HIRSCHHORN: So place it in the beginning of the list.
And what do we do to the thing that was in the beginning
of the list, right?
We're overwriting something.
So where do we put that?
Yeah, Anna?
>> STUDENT: Where the smallest number was?
>> JASON HIRSHHORN: So put the beginning of the list where the
smallest number was.
So while the list is out of order, find the smallest number, place it in
the beginning of the list, put the beginning of the list where the
smallest number was.
Marcus, can you rephrase this line while the list is out of order?
>> STUDENT: While the numbers haven't been sorted?
>> JASON HIRSHHORN: OK, so in order to know that the numbers haven't been
sorted, what do we need to do?
How much do we need to go through this list?
>> STUDENT: So I guess a for loop, or while, while numbers checked is less
than the length of the list?
>> JASON HIRSHHORN: OK, that's good.
I think I misphrased my question poorly.
I was just trying to get at we're going to have to go
through the whole list.
So while the list is out of order, for me, is hard to map on.
But basically, that's how I think about this.
Go through the entire list, find the smallest number, place it in the
beginning-- actually, you're right.
Let's put them both.
>> So while the list is out of order, we need to go through the entire list
once, find the smallest number, place it in the beginning of the list, put
the beginning of the list where the smallest number was, and then if the
list is still out of order, we've got to go through this
process again, right?
That's why selection sort, Big-O runtime of selection sort, anyone?
>> STUDENT: n squared.
>> JASON HIRSHHORN: n squared.
Because like Marcus and I just realized here, we're going to have to
go through the list list number of times.
So going through something of length n n number of times
is in fact n squared.
>> So this is our pseudocode.
This looks very good.
Does anybody have any questions about the pseudocode?
Because actually selection sort should probably come one to one, code from
pseudocode.
So any questions about the logic of the pseudocode?
Please ask it now.
>> Selection sort-- while the list is out of order, we're going to go through it
and find the smallest each time and put it in the front.
So while the list is out of order, can somebody give me that line of code who
has not given me a line of code yet, please?
It sounds like a what?
>> STUDENT: That's a for loop.
>> JASON HIRSHHORN: It sounds like a for loop.
OK, can you give me the for loop?
For--
>> STUDENT: i Equals 0.
>> JASON HIRSHHORN: i or--
what are we missing?
What goes right here?
>> STUDENT: Int.
>> JASON HIRSHHORN: Exactly.
(int i = 0;--
>> STUDENT: i < n; i++).
>> JASON HIRSHHORN: Nailed it, Jeff.
We're going through the list, right?
We've seen that code before.
Perfect.
So let's put our curly braces here.
I'm going to put some curly braces here.
>> So while it's 0, we need to go through the entire list.
So each time we go through the list, what do we want to keep track of?
>> STUDENT: If any swaps are made.
>> JASON HIRSHHORN: Find the smallest number.
So we should probably keep track of the smallest number each time.
So line can I do to keep track of the smallest number?
Aleha, how can I keep track of something?
>> STUDENT: Start a new variable.
>> JASON HIRSHHORN: Start a new variable.
So let's create a variable.
What type?
>> STUDENT: Int.
>> JASON HIRSHHORN: Int.
Let's call it the smallest.
And what does it equal when we're just starting out?
We haven't gone through the list yet.
We're at the first part of the list our first time through.
What does it equal, the smallest number?
>> STUDENT: Values i.
>> JASON HIRSHHORN: Values i.
That sounds exactly right, right?
The smallest number at the beginning is where we are.
So now we have our smallest, and we need to go through the entire list and
compare this smallest to everything else.
So do we go through the list again?
Michael?
>> STUDENT: You need to make another for loop.
>> JASON HIRSHHORN: Another for loop.
Let's do it.
Give me some code.
>> STUDENT: For loop--
for the smallest--
just int j, could you say?
= 0; such that--
>> JASON HIRSHHORN: Well, if we want to go through the entire list--
>> STUDENT: j < n, j++).
>> JASON HIRSHHORN: Fantastic.
We're going to go through the for loop once again.
And how do we find the smallest number?
Tom?
We have the current smallest number, so how do we find the new smallest?
>> STUDENT: We can check if the smallest number we have is greater than
values bracket j.
>> JASON HIRSHHORN: So if smallest is greater than values bracket j.
So if our current smallest is greater than--
I'm going to move these two lines of code out there for a second.
Because before we do any swapping, we need to go through the entire list.
So this pseudocode should actually be outside that inner for loop.
So go through the entire list.
If smallest is greater than values j then what?
>> STUDENT: Then smallest equals values j.
>> JASON HIRSHHORN: Fantastic.
One quick question--
the first time we go through this loop, i's going to equal 0, j's going
to equal 0 once we get in here.
So we're going to be comparing a number to itself.
Is that efficient?
No, it's not really efficient.
So does our j need to go from 0 to n each time?
Do we always need to check through the entire list?
[INAUDIBLE]?
>> STUDENT: Start with i instead.
>> JASON HIRSHHORN: j can start with what?
>> STUDENT: i.
>> JASON HIRSHHORN: j can start with i.
So now we compare starting with the one we're on.
But even then, is that as efficient as possible?
>> STUDENT: i + 1.
>> JASON HIRSHHORN: i + 1 seems to be the most efficient, because we
already have i.
We're stating that as the smallest in line 15.
We're going to start with the next one automatically.
So we go through the for loop.
We'll go through each time.
We'll go through a number of times.
Now we've gotten through this inner for loop.
We have the smallest value saves.
We need to place it at the beginning of the list.
So how do I place it at the beginning of the list?
What is the variable that refers to the beginning of the list?
We're in this outside for loop, so what refers to the
beginning of the list?
>> STUDENT: Values i.
>> JASON HIRSHHORN: Exactly right.
Values i is the beginning of the--
or sorry, not the beginning.
That was confusing.
It's where we are in the beginning of the unsorted portion of the list.
So values i.
And what does that equal?
>> STUDENT: Smallest.
>> JASON HIRSHHORN: Values i equals what?
>> STUDENT: Smallest.
>> JASON HIRSHHORN: Smallest.
Exactly right.
So we're placing it at the beginning of the list, and now we need to put
the beginning of the list where the smallest number was.
So how do I write where the smallest number was?
Values of what?
>> STUDENT: 0.
>> JASON HIRSHHORN: The small number's at 0?
>> STUDENT: Yeah.
>> JASON HIRSHHORN: What if the smallest number was at the end of
this unsorted list?
>> STUDENT: Sorry, what was the question?
>> JASON HIRSHHORN: Where is the smallest number?
We took the smallest and put it at the beginning, with this line right here.
>> STUDENT: It should have been stored in some--
>> STUDENT: Values j.
>> JASON HIRSHHORN: Well, it's not necessarily values j.
It doesn't even exist at this point.
>> STUDENT: You have to declare a variable earlier and
then assign it to--
when you find the smallest number, assign the index of that number to
some variable or something like that.
>> JASON HIRSHHORN: So can you say that again?
>> STUDENT: So where you declared int smallest, you should also declare int
smallest index = i, or something like that.
>> JASON HIRSHHORN: So where I do int smallest, I should not only keep track
of the value but the location.
int smallest_location = in this case, we'll just do i.
We need to know where it is.
We got to the end of the code, and we realized we had no idea where it was.
And so again, we are mapping this on one to one.
You guys coding this on your own will probably get to the same problem.
How the heck do I find it?
And then you realize, wait, I need to keep track of that.
>> So if smallest is greater than values j.
We set smallest equals to values j.
What else do we need to change?
Constantin, what else do we need to change?
>> STUDENT: The location.
>> JASON HIRSHHORN: Exactly.
So give me that line in code.
>> STUDENT: smallest_location = j.
>> JASON HIRSHHORN: Exactly.
And then down at the end, if we want to put the beginning of the list where
the smallest number was, how do we refer to where the
smallest number was?
Marcus?
>> STUDENT: The smallest number was located at smallest location.
>> JASON HIRSHHORN: So at values smallest_location.
And what do we put there?
The beginning of the list, what's that?
>> STUDENT: Well, we don't really know anymore because we overwrote.
So it's a swapped locations of those two lines?
If you switch those two lines around.
>> JASON HIRSHHORN: OK, so we don't anymore, because we've reset the line
before values i to smallest.
So we lost that initial value.
So you said swap these two lines.
So now put the beginning of the list where the smallest number was.
So smallest_location equals values i.
That's moving the beginning of this unsorted portion of the list to the
smallest location.
And then into values i we're moving that smallest number.
>> Does that make sense why we had to make that swap?
We would have overwritten that value-- another thing you probably would have
figured out and found in GDP.
So we've taken care of all the pseudocode.
Is there anything else we need to write here?
Can anybody think of anything?
>> STUDENT: How do you know when you're done?
>> JASON HIRSHHORN: How do we know when we're done?
Great question.
So how do we know when we're done.
>> STUDENT: Create a variable to keep count of if there's a swap made or not
and go through a pass.
>> JASON HIRSHHORN: OK.
That would work in bubble sort.
But for selection sort, if we don't make a swap, that might just be
because the smallest value is in it its right location.
We might have a list 1, 2, 4, 3.
The second time through we won't make any swaps.
We'll be on the number 2, but we'll still need to keep going.
So do we need to keep track of when we're done, or do we just want to go
until this is finished?
>> STUDENT: We can just go until it's finished.
>> JASON HIRSHHORN: We can just go until this is finished.
In bubble sort, you're exactly right, Jeff and Aleha, with your solution--
it is great to keep track of how many swaps you made, because in bubble
sort, if you do in fact make no swaps, you're done and you can maybe cut your
problem down a bit.
But for selection sort, you've really got to go through to the end of the
list each time around.
>> So this is that.
We have two minutes left.
Let's make all.
Let me just open Find here and make sure I'm in fact calling up--
I'm not calling bubble sort.
Let's change this to selection sort.
make all ./ find.
Let's find 42.
This time we're going to pass an unsorted list, because it should sort
first, per the find code-- should sort first using our sort function and then
look for something.
Fingers crossed everyone.
>> Oh my goodness.
Whoa, my heart was beating.
So that is correct.
In fact, if we ran this more extensively, the code, as far as I can
tell, is perfectly correct.
There are some suggestions I would have for you.
For example, 15 and 16 seem a little redundant.
It seems like you don't necessarily need to save both those.
If you have the smallest location, you can easily find the smallest value by
just typing values of i.
>> So if I were to be grading your code, which I will in fact be, I would
probably take off a point if you included both of these, because you
don't need both of these.
If you have the location, you can very easily get the value.
And it seems a little weird to store both of them.
Maybe not even take a point, but certainly comment that that is maybe
not a stylistic choice you need to make.
Of course, the code still runs perfectly well.
>> So unfortunately we didn't get to bubble sort.
I'm sorry about that.
We did finish selection sort.
Does anybody have any final questions about selection sort?
>> OK, before we head out, I want you to open up your Chrome browser.
Sorry, that was just a blatant plug for one type of internet browser.
You can open up any type of browser, but it'll probably be Chrome.
And go to this following website--
sayat.me/cs50.
If you're not typing in your computer right now, you're clearly
not doing it, Tom.
>> And please do it either right now or in the next hour--
give me some feedback.
This is only section two.
We have many more together, so I have a lot of room to improve.
I hopefully also did some things well.
So you can make me feel all bad, but if you also want to give me a smiley
face, I would appreciate that as well.
Fill that in.
>> And with one minute left, that was week three.
I'll stand outside for a bit if you have any questions.
I will see you guys in lecture tomorrow.