>> Lecturer: All right.
Welcome back to CS50.
This is the end of Week 3.
Nothing stupid to start off with today on the overhead.
Instead I need eight of you if you would be so brave?
Yes, one, come on; okay, number two, come on up.
Don't look up.
No one is looking up in this area.
Three? Okay, come on up.
Again, you must be comfortable on camera.
You two, come on.
Okay, wait let's see, one, two, three, four, five,
you three in front here.
Yeah. We'll do some other awkward things in the future.
I promise.
Okay. So here we go.
If you could line up in that order up here on stage?
[ class noise ]
Perfect, perfect.
Okay, so if you guys could make yourselves look like that,
the first moment of awkwardness here is just to remind you
where we left off last time and that was the goal,
among the goals on Monday was to actually search numbers,
and we had a wonderful demonstration
that worked perfectly whereby Edward found the numbers
in question immediately, but at least the second time
around in theory he was able to assume
that the bottom most array was actually sorted.
So today we ask this question, how do you go
about sorting those numbers?
And for this now we need the ninth volunteer.
Yes, in the pink shirt there; come on down.
So, this gentleman here will be in charge
of the sorting demonstration.
So we have eight numbers, and if you would
as this gentleman comes down think
to yourself you've got eight humans here each
of which is representing an integer, how would you,
the human, go about sorting these folks and let's see
if yours actually coincides with?
>> Student: Adam.
>> Lecturer: With Adam's approach.
So, Adam, your goal here is simply to tell these eight what
to do and sort them from smallest on the left
to largest on the right.
>> Student: All right.
You and you switch.
Will you switch with him?
Will you go to the end, please?
And then will you come in between these two?
>> Lecturer: Round of applause, absolutely.
[ Applause ]
That was fantastic.
Okay. So, what was Adam's approach?
Can someone put into words what he just did?
What is the algorithm?
How would you specify this?
Not so many volunteers now.
Okay?
>> Student: Determine the least number and put
that in the first index and then repeat [inaudible].
>> Lecturer: Okay, good.
So look for the least, look for the smallest number,
pull that person out and tell them go to the beginning
and then repeat recursively so to speak do the same thing again
but with a problem that is ever so slightly smaller
and minus one instead of N and, in fact,
we got to the end result.
What was your actual approach?
>> Student: It was basically what you said except I also
tried to look to make sure not to change anyone that was
in their correct position already.
>> Lecturer: Okay, good.
So, we had a little optimization heuristic perhaps whereby
if someone was already in the right position,
we didn't move them at all thereby not wasting any cycles.
Okay, so let's see if we can't slap both a label on this
for the sake of discussion, but then also make some claim
as to the efficiency of what Adam just did.
So, let's see here could you go back
to the order you were just in?
Okay. So we pretty much just did what this gentleman said.
We selected so to speak the smallest element.
Is it this person?
This person.
Ah-ha, we found it and notice the one difference here.
So, the human, Adam, might have immediately gone
for obviously you're number one you go here,
but remember a computer is not going to be able to sort
of [inaudible] be able to know who is the smallest
and where they are because if you think
about how you would represent these eight humans,
what data structure as we'll call it would you use these days
and see?
So you'd use an array, which you might have had a list
in scratch, but an array even though it allows you random
access where you can jump randomly
to any one location just by indexing
into the array numerically by way of the square brackets,
that doesn't necessarily mean [inaudible]
that you know where to look.
So, for instance, your name is?
>> Student: Gabrielle.
>> Lecturer: Gabrielle.
So Adam didn't necessarily know that Gabrielle was
in index location zero, one, two, three, four; he only knew
that presumably because as a human he very quickly scanned
the list, but much like a computer he had
to start somewhere so start at the left and move to the right
and then finally he saw Gabrielle and then just
to push a little harder here once you found Gabrielle did you
know this was the smallest element?
>> Student: I did.
>> Lecturer: Okay, you did, why?
>> Student: Because I had seen all the other elements.
>> Lecturer: Okay, good.
So, there's at least some knowledge in advance here
as to what the numbers are so he at least was able
to optimize there, but in the worst case
if you didn't have this little cheat sheet that's 20 feet high
over here, what would you have had to do to find
that smallest element?
>> Student: Check the last three.
>> Lecturer: Okay, good.
So check the last element.
So maximally finding Gabrielle
or more generally finding the smallest element would take
from the audience how many steps?
Okay so N steps, right?
You start here, you check four.
Okay, four is actually the smallest element I've seen,
but let me keep looking.
Oh, two is even better;
let's forget about, what was your name?
>> Student: Praya [phonetic].
>> Lecturer: Praya.
Let's forget about Praya because we've just now found?
>> Student: Juliana.
>> Lecturer: Juliana, who's number is smaller so now think
about how you would implement this I just need to keep
around it seems a variable, I or N or whatever that keeps track
of maybe what the smallest value is or at least where it is.
So, index location 1 and then I keep going, keep going,
keep going, finally I get to Gabrielle
and I update my variable because I found something better
than Juliana and now I keep going and then I get
to these guys and realize that was a waste of time
because I've already found the smallest element.
So, I pull Gabrielle out
and then what did you tell her to do exactly?
>> Student: Switch with Praya I believe.
>> Lecturer: Excellent.
Okay, good.
So notice, and if you could implement this in reality,
so we've switched them and this was actually pretty smart
because what would another approach have been to make room
for Gabrielle down here?
Yeah?
>> Student: Maybe [inaudible] one extra spot.
>> Lecturer: Okay.
So we could make another array, and we'll see
in time how you can create arrays in advanced that are
as big as you'd like them subject to RAM constraints
so we could just kind of make a bunch
of blank space then start filling in the holes.
What would another approach be as opposed
to just having these two swap?
So we could shift people, right?
If you could go back to your original locations
for just a second?
Another very reasonable approach would have been to say, okay,
come out to the line if you would.
You guys make room, she's got to go into the front of the list,
but that's another one, two, three, four steps just
to make room now for Gabrielle.
So, we have a couple of options here, right?
Clearly in a program it's going to take us N steps
to at least find Gabrielle
or more generally the smallest number, but even then
after that there's some clever decisions we can make
like as Adam did swapping the two instead of foolishly,
though correctly, shifting everyone down.
So let's now ask the question,
if this algorithm is essentially defined
as selecting the smallest person, moving them immediately
to the front of the list and then repeating
as this gentleman said, how many steps maximally is this
algorithm going to take to sort everyone?
So it's not as bad as N factorial, thankfully,
because that would actually get really slow really fast.
>> Student: A little less than N squared.
>> Lecturer: Oh, okay.
Say again?
>> Student: A little less than N square.
>> Lecturer: Yeah, it's actually a little less than N squared.
Well, why is that?
Well, let's see.
If I take N steps initially, I take N steps and I get here,
but now what do I have to do?
I essentially have to repeat,
but I can slightly optimize, right?
Because I already put Gabrielle in the right place
so I don't have to look at her number again
so now I have N minus one steps
and then the next iteration N minus two steps then N minus
three then N minus four dot, dot,
dot so that begs the question in the end,
what is N plus N minus one plus N minus two plus dot, dot,
dot down to one or down to zero?
What is that?
Anyone remember the little cheat sheet at the back
of your high school math book?
Yeah, so it's N times N plus one all over two,
which is roughly what?
N squared.
So, let me part the river here for just one moment.
Sorry, we'll get you some cough medicine shortly.
So, that series N plus N minus one --
I promise not to do too much math while you guys are standing
here -- plus, whoops, not N plus one,
N minus one plus N minus two plus dot, dot, dot,
plus all the way down to the very last step.
You may recall that this generalizes N times N plus one
over two, what does that equal?
Well, that's N squared plus N over two and now is
when we apparently have a way of expressing the running time
of this algorithm and we talked on Monday about big O and omega
and what those actually mean.
So, what's the worst case running time of this algorithm?
So it feels like it's big O of this.
So, big O of this thing here, but one of the rules of thumb
when it comes to talking about the running time
of an algorithm mathematically or formally like this is
when you start talking about really big values of N,
adding another little n like this doesn't really matter.
You start to care more about the degree,
the member in the formula that has the highest exponent,
for instance, because if N is not just eight
but N is a billon, well, N squared, a billion squared,
that's a really big damn number plus one more billion not
so material and so when we talk about big O notation,
we tend to get rid of the smaller terms and this divided
by two, I mean that's really not so interesting either
that we actually only did half as many steps
and the motivation conceptually
for this is essentially this idea.
When I started counting everyone linearly
in the lecture hall the other day, one, two, three,
we immediately improved on that.
That was a big O of N algorithm,
but I immediately started doing two, four, six, eight, ten.
So that's like an N over two algorithm
and mathematically N is slower than N over two
because I'm doing twice as many steps in the first version
and half as many steps in the second, but you know what?
If I wait 12 months, 18 months, you know, Intel is going to come
out with a faster CPU that, you know, tends historically
to be twice as fast and so over the course
of a year my algorithm naive though it was automatically gets
twice as fast, but that's not interesting.
We need to be able to abstract away from the running time
of me the human, the running, sorry, the speed of me,
the human, or the speed
of the machine implementing these algorithms
so that we can say something interesting
about the performance of algorithms independent
of however many gigahertz happens to be
in vogue at the moment.
So, with that said the big O running time
of this algorithm we would say it's just big O of N squared.
Now what about in the best case?
If you guys could realign as you were a moment ago,
this is not the best case,
but what would the best case scenario be
for Adam upon arriving on stage?
>> Student: Everyone already in the right place.
>> Lecturer: Okay.
So everyone is already in the right place.
So, if you could quickly sort yourselves from one
through eight so now Adam has just arrived on stage,
he is handed this array say with no other knowledge in advance,
if he applies that same algorithm of looking
for the smallest element, putting him or her
at the front then repeating
for the N minus one remaining elements then repeating
recursively, how many steps is the algorithm going
to take this time?
>> Student: Eight.
>> Lecturer: So it's actually not eight.
At least as we've described it here, it's the same number
because what does he not know upon each iteration of this
if we implement exactly the same algorithm?
>> Student: I'm still not sure it one is the smallest element
so I have to still check all the way down.
>> Lecturer: Exactly.
So, again, you can [inaudible] the cheat sheet that's up here
if Adam is the computer that's been handed this array
of eight numbers, it's wonderful that they're sorted,
but his algorithm is not designed
as we've just described it to really take that into account
because he's still going to start at the left and he's going
to realize, oh, wow, this is a really small number,
I'm going to remember this one bigger, bigger, bigger, bigger,
bigger, bigger, damn, I just wasted seven steps and
yet I had the winner at the very beginning, okay, so I'm going
to leave her where she is now let me repeat
for the remaining elements, all right?
Here is the small number, two, I'll remember this.
Bigger, bigger, bigger, ah, I've wasted more time, but I'm going
to keep wasting time because at least
with this algorithm defined as iteratively
or recursively selecting the smallest element
and plopping them at the beginning, there's no cognizance
of whether or not the list is already sorted.
Now, you might think well this is just stupid now, right?
Just keep track of whether
or not you've seen smaller numbers before and that's fine,
but that's a different algorithm then, right?
We need more memory for that
or we need a different set of steps.
So let's try one other approach at least here.
Could you guys reshuffle in this order?
And this is really random.
It doesn't matter what they reset to,
but at least this gets it done quickly.
So what might another approach be?
Let's tell Adam this time what to do rather
than leaving it to him.
How else could we go about sorting these eight people?
>> Student: Bubble sort.
>> Lecturer: Bubble sort.
What a wonderful lead in.
Okay, well, what does that mean?
Well, let's think about another very simple approach.
You know, this is a really kind
of overwhelming problem eight numbers, I'm the program,
this is a lot of work to do, let me keep it simple
and let me start at the left.
So, these two here are clearly out of order, four is bigger
than two, but two should be to the left
of four so you know what?
Let me just try a very simple algorithm
of swapping these two volunteers.
So we swap them.
That takes one step or maybe three steps if you think back
to our swap preparation, but a fixed number of steps,
a constant number of steps.
And that's okay.
We're more worried about recurring costs, all right?
So, now I compare four and six.
Oh, these two are actually in pretty good shape.
I'm going to leave them alone.
Six and eight, they're good.
Oh, eight and one, let me do a swap,
but again, I'm not backtracking.
I'm still making forward progressive.
Eight and three, got to swap these two; eight and seven,
going to swap these two; and then eight
and five going to swap these two.
Done, right?
All right so obviously not, right?
The list is not sorted.
So I've taken N steps here and done some swaps in the middle,
but any swaps were just constant time anyway.
It's always the same number of steps
to move two humans or to swap two ends.
So, what do I do now?
Well, let me try repeating.
Two and four, no, four and six?
Off six and one.
And now notice what's happening to Gabrielle this time.
Go ahead and swap.
So notice, and we can slap the label that's already been
applied to it on this algorithm.
The smallest number seems to be bubbling her way up to this end
of the list and meanwhile eight has already bubbled his way
up to the end of the list.
So this algorithm is, in fact, generally called bubble sort.
It is just as correct as the previous one that Adam proposed,
which was generally called selection sort
so that begs the question, is one better than the other?
Well, how many steps is bubble sort going to take?
So it's also N squared.
Now, why is that?
Let's see.
Every time I want to move from left to right I'm looking
at eight elements and maybe doing some constant number
of swaps.
So, some product of N am I doing through each iteration,
but in the worst case, who is where in this scenario?
So in the worst case, maybe Gabrielle is all the way
over here and this gentleman.
>> Student: Ravi [phonetic].
>> Lecturer: Ravi is all the way over there
so that then begs the question if on each iteration someone
like Ravi or Gabrielle only bubble up one place to the left
or one place to the right, how many times am I going to have
to repeat this process to pull Ravi all the way that way
or Gabrielle all the way this way?
Well, another N times or N minus one.
So I have to do N things N times
and that one conceptually is perhaps even easier
to wrap one's mind around.
It's big O of N square.
Now, I think we've had you up here
for an awkwardly long enough moment.
A big round of applause if we could for Adam and these guys?
[ Applause ]
Little souvenir and if you want, our paperwork awaits.
Thank you.
So, let's.
>> Student: [Inaudible].
>> Lecturer: No, no.
We don't need to do it every time.
We have you for life now.
All right so let me go ahead and show exactly what this means
for something to be taken N squared time
because we'll actually see
that N squared though very simply defined
and that was actually pretty simple to implement if you think
about it I've got a four loop then maybe another four loop
so I can pretty relatively easily translate what we just
did with Adam and team into code.
Well, let's see if we can't visualize it as well.
So this is a length that we have on the course's website
under lectures and it's just a really nice Java applet,
a program someone happened to write in Java,
works in a web browser,
that helps us visualize some of these algorithms.
If I go down here to this drop down if you want to play along
at home and I go choose bubble sorts, array type random,
it's just going to populate it randomly,
and this delay is just going to control the speed
of this demonstration.
I'm going to make it ten milliseconds or whatever this is
and now I'm going to go ahead and click start.
What we have here is more, a larger input set.
So, each of these bars represents a number or a human.
The taller the bar the bigger the number; the shorter the bar,
the shorter the number, the smaller the number.
So Gabrielle would be the small bar up here number one
and Ravi would be one of the larger bars at right.
That's the analog here.
So what's happening in red from left to right is
that this program is implementing bubble sort.
It's comparing pairs or neighbors of elements
and if they happen to be out of order, it swaps those two
but then forges ahead to do it again to the next pair
of neighbors and what you can see perhaps more easily
since this is a longer demonstration
that bigger numbers are, in fact, bubbling up albeit slowly
and smaller numbers are bubbling their way down.
Now this is only what, that looks like 30 or 40 bars total?
So N is not very large and granted we fixed the speed
of this thing, but it's already getting kind of boring.
So, N squared does not scale particularly well.
Sorting elements with even more than 40 elements or whatever is
up here definitely takes a while and let's see then
if selection sort does a little better.
So I'm going to go ahead
and choose selection sort as it's called.
I'm going to go ahead and click start, again,
and now notice less seems to be happening,
but that's because this algorithm is swapping bars
as far to the left as possible on each iteration.
So what's getting highlighted
in red is the then smallest element that's been discovered
say by Adam and then it's being moved all the way to the left.
So, what's a little neat about this algorithm is
that you can actually see the progress
and that definitely happened more quickly, right?
If we ran it again or you actually timed it,
I mean I'm still talking and
yet this thing is done selection sort seems to be faster
and that's because what I've crossed off here
for formality sake definitely has real-world implications.
So N squared is slower than N squared divided by two
for instance, but realize once we start talking
about really large data sets, the number of Face Book users
out there or the number of web pages that Google indexes,
this is when things like N squared
and these design decisions really start to hurt potentially
because they take more time
than you might necessarily have patience for.
So let's see if we can't express this in a way
that is more easily translated to code.
So here's bubble sort pseudo code for it.
You can write this in any number of ways,
but the algorithm essentially boiled
down to repeat the following N times.
For each of the elements in the array if I
as we'll call it iteratively and its neighbor are
out of order, swap them.
So this is, again, another lesson
in pseudo code what it means to communicate your ideas
without getting bogged down in uninteresting minutia [phonetic]
like syntax specific to C or any other language,
but with the expression
of pseudo code here you can see perhaps more clearly the actual
running time.
You can see in the very first line there repeat N times.
You have an explicit directive
that the following is going the take N steps,
but beneath that it says for each element I.
Well, how many elements are there?
There's N elements in the array so a four each loop is going
to induce another N step so you can immediately see
in the pseudo code alone
that this algorithm is apparently going
to take N times N steps to actually get the job done.
Now bubble sort actually allows for more optimization though.
So, when we had our eight volunteers up here,
we for the sake of selection sort told them to get
into proper order and then we asked the question how long
would it take to sort these elements using selection sort
in the best case, but we didn't ask that in bubble sort's case.
So, if in bubble sort's case you have eight humans here from one
on up to eight already sorted,
how many steps is this algorithm going to take as written?
>> Student: [Inaudible].
>> Lecturer: So I'm hearing a few answers among
which are N squared N, I heard seven, but it is, in fact,
again just look at the code if you will
and do the following N times for each of the elements
so N more things if I and its neighbor are
out of order, swap them.
No matter what this implementation
of bubble sort is just blindly telling you
to do the following N times,
N times this algorithm takes N squared steps.
So, if Adam had come on stage and realized,
had been handed an array of eight people all
of whom were sorted already, doesn't matter.
He's going to very blindly compare again and again
for a total of N squared steps all of the humans in that row
and then eventually he's going to stop because what's neat
about this algorithm at least is
that because you are doing it N times N times no matter what it
will have worked by the end, but there's clearly an opportunity
for optimization here.
So, bubble sort right now let's slap some numbers on these just
to have sort of a list and then see if we can't do better.
So bubble sort, so bubble sort thus far it seems
to be big O of N squared.
Selection sort seems to be also N O of N squared
but we also said it also is in omega of N squared because,
again, you just keep going through and going
through selecting the N smallest element but you don't know
in advanced that you found the smallest element
until you've checked.
So, is Omega a bubble sort better in this case?
So, no so can we do better?
How would you optimize this algorithm?
How would you after receiving some feedback
from your TF go back to the drawing board
and just add a couple lines of code to fix this, yeah?
>> Student: [Inaudible].
>> Lecturer: Yeah.
Okay, so keep track of how many switches you've made
by way of a variable.
So initialize some counter variable in there, initialize it
to zero and then as you iterate over all of the elements
if you actually execute this if condition and swap elements,
what should you do with this variable?
Little plus, plus.
Right? Or it could be a Boolean.
It could just be a Boolean
that says true I have swapped something because then
when I get to the end of the list and I meet Ravi,
who has been here the whole time because he's already sorted
and he's number eight, what do I then check before deciding
whether or not to repeat this algorithm?
>> Student: [Inaudible].
>> Lecturer: Right.
So if my variable equals equal zero,
don't waste your time going back to the beginning
and repeating this algorithm.
Instead do something like if variable equals equal zero,
new line, break.
So break is a syntax you might have seen in section
or some past examples you can forcibly exit a loop simply
by executing the statement break semicolon and so
that would be the easiest way of translating
that little optimization to code here.
So, what are the returns?
What then is the best case running time of bubble sort?
Yeah, it's just N and that's cool, right?
So that was easy.
Just by adding two lines of code and, again,
testament to this idea of putting up a little more effort
and thought and intellect into the design of an algorithm,
can you significantly chip away at the running time,
which as we saw on that big chart the other day,
something that's linear is much, much better as N gets really,
really large than something that's quadratic or polynomial.
So this is already a good thing, but it still feels pretty slow.
So is there another approach altogether?
Well, I'll wave my hands at some more pseudo code here
since once could write this in a number of ways
and this just expresses what Adam
and our volunteers already put forth to us, but it turns
out that this trick from Monday, this capability
of a functions calling itself is actually a really
powerful thing.
So, there exists this other algorithm called merge sort
and as the name implies, it boils down to taking an array
or taking a list more generally sorting half of it,
sorting the other half and then merging the results
and voila you then have a perfectly sorted list.
Well, how does this work?
Well, this is it.
So this is the pseudo code for merge sort.
It says on input of N elements so in the form
of an array first you do a sanity check.
If you've got fewer than two elements,
there's no work to be done, return.
And if you can recall the lingo from Monday,
that represents our base case
that actually prevents this thing from devolving
into a really bad infinite loop after which bad things,
segmentation faults and all of that happen.
So, else if you do have enough elements
to actually do interesting work on, what should you do?
So, sort the left half of elements, sort the right half
of elements, then merge the sorted halves.
Well, what does this mean exactly?
Well, if I have a list of eight numbers
and then I take the four numbers on the left and the four numbers
on the right, how do I go
about sorting the left half of those elements?
What would you do?
Right, I've got eight volunteers here who we have dismissed,
but pretend there's four people here, four people there,
I have to divide the list into two
so here's the four people I need to sort,
how can I sort half a list?
>> Student: [Inaudible].
>> Lecturer: How about in back?
>> Student: Cut it into quarters.
>> Lecturer: Cut it into three quarters?
>> Student: [Inaudible].
>> Lecturer: Okay.
So I could cut it in half again and again and again.
Okay. So finally I get down to Gabrielle or any
of our volunteers because I've cut my list of eight into four
into two into one, what do I need now with Gabrielle
or whoever I've found?
Can't go back to the laptop now.
You're on the hook.
>> Student: Oh, you just cut it in half,
cut in half and [inaudible].
>> Lecturer: Okay, true,
but then what do I do once I keep cutting the list in half?
Now I just have eight people, what do I do with them?
>> Student: Merge every two.
>> Lecturer: Okay, I merge every two.
Okay. So, you're actually going frankly in this direction,
but it seems like you're just kind
of weaving a circular argument around me, right?
I'm asking you how to sort an element
and I've already cut them in half.
You're telling me, oh, just cut them in half again
and then cut them in half again.
I feel like we're not actually getting to resolution here.
Yeah?
>> Student: Well, a single element [inaudible] and so
when you get down to one element sorted
and then you would merge it with another element [inaudible].
>> Lecturer: Okay.
>> Student: And then [inaudible]
and then those two pairs would be merged [inaudible]
so on and so forth.
>> Lecturer: Okay, good.
So to summarize maybe the magic here is not in this punting
in lines the second to bottom line.
When I say sort left half and sort right half, you know,
I'm kind of just punting on that
and saying go sort these elements then the magic seems
to be in the merging of sorted halves because if we kind
of think through the logic that's been proposed,
if I eventually get down to a list of one,
of size one just Gabrielle or just Ravi,
there's actually a really neat feature of that situation,
which is that Gabrielle as a single number is already sorted
by nature similarly as Ravi or any
of our eight volunteers already sorted if I try
to sort just them, but then I apparently need
to take a step back conceptually and say, okay, I've got a list
of length one, it's already sorted trivially
because that was really an uninteresting exercise,
but now I have two lists that sounds of size two.
So, I know this is going to happen,
but I will say let's take a five minute break think
about how we will solve this and then we'll reveal the answer
after you've not actually thought about it.
[ Break ]
>> Lecturer: All right so we are back.
Here are, we'll do this one without humans,
but here are the same numbers
that our volunteers represented the motivation here
to make sure the context is clear is to do better
than N squared and even though the algorithms we demonstrated
both with humans and with computers up top,
hasn't taken terribly long realize that we only had, again,
30 or 40 bars on the screen that we're getting sorted and even
that was relatively slow, but the goal here will be
to compare just how quickly or how much better we can do if,
again, we inject a little more intelligence and start
to deploy some more sophisticated techniques
like this thing called recursion on Monday,
which at the time very uninteresting
to implement factorial or sigma, the summation function
with recursion because we already had other ways of doing
that but as in this case as we'll see,
sometimes recursion lends itself to the expression
of an algorithm that would just be much harder
to express iteratively or with lots of loops and variables.
So here's our algorithm and let's see
if we can apply this here.
So here's our eight elements.
The first step is to on input of N elements,
if N is less than two, return.
No, N is actually eight so I'm not going to return
so else I do the following.
Sort the left half of elements.
So, somehow I need to do something
with these guys here, no.
With these guys here so real-world bugs as well,
and then I'm going to move on the those, but not just yet.
So, I've called a function essentially sort left half
of elements.
So I need a way of sorting these four elements.
What algorithm might I apply to these four elements?
So, I've got bubble sorts, I've got selection sort,
but feels like if I deploy one
of the algorithms we've already dissected and analyzed
and used it twice that we're not really going
to make a fundamentally important step forward,
but you know, we do have a new sorting algorithm supposedly.
We don't know if it works, we haven't seen how it works,
but it is called merge sort so let's take this leap of faith
and sort the four elements on the left half
with the same algorithm, merge sort.
So you'll have a little bit of stories piling
up in one's brain here as we do this recursively,
but here we go.
So, I've just sorted, I need to sort the left half,
that's these four elements,
which means I'm invoking merge sort N is now four,
is four less than two?
No. So I do the else sort left half of elements.
Well, what does that mean?
That means I now need to sort these elements here,
okay, what does that mean?
How do I sort two elements?
Let's deploy merge sort.
So, call merge sort on a list of size two.
Is two less than two?
No. So, I proceed to do the else construct
yet again sort the left half of elements and here I go.
I now sort the left half of elements and voila,
I seem again, I seem already to be at the point
where I have a list that's now size one.
So is one less than two?
Yes, finally.
So I return immediately.
Now, at this point in the story I've got a list
of size one what was the next step
if you roll back in time now?
So, sort the right half, the right half in question
at this moment in time having called merge sort multiple times
already was sort the left half,
now I need to sort the right half.
So, I'm down at this point here.
Sort two is trivial to sort because if N equals one is less
than two I return so now I'm at this point
in the story what do I do with four and two?
I've got two lists of size one and the goal now is
to merge these sorted halves.
How do I merge these sorted halves?
>> Student: [Inaudible]
>> Lecturer: Well, we can do this fair,
I mean we can do it verbally, all right, here's a list,
here's a list, I need to merge them somehow.
All right, who's going to come first in the merged list?
Two obviously.
So, I'm going to make some extra space here.
We'll call this I need actually in reality extra memory
for merge sort so I'm just going to give myself an extra array,
some blank space that I can start writing
on so here's two lists, I've already plucked off the two,
I advance to the next element
in list there's nothing there so who comes next?
So four. So, now I'm at this point in the story,
and I have a list of size two that's been sorted,
where did we leave off in the story now?
>> Student: Six and eight.
>> Lecturer: So six and eight, right?
Because this was the left half but then this was the left half
of the left half, we sorted him, then we sorted the right half
of the left half, that was easy, then we merged the left half
of the left half with the right half of the left half,
and we got two and four.
So, I realize this is actually a little confusing
but that's why we're actually doing a fairly small
example here.
Two and four now are sorted so who is their counterpart?
Who is their right-hand side?
That's these guys.
So, how do I sort the right half of this list?
All right, I sort the left half of this list first, okay,
now I sort, that's already done because it's a list of size one;
now I sort the right half of this list,
that's already done, what do I do now?
What's the third step in this sorting process?
So I still need to merge them.
We, the [inaudible] humans can see they're already in order,
but we as the computer don't know in advanced
until we actually look at them so let's look at them.
I've got a list of size one, a list of size one,
which one is going to come first when I merge the two?
Obviously the six and then I advance this finger,
the list was only size one there's nothing there
so now I merge the remaining element six,
remaining element eight, so I've got six and eight.
At what point in the story am I?
We've rolled back almost to the beginning.
Right so I sorted the left half, which was here,
I sorted the right half so the third step here and final step
on the board is to merge the sorted halves.
So now I'm going to do the same algorithm and, again,
I tend to use my left and right finger when I need
to represent a loop that has maybe two different indices,
two different index variables.
So how do I sort, how do I merge these two lists?
Well, they're already sorted so I don't have to compare all
of the elements against every element, I just need to look
at the front of them because I already know
from my previous steps that I put the smallest elements there.
So I now need to merge this list and this list
so here's the two smallest elements.
I compare them.
Is two less than six?
Yeah, it is.
So, let me put this into my empty space.
Now I advance.
Okay, this time there's something there
so I don't just blindly take the six,
I now compare four against six.
Obviously the four comes next, now I advance,
now there's nothing to compare
against so I can just finish my loop
over the six and over the eight.
So at this point in the story I've just finished which step?
>> Student: Sort.
>> Lecturer: Sort left half.
The very first time in this story
that I said sort the left half was to sort these four elements.
We finally completed that step, but notice what happened.
It induced that simple goal of sorting the left half
of elements, induced another call to merge sort, another call
to merge sort, another call to merge sort,
and then we merge the lists, but then we did the same thing.
Another call to merge sort, another call to merge sort,
then we merge the lists
and we're not even done yet.
So, it actually feels like we're doing a lot of work here,
but let's see if it pans out.
Well, on the right hand side if that's the next step,
I sort the right hand side of the list.
How do I do that?
Sort the left half.
All right so that's these two guys.
How do I do that?
Sort the left half.
All right, that's actually pretty easy, done.
It's a list of size one now I sort the right half.
Easy, it's a list of size one done.
Now the magic happens, but it's seemingly fairly simple,
merge them.
All right, so how do I do that?
I compare and I'm going to plop down one first then three.
These guys are now sorted.
Where am I at the story?
Now I sort the right half of the right half so that means look
at these two, chop it into left and right, do this, trivial,
it's already sorted do this, trivial, it's already sorted.
Now again the magical step of merging the two
and obviously we get out five and seven so now I have a list
of size two that's sorted, another list
of size two that's sorted, the left half
and right halves respectively of the right half of the original.
What's the last step?
To merge the sorted halves.
So, one and five I compare.
One comes first, now I compare three
and five, three comes next.
Now I'm out of numbers there so five
and seven get plopped down am I done?
Not quite.
Merge sort boils down essentially to three lines
of code; sort left half, sort right half, and I've done that
and I've done that and now the third and final step
of merge sort is to merge those sorted halves.
So what do I do?
Well, I'm running out of board space,
but I don't think it'll be all that enlightening to know
that the numbers are now going to get merged as one,
two, three, four, but how?
Well, again, remember the two index variables.
I've got on the start of this list, one on this one,
I compare the two fingers, one comes first so I write down one.
Then I advance this finger.
Now, I compare two against three.
I put down two and I advance this finger.
And the point of this little finger demonstration is
to make clear that at no point is my left
or right finger going backwards on the board.
They're always making forward progress.
In other words, every time I merge,
I'm touching physically N elements
or put another way I'm touching every number once and only once
because once I've touched it, I advance and move forward again.
I never double back.
So, in other words from left the right,
I seem to be conceptually always taking N steps
in this direction.
Every time I do merging, there's N steps involved
because I'm touching every number once
but never going backwards.
So that then begs the question on the other axis here,
how many times did I go down in this list?
How many times did I chop lists in half?
Because if I'm doing something N times this way,
hopefully I didn't chop the list N times this way.
Otherwise we've got an N squared algorithm
and this was all a waste of time,
but how many times per week zero can we take a list of size N
or a list of size eight and divide it in half, in half,
in half, and then bottom out with one element?
>> Student: [Inaudible].
>> Lecturer: So log base two of N. So even if you got lost
in some of the details, that's certainly fine
at first glance here, but just conceptually what was I doing?
Dividing the list in half, in half, in half, in half
and then I bottomed out with individual elements.
How many times can you do that?
Log N times, but every time I did that the goal was
to then merge all of the elements together as we tried
to do visually here so I'm doing something log N times
and then each time I'm doing N merging steps.
N moves with my fingers so this algorithm feels
like it should be big O of, and I'll write it here just
for the sake of reference, big O of N times log N,
and it's technically base two,
but just like we started scratching off constant numbers
before in the context of big O, the base also means very little
since it's just a constant value.
You can convert one base in binary
to any other constant value as well.
So if this depiction,
if I didn't do this depiction justice, let's just try to think
about it more abstractly.
If the problem at hand is to figure out what T of N is,
the running time of an algorithm whose input is
of size N how can we actually compute its running time
by looking at the pseudo code essentially?
So this is the algorithm.
The last time we talked about pseudo code we were able
to slap big O of N squared on it just by looking at it
so let's see if we can't translate this
to big O notation.
All right so this first line here if N is less
than two that's constant steps so there's a one in there
and something uninteresting.
Clearly the meaty part of this algorithm is down here
in the outs condition.
So, let's ask ourselves what is the running time
of this algorithm?
Well, if you had N elements, we need to figure out T of N,
which is just a fancy way of describing its running time.
So, what does that mean?
Well, computing T of N means you first sort the left half
of the list so that's T of what, N over two,
then you sort the right half, that's T over T of N over two.
So I don't know what the function is.
I don't know what T is yet, but I know it's going
to be the same thing but with an input that's half as big
and then finally how many steps does it take
to merge sorted halves?
Well, per my fingers moving slowly from left to right,
that's some number of N steps
because every finger moves forward once
and then they eventually both stop.
So we can express this even without quite knowing
where we're going yet with an algorithm like this.
T of N, the running time of an algorithm
with [inaudible] elements is the same thing as sorting half
of it, T of N over two, plus half of it, T of N over two,
plus N steps, but you know I'm kind of asking lots of questions
so maybe there's a constant factor in there.
So, here two, even in this context can we say the merging
takes linear time I don't know exactly if this is one step
to compare two elements or maybe this is two steps, but again,
these are constant values, who cares, let's just generalize it
as big O of N, but now we've kind of handed and turned
in an answer that itself is recursive.
What's the running time of this algorithm?
Well, it's the running time of running the algorithm on half
of itself and half of itself.
Like we haven't really made progress per se, but let's see
if the number at least pan out.
So how long does it take to sort not eight,
but we can do a little more interesting than that,
16 elements, but it's still a power of two just
so that the math works out perfectly even though
in reality there'd be some rounding.
So, let's just plug these numbers into the formula.
So, the formula, again is T of N equals T of N over two plus T
of N over two plus some linear time.
So let's do it.
How long does it take to sort 16 elements?
Well, T of 16 is T of eight plus T of eight or two times T
of eight plus 16 to do the merging.
So sort the left half, sort the right half plus the merging.
Unfortunately, we've again gotten caught
in a little circular argument here
because now the question is, what is T of eight then?
All right, well T of eight is the process
of sorting the left half, which is now size four,
plus sorting the right half, which is also size four
so T times two of T of four plus eight.
All right, what is the answer to T of four?
Well, T of four is now this, two times T of two, plus four.
What is T of two?
Well, T of two is two times T of one
and hopefully we're now going to bottom out
and not get stuck in this loop.
Ah, T of one is just zero
because how long does it take to sort one element?
Well, no time.
It's already sorted.
That's when we returned immediately.
So now we just have some high school arithmetic,
a little substitution here.
I now can fill in T of one then I can fill in T of two,
and then it bobbles back up so if we do out the math,
and I just flip the numbers
around so I can do the substitution from top to bottom,
it looks like T of 16 is ultimately two times T
of eight, but what is that?
Well, that is just the answer to T of eight,
which is apparently twenty-four, if you go through the math.
So long story short T of 16 is 64 steps.
Does this jive with the claim
that the running time is big O of N times log N?
>> Student: Yes.
>> Lecturer: Yeah.
So 16, right, so if the running time here is N times log N.
So N is 16, that's 16 times log base two
of sixteen that's four so, yes, so sixteen times four, 32, 64.
It is, in fact, 64 steps so the claim ultimately is, in fact,
correct that merge sort takes 64 steps concretely
with 16 elements but more generally N times log N.
So what's the take away there?
Like who cares?
Right. There's no point in memorizing
that merge sort takes 64 steps or 64 seconds for inputs
of size 16 but what would the N squared algorithm have been?
How long would bubble sort have taken?
How long would selection sort have taken?
Sixteen squared and that's if you do the math 256
and these are small inputs.
Now I'm comparing 256 steps against 64 steps.
Already the math is starting to work out in our favor,
and if you think back to the slide where we had those graphs,
when N really gets big do these numbers really start to hurt.
Well, it turns out there are other algorithms to be fair
out there so we'll see things over time whether in sections
or in future CS classes things called heap sorts
and insertion sort, quick sort, rate sort, shell sort
and as an aside especially for one
of the hacker editions you might enjoy reading up on one or more
of these, but N log N for now is about as good as we'll try to do
but let's just see exactly how good that is.
All right so here we have the second demo.
This, too, is linked on the course's website.
This is just another Java applet
that someone very nicely put together and each
of these drop downs is a whole bunch of sorting algorithms.
So the [inaudible] has had a lot of free time over the years
to come up with algorithms like bozo sort and stooge sort
and cocktail sort and a whole bunch of other silly ones
so apparently if you come up with a clever algorithm,
the fun part is you actually get to name it, but now we have
from left to right selection sort,
bubble sort and merge sort.
The question of the day was, can we do better
than these initial algorithms, bubble sort
and selection sort, and if so, who cares?
Why does it really matter?
What I'm about to do is click on each of these one right
after the other so that these things essentially run
in lock step and let's see what it means for something to be
in N log in as opposed to N squared.
Apparently not much.
There we go.
Done. And with that we'll see you Monday.