[ Silence ]
>> Alright, welcome back!
This is the start of week 4 and this is CS50,
and this is an actual receipt that floated around online
after someone photographed it.
It perhaps speaks to what goes wrong when you have the problem
of floating point imprecision, particularly bad
if it's a cash register.
This is-- just to zoom in--
this is the receipt from a restaurant.
And again, things should probably not cost 1.48999 cents,
probably unintentional.
But computers make mistake
and apparently people buy computers with mistakes.
So, looking ahead to this week, so Problem Set 3 introduces you
to this sort of age old game of The Game of 15,
whereby you've got a board like this and the goal is
to move the puzzle pieces up, down, left to right
so that you've ordered them ultimately from top to bottom,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 with a blank
in the bottom right hand corner
so the problem set this week introduces you too
for the first time to something we'll call Distribution Code,
Distro Code.
Something that someone else wrote,
in this case it's code written by us but we stop short
of implementing this whole game and rather we left blanks,
little holes for you to fill in throughout the frameworks
so that the goal of this game is really twofold
so far as the P set goes.
One is understanding someone else's code, so not diving
in with a blank slate and figuring out how
to implement the whole thing from scratch,
but rather understanding how a framework works that we provide
and you'll see its all nicely commented and indented,
and we then direct you toward the holes you need to fill
in with code of your own.
Now, those of you enticed with this Hacker Edition will know
that the goal is not to implement the game per se,
but a solver for the game.
So that if you actually play this thing rather
than be the human typing in the number 3 and 4 and 15
to move the puzzle pieces around,
instead you will type G-O-D in all caps, and voila!
The computer will solve this problem for you
and its quite fun to see it happening live animatedly.
So you can play with the Hacker Edition even
if you're doing standard in the appliance
because we've included the solutions to both--
in CS50's own directory.
So also as part of this problem set is an opportunity to dabble
with the couple of sorts and searches so you'll be asked
to implement essentially binary search
and we talked about binary search.
We looked at Sean's implementation
of binary search on video last week.
And there's a couple of ways you can implement it
if you look back at the walkthrough from yesterday
on video if you've not already, if you need some guidance there.
And then you're asked to implement sort,
because again this notion
of sorting elements is what ultimately empowered someone
like us on stage to find numbers more efficiently, more quickly.
We were able to find Mike Smith
in the phonebook some four weeks ago because the thing was sorted
but that begs the question, how expensive?
How time consuming?
Is it to sort?
And so we looked at Bubble Sort, and Selection Sort,
and unfortunately those weren't the fastest players out there,
they were in what we call big O of N squared
since they might take N times N steps
but they did get the job done.
Now, those of you interested in the Hacker Edition also needs
to implement sort but you need to do it in Big O of N,
linear time, but you're allowed a couple of assumptions
as the spec directs you toward.
So by popular demand on two accounts, CS50 WiFi now exists
so if you're here for your-- with your laptop,
its time to pull up Facebook if you like and use the CS50 SSID,
it is password protected at the moment but the password is--
>> The combination is--
[ Laughter ]
>> One.
>> Two.
>> Three.
>> Four.
>> Five.
>> Six, seven, eight, so the software required
that they assigned an 8 digit password
but 12345678 should work for you, if not just catch one of--
myself or one of the TFs on the way out and we'll figure
out how you get you started for next week.
Also, lunch, so this Friday we'll be joined
by an alumnus who's also now
with the Venture Capital Firm NEA,
so if you'd like to not only dine with and chat with me
and the TFs and CAs but also have some vision
of a business you would like to pitch to a--
a friendly VC, do feel free to RSVP
at the usual URL, cs50.net/rsvp.
So, these were the numbers that we played
with quite a bit last week and these were just random numbers
but there were 8 of them
and 8 is almost always convenient 'cause we can divide
by 2, divide by 2, but in reality and in P set 3,
you're not gonna have the luxury of assuming
that you're only gonna have 8 numbers, but this allows us
to at least discuss them and we looked at again,
a number of algorithms: Binary search, Linear search.
Binary being the faster of the two, it was that divide
and conquer strategy, linear search was just left to right,
or right to left, but they were both correct
but one performs, of course, better.
We looked at a couple of searches and in English terms,
how did Bubble Sort work anyone?
If you implement Bubble Sort, how does it work?
[ Inaudible Remark ]
>> Okay, good!
So it compares two values that are adjacent to one another
and in short, if they're out of order, swap them,
and then repeat, and then repeat, and then repeat,
and then repeat, and at what point could KC
or anyone sorting N elements stop doing those comparisons?
Does she-- did she just need to walk
across the stage once comparing these two, these two, these two,
and by the end done with Bubble Sort?
Well, no, 'cause remember in bubble sort in the worst case,
the person who's all the way at the end
if we had the number one completely in the wrong spot,
he or she might only bubble up one place despite KC's pass
through the entire list of people so KC potentially had
to go back and again, and again, and again potentially N times
and that's where we got the N squared from.
So what about Selection Sort?
This was the first version
and it was actually pretty intuitive, pretty consistent
with what a normal human being would do.
How do you define Selection Sort?
Just in English, how do-- someone else?
Yeah?
>> It's where you find the lowest number
and put it all the way to the left.
>> Okay, so you find the lowest number
and put it all the way to the left, perfect!
And then repeat, but you do it with the next smallest number,
and then the next smallest number,
the problem with this though as clean and as intuitive as it is,
it too involve just as much work because recall
if the list was completely backwards, number one is
over there, number 8 is over there, KC would have
to go all the way over here, find "Oh!
Here's number one, let me move him or her over here."
And just evict this person, and just swap them
over there 'cause they're in random at order
in the first place, it doesn't matter we just shove them
to the end anyway, but now she has to repeat and who knows
where number two is so you have to look again, and again,
and again, and finally we get N squared again 'cause she has
to make N traversals back and forth across the stage,
each time looking at potentially some N or N minus one
or fewer humans so to see this in action, we can actually look
at this visualization which is a little--
this shows us not just the ones we looked at but a few others
as well so this again, each of the bars represent a number,
smaller bar smaller number, big bar big number.
And in a moment I'm gonna click that green arrow at the--
the top, and you'll see there's a few more sorts in this world
than just Selection Sort, Bubble Sort, and Merge Sort,
which we looked very briefly at the end of-- last time.
There's Insertion Sort, there's Quick Sort, there's Shell Sort,
Heap Sort, couple of which we'll come back to eventually
but there's dozens of these things
and really it's the principles in just a few of them that--
that we'll focus on for now.
But the takeaway here is this.
I've clicked random order so that we just kind
of got some random numbers, small and big in there.
If I click Go, what's neat
about this visualization is it's gonna show us more than three,
it's gonna show us all 8 of these algorithms at once,
and recall Merge Sort one last time,
he's doing pretty well this time.
Apparently, Insertion Sort's pretty good, Heap Sort,
Quick Sort, Quick Three, Shell--
I mean, maybe we should've started with these, right,
'cause these are clearly much higher performance, apparently.
Here comes Insertion Sort, and there's N squared for you.
So as simple as Selection Sort was and as intuitive as it was,
and as correct as it was, it's clearly suboptimal,
at least on random inputs and we can do this again and again,
but unless you get lucky with--
whereby maybe they're all sorted initially, those two algorithms
in particular are gonna perform and feel slower,
and thus is N squared.
So hopefully, we can do better.
In fact, if-- you might not have seen this a few years back,
a certain someone was running for president
and he was actually asked this question of, what--
which of these various sorts would you use?
It's perhaps worth hammering home this point
that N squared is indeed a little slow with this interview
with former Google CEO Eric Schmidt.
[ Pause ]
>> Oops, start at the beginning.
[ Applause ]
>> Now-- now, Senator, you're here at Google and I
like to think of the presidency as a-- as a job interview.
[ Laughter ]
>> Now, it's hard to get a job as president.
>> Right.
>> And-- and you're going to [inaudible].
It's also hard to get a job at Google.
>> Right.
[ Laughter ]
>> We-- we have questions and we ask our candidates questions
and this one is from-- Larry Schwimmer.
>> Okay.
[ Laughter ]
>> What-- you guys think I'm kidding?
It's right here.
What is the most efficient way
to sort a million 32-bit integers?
[ Laughter ]
>> Well-- I-- I--
>> I-- I'm, maybe-- I'm sorry maybe we should
>> No, no, no, no--
>> That's not--
[ Simultaneous Talking ]
>> I-- I think-- I think the--
the Bubble Sort would be the wrong way to go.
[ Laughter ]
>> Come on, who told him this?
[ Applause ]
>> So there you have it.
So today, we'll look at one of these faster algorithms and sort
of the principles that you can leverage in order to do better
than Bubble Sort but first a few empowering techniques.
So thus far with problem sets and even lecture code
if you've been playing along at home,
you will run into bugs, right?
Your code might not compile.
You might get segmentation faults or core dumps.
You-- your program might never stop
and so it just produces output and output and output
or the cursor never comes back to you.
There's so many ways in which you can screw up a program
and it gets easier, trust us,
to actually find the problems there in,
so thus far if you've been debugging programs,
hopefully you've realized
that printf is absolutely your friend, plugging a few printfs
to see what the value of X is, what the value of Y is--
this point, and this point,
and this point can certainly help you along,
but unfortunately printf can only take you
so far plus it's tedious then you have to rip
out that code once you found your problem, and especially now
that we're in problem set 3 which is a game,
The Game of Fifteen, there's a little bit
of primitive animation there and you're gonna completely screw
up the game board if you're trying to print
out some error messages or the values of variables
on the screen at the same time.
And so we kind of need more sophisticated techniques now
to debug programs.
So enter into the picture a program called a debugger,
so one of the most popular debuggers out there for Linux,
and Mac OS and it's available on Windows
as well is a program called GDB, the new debugger.
And what this program allows you
to do is set what are called breakpoints
in your program whereby you say, don't run my program all the way
from top to bottom rather pause execution on line 13 of main.
Why 13? Well, you are suspicious that you have a bug somewhere
around line 13 but your program's flying by so fast
that you can't really wrap your mind around what the problem is
so you'd really like to slow things down and look
at step 13, then 14, then 15.
Well a breakpoint, as the name suggests, allows you to brake
at a certain point in your program and then at your pace,
your human pace, only advance line by line when you're ready.
Similarly, while you're inside this debugger you're gonna be
able to printout the values of variable, so you don't have
to use printf, you can just ask the debugger what bits are
inside of this variable X, what number is there,
or what string is here?
And so you can actually see the inside
of your program while still interacting with it.
So let me go ahead and open up the appliance here,
and I'm gonna go ahead and open up, let's say a program called--
let's go with-- about buggy3, so buggy3 was this program
and we'll actually finally start solving this program--
this problem this week and next.
This was that broken swap function whereby
in main we had an int X and Y, they each had some values.
We have some printfs, then we called this--
function Swap which then looked like this
and we claimed verbally a week or so ago that Swap was correct
at least in so far as it goes when it comes to swapping A
and B, but it did not swap X and Y. The moment swap returned,
yes, A and B we claimed were swapped but X
and Y were unchanged, they were still 1 and 2, respectively.
So just conceptually, what was the explanation behind the
bugginess of this program?
Yeah?
>> The variables would pass that value not--
>> Yeah, so the values of X and Y--
the X and Y were passed by "value" which meant a copy of X
and Y was passed into Swap, Swap just so happened to call them A
and B, but it could call them whatever it wants,
but they're indeed distinct 32 bits worth of integer
so at this point when Swap was called,
we claimed that there exist in this world X and Y,
and then also A and B, and if you think back
to how we drew the RAM inside of our computer, mains--
variables were down here, this slice of the stack frames
so to speak, and then on top of it somewhere else in RAM was A
and B, so just pictorially too,
they were distinct chunks of memory.
So, now we can finally see things like this
and this program isn't just--
fixing this program actually takes a bit of ingenuity.
And we'll actually get there later this week.
But for now, we can at least understand what's going on
and not just have to take my own word for,
and along the way we can actually learn some
of these commands.
So I'm gonna go ahead and do this.
I'm gonna open a larger terminal here,
just so we can see more at one time.
I'm gonna go ahead and run make buggy3, okay, it's up to date,
which means I already compiled it last week so that's good.
And I can go ahead and run it just to prove
that it's still broken.
So X is one, Y is two, there's still one
and two at the end of this.
So let's now, instead of running this as Buggy 3,
lets instead run GDB and then pass to GDB
as they're so-called Command Line Argument,
the name of the program I wanna debug.
So I'm gonna go ahead and hit Enter now.
And now I see a bunch of warranty information
and all this and then a new kind of prompt.
At the bottom left there is a prompt that says,
in parenthesis GDB, and that means I'm inside of the debugger
and nothing's gonna happen just yet.
I can hit Control L to clear the screen,
now I'm inside the debugger
but my program is not running yet but I can run it.
I can literally type Run Enter and voila!
I've run the program inside of the debugger.
Now, unfortunately this is not at all useful thus far.
All I've done is now run my program inside
of another program but I haven't specified
that I wanna poke around.
I haven't specified breakpoints.
I haven't specified I wanna see anything.
So let's do that.
This time, I'm gonna hit Control L just to keep the screen clean,
I'm gonna type break,
and I don't actually remember the line number 13 I made
up before, but I know the function name
so I'm gonna start simple, break at the function called main,
and what you see now on the screen is "Breakpoint 1
at 0x804842d file buggy3.c line 21."
So-- on the one hand, GDB figured out where main starts,
it's apparently line 21,
but what in the world is this 0x804842d do you think?
[ Inaudible Remark ]
>> Yeah, so it's a memory address
and we'll start seeing more things that look like this
but almost any time you see a number in the context
of programming that starts with OX, first of all,
that's indication of hexadecimal notation or basics team,
but we'll come back to that but for now it's just another way
like decimal and binary of expressing numbers.
And yes, that represents the address inside
of my computer's memory at which what lives?
Main itself, right?
We said last week that main itself
and really your program itself lives inside of RAM, in fact,
it's one of the things that's up on toward the top of your memory
and one of the things you run the risk of clobbering
if you call functions way too many times,
such that you overlap that memory
but for now GDB has figured out where it is,
it at a breakpoint number 1 and now if I go ahead and type Run
and hit Enter, now it runs but it seems to break quite quickly.
So it says "Breakpoint 1, main at buggy3.c line 21" well,
I forget what that is but GDB is reminding me.
If you'd like to see it in context, you can go back
to G Edit and you can scroll down and find line 21.
If you've never noticed in the bottom right corner of G Edit,
it always tells you what line you're on
and even what column you're
on so you can do a quick sanity check there,
so I'm gonna go back to my terminal now.
And GDB at this point is saying, "You're on line 21,
I'm about to execute line 21, what do you want to do?"
Well, let's go ahead and do this.
Let's move on to the next line.
So next means execute what you see
and move on to the next line.
Alright, now, I'm gonna go ahead and say, "Yep, lets go ahead
and execute this next."
Okay, now I'm gonna get to line 25 and it's gonna print
out it seems the value of Y. Well what is this?
Why did I just do that?
Interesting.
Let me go ahead and do this.
Print Y Enter, so is that consistent with what we expected
if I go back to the code here?
So yeah, Y was initialized to two here,
I'm now down at this line here.
The reason I'm kind of mumbling
to myself is I'm actually not sure why GDB just skipped X
there, so we'll come back to that later, but for now,
we're at this line here where Y is percent D. If I print out Y
within GDB, it is in fact 2, so let's hit Next again.
And now, indeed, it prints out as much, and now let's go ahead
and say, Next, and oh, this is interesting.
This is the line of code that if executed is supposed to swap X
and Y, so quick sanity check, let me go ahead
and first print X, it's still one.
Print Y, it's still 2.
As an aside, the dollar sign notation here,
this is just the GDB thing, it's giving you temporary nicknames
for those values in case you wanna refer back
to those values, but for now you can essentially ignore the
dollar sign 2 and dollar sign 3,
all we're seeing now is the value of X and the value
of Y. Alright, so let's go ahead and hit Next
and let Swap do its thing so I hit Enter,
now it's about to print
out Swapped exclamation point but lets do a check.
Print X, still 1; Print Y still 2, so clearly it's broken here,
so let's start over and actually see where the problem is,
so let me go ahead and type Run again, it's gonna say,
"Wait a minute, you're still debugging,
do you wanna start it from the beginning?"
I'm gonna say yes, and now we're back at the beginning,
so now let me go and do a sanity check, print X--
seems like I've got multiple bugs, what's going on here?
[ Inaudible Remark ]
>> Sorry?
>> You haven't hit Next yet.
>> Yeah, so I haven't hit Next yet which means what?
Line 21 has not yet executed
which means what should be the value of X?
[ Inaudible Remark ]
>> Right, it's some garbage value, right?
We talked last week about how
because these stack frames are always piling up and going down,
and up and down, you're reusing the same bits
that some other function maybe not even written
by you has actually previously used.
So what we're seeing
at X's location is this number 3,219,444,
those are just random bits left
over from something else's execution
and so we're just seeing the remnants of that,
but if I do click Next, and then print out X-- okay, whew!
It's back to one.
If I print out Y, same thing, another complete garbage value
but if I hit Next now and then go ahead
and print Y, now it's back to two.
>> So let's hit Next, let's hit Next,
and notice it's just doing the printf's
and this is printing correctly,
I must have hit something wrong earlier
so let's hit Next now, and now Swap.
So if you wanna step into a function and not step over it,
what you do instead is literally type Step, so if I type Step,
now notice what GDB is telling me, I'm now inside
of a function called Swap, the arguments that were just passed
to this function are one and two for the variables A
and B respectively, I'm at line 41 in the same file, buggy3.c
and I'm about to execute line 41 so let's go ahead and do this.
So let's do Next, let's do Next, let's do Next,
and now line 44 is the curly brace.
So this is where our story verbally used to stop.
Let's do a quick sanity check, Print A, Print B,
and what should Temp be if I print Temp?
And fifty-fifty percent chance here, and it's indeed one,
'cause we initialized the two to the value of A and then used
that to put that same value in B. So this looks right.
When I printed A, I got 2.
When I printed B, I got one, so let's go ahead
and click Next and now I'm back.
GDB is telling me back in main where I left off, line 28,
so if I now print out X, print out Y, they're still broken
as we expected and if I try printing A,
no symbol A in current context Print B,
same thing because they're no longer in scope.
So to be honest, using GDB even for these simple operations
of using Print, Next, Step, and Break are hugely more powerful
than just using printf alone, so we'll spend time on these
in section and certainly more over time as well here.
But if you go in the meantime to cs50.net/resources,
you'll see that under the GDB tag, there's one a--
some documentation here,
but there's also a little quick reference cheat sheet
that has way more commands than you'll probably care
about initially, but it's a one-page PDF you can print out
and it's a cheat sheet of sorts and you'll see
that it gives you a quick sense
of the various commands you can type, and also GDB is nice
in that you can be fairly succinct.
You can just say-- P for Y, PX.
You can almost always type just the first one
or two characters of the command.
So you don't have to redundantly type out print all the time.
And you can also scroll up, down, left, right.
And finally when you're done just type Q or quit.
And that will warn you that you're about to quit.
And now you're back at the appliances prompt,
so a hugely useful tool.
And this is one of those things honestly
where I did the same thing.
We sort of introduced this.
We claim that's incredibly useful.
But there's invariably a learning curve,
whether it's ten minutes, an hour or so to acclimate to it.
And so this is absolutely one of these tools
that like almost every student puts off, myself included back
in the day, until later and later and later in the term.
But honestly, spending the ten minutes, the hour for P Set 3
and 4 to play with GDB, I promise will save you hours
of time in the future.
It is so much more useful than just using printf
in your own brain sometimes when looking through code.
It allows you to step through much more reasonably.
Alright, any questions on debugging or GDB?
Yeah?
[ Inaudible Remark ]
>> Good question, if you're dealing with arrays by default,
GDB will usually know how to print something that's
like an array or a string which is an array of characters.
It does sometimes depend on the context.
But for now if you declare an array inside of a function
and then type "print space foo" where "foo" is the name
of that array, you should see all
of the members of that array, yes.
The only problem arises sometimes if you start passing
that array around which we haven't really done,
except in problem set three's distribution code
that sometimes GDB essentially loses track of the length
and so it has trouble printing it for you.
Other questions on GDB?
Alright so comparing values, and now sorting values,
how can we do this better?
So this little picture here suggests that one
of the fundamental operations,
anytime we're actually doing sorting is that we need
to compare stuff, alright?
We need to compare one value against the other.
In Bubble Sort that's literally what we were doing.
And really in Selection Sort,
that's what we were doing as well.
Even though we describe it as go find the smallest value.
Well, how do you find the smallest value?
Well you look at the first person, there number 8,
you just assume they're the smallest by default
because they are thus far.
Then you look for someone smaller
and smaller every time comparing the person you found
against the number you're considering replacing them with.
So comparisons are really fundamental to this process
of sorting and then to some extent, so is swapping,
of course swapping is very easy if you just use X and Y
in a temporary variable in your function but of--
we've seen that it gets problematic
if you have a Swap function but we'll fix that problem
on Wednesday but realize that for Problem Set 3,
you don't need to implement your own Swap function, right,
with just three lines of code, case in point,
you can implement Swap inside of a for loop or inside of main,
you don't necessarily need this auxiliary function just yet.
So, can we do better and how can we go about doing better?
Well we need a new technique.
So if we want to solve these problems more effectively,
it'd be nice if we could express ourselves a little more
elegantly, and it's not gonna necessarily empower us
to solve problems we couldn't with something called Iteration,
otherwise known as Looping, but besides for loops
and while loops and do-while loops, there's other ways
to do something again and again and again,
and thus far we did it once intentionally, though foolishly,
recall that when I implemented a function foo,
and then I had foo call foo,
I think that was the function's name, what happened
when I had a function call itself?
[ Inaudible Remark ]
>> It kept going, it kept going,
it kept going, until what happened?
>> Segmentation--
>> Segmentation fault, right, core dumped.
So why was that?
Well, we claimed last time that when you think of your memory
as that big rectangle and you keep calling a function,
each invocation, not the function,
each call of that function gets its own slice of RAM another,
another, another, another,
and even though you might have gigabytes worth of RAM,
eventually you do something infinitely long and you're going
to take up more than you're allowed
and so the operating system's gonna kill you,
you're gonna dump core, and inside of that file
or the contents of memory.
As an aside, before I forget, if you are very good
at creating core dumps in your programs,
realize that GDB here can also save the day.
If you do find that you do have one of these files called Core,
what you can do with GDB is run GDB
on whatever your program name was but then specify
as a third word at the command line the name
of the file, Core, C-O-R-E.
And then hit Enter, and if I actually had had a core dumped
from this invocation of this program,
the GDB is being handed not only the program called Program,
but also the core dump and inside
of the core dump, is what did we say?
[ Inaudible Remark ]
>> It's the contents essentially of RAM
at the point your program crashed
which means this is your opportunity for an autopsy
of sorts, this is the dead program sitting there
in the file called Core and with GDB, you can now step through
and type Print, and other commands to actually look inside
of what happened there.
So there, too, is an opportunity.
Alright, but we'll be having plenty
of segmentation faults Wednesday onward
when we finally introduce something called Pointers
but for now, really an elegant technique,
and this is something we won't use all that often this semester
but in future courses if you decide
to proceed particularly courses like 51,
or in a Data structures, or algorithms class or really
in the real world when you start trying
to solve really complex problems,
this notion of recursion is really powerful.
And recursion boils down to calling yourself,
like you are a function, you are said
to be recursive if you call yourself.
Now, we saw last week that this is apparently a bad thing.
If you call yourself, you get into this infinite loop
and use segmentation fault.
But that's true if you'll just call yourself--
if you just call yourself again and again
without even considering stopping.
But suppose we introduce a branch or a condition that says,
sometimes you should stop
so that we can short-circuit this otherwise infinite looping.
So here's some generic pseudo-code
for that algorithm Merge Sort, so just as a teaser here,
here's how Merge Sort works.
Merge Sort was that super fast algorithm we saw at the end
of last week and we saw among the 8 candidates today it works
as follows.
If you were handed N elements and N is less than two,
you just return, right?
If you get fewer than two elements, how big is the list?
It's zero or one, in either case the list is sorted
so you're done.
Else, if you actually get an interesting size list
of size two or three or a thousand or anything bigger,
you're gonna instead do this.
Sort the left half of elements, sort the right half of elements,
then merge the sorted halves.
That's it!
Right, you might have thought that Merge Sort, wow,
must be really interesting and complex, it's gonna take,
you know, really complex demonstration but no--
maybe, probably, actually you didn't think any of that.
So instead Merge Sort is defined literally this simply,
it literally calls itself.
Right, if you're an algorithm and you wanna kind
of be a smart-ass algorithm and you're told here,
sort these N elements, you could just push back and say,
"Okay fine, I'm gonna sort these N elements
by first sorting the left half, then sorting the right half,
and then I'll merge the two sorted halves."
But that then beget-- that then begs what question cyclically,
okay fine, how are you gonna sort the left half?
How are you gonna sort the right half?
Well, I can give you the same wisecrack answer and say,
well I'm gonna sort the left half of the left half
and the right half of the left half and then the other side
and I'm gonna merge the two, right?
>> Now these two feels like you're being difficult
and aren't really answering the question but you kind of are
because what if you get down to the point in this sort of back
and forth argument where all I do is hand you two numbers
like this.
Well, you're gonna say the same thing,
I'm gonna sort the left then I'm gonna sort the right then I'm
gonna emerge the two.
Alright, find I'm gonna push back one last time
and say "Fine, how are you gonna sort the left half?
Well, the left half looks like this.
How you're gonna sort this?"
It's already sorted.
Right, so there is the brilliant insight.
Once this argument kind of bottoms out and the list is
of sufficiently small size the problem is trivial to solve.
All you have to do is hand me back the list.
So in Merge Sort as its name kind
of suggests the real magic is not so much
in the sorting per se but in the last step the merging.
That must be where the sorting in real terms actually happens.
Now in as much as this algorithm Merge Sort effectively calls
itself by cyclically saying, how do you sort N elements?
Well, you sort these elements then you sort these elements.
The fact that you're answering question
with the same question means that it's recursive.
So let's see this notion of recursion,
but first in a simpler context.
Let me go over to this file here and the appliance
and open up let's say sigma1.
So for those following along at home
over the PDF this is sigma1.c. And I'm gonna scroll down here
and let's see what this sigma function does.
So this function gets its name incidentally
from just the Greek symbol for adding a bunch
of numbers together that looks a little something like that.
So this is just an addition function at the end of the day.
So how is this addition actually working?
Well, let's take a look.
So we have at the very top of the file a prototype
for a function called sigma whose argument is an int
and whose return type is an int.
Recall that I mentioned that for prototypes you don't strictly
need to mention the name of the variable just its type.
So that's an example of that shorthand notation
up at the top.
Now here is main, so what's main doing?
It's gonna ask the user for a positive int.
So here's an example of using do-while.
Again, we keep using do-while in programs
and P sets anytime you wanna get something
from the user then yell at them
if they don't oblige the first time.
So it's a good construct for that.
So all of these first five
or six lines are doing are getting an integer
that should be positive from the user.
Then, apparently I'm declaring an int called answer.
I'm storing an answer,
the result of calling a function whose name is sigma
and the input to sigma is N, whatever the user typed N. So,
I claim that sigma's purpose in life is to compute the sum
from 1 up to N. So if the user types
in two sigma should give me 1 plus 2 it should give me 3.
And if the user types in 3 the program should give me 1 plus 2
plus 3, 6.
I should get back.
You should get the summation of those numbers.
And then, all this program is gonna do is report the answer.
So let's go ahead and run this to see.
Let me go on to the source directory,
I'm gonna go ahead and make sigma 1.
Okay, compile is okay.
Let me run sigma 1 on 2.
Oops, no, doesn't take a command line argument.
Let me run sigma 1, then give its number 2
and it does give me 3.
If I give it 3, it gives me 6, if I give it 10,000,
it gives me a really big number.
So it seems to be working but, you know,
I could be the difficult one or the TF, do something like this.
That was probably a bad idea.
[ Laughter ]
>> So what might be happening here?
That's a pretty big number.
It's bigger than 4 billion.
You know it's pro-- feels
like it's looping infinitely even though that's a big number.
So what-- remember what can happen
if you overflow an integer it could be mistaken as negative,
so it's possible I'm actually looping ad nauseam now
because I've never gonna hit my condition.
So in any case that's something where we'd have to assume a way,
we would tell you in a P set,
assume the user is not gonna type something more
than two or four billion.
But at least it seems to be working for small value.
So let's go back and see how.
So how is sigma working?
Well, it's actually pretty simple.
And this is kind of week 1, week 2 stuff now.
So sigma takes an argument we called it M.
But it could be anything so long it's an int.
First we do have a bit of-- oh, so interesting I actually made
that up for just a moment ago 'cause I'm actually checking
for negative value so there must be something else.
And we could use GDB to figure
out what was really going on there.
So it's saying if M is less than one return zero immediately
so that we don't run the rest of an infinite loop.
Now in here, return the some of 1 through M how does this work?
I've got a variable initialize to zero.
I've got a for loop that's gonna go from literally 1
up to an equal to M. So that's a literal translation of the goal
and then sum plus equals I and then return the sum.
So it feels like a very reasonable simple implementation
of summation from I equals 1 up to M
and then returning the value.
And we did get back that value.
But there's kind of an opportunity here, right?
If I wanted to solve this problem in sort
of fundamentally another way, what does it mean
to compute the sum of 1 through N?
Well, it's-- if I wanna be the wise ass like here.
It's really, alright it's N plus the sum of 1 to N minus 1.
Alright, so that bags the question,
what is the sum of 1 to N minus 1?
Well, it's N minus 1 plus the sum of 1 to N minus 2.
And okay fine, what's the sum of 1 to N minus 2?
Well, its N minus 2 plus the sum of 1 to N minus 3, right?
So you keep going and going and going
and this could become problematic
if you do go negative.
But it's if at some point you do have a mental check
that says what?
What's the sum of 1, 2-- 1 to 1?
Well it's just 1.
So you better stop asking me this stupid question.
Right, at some point there should be a very simple case,
let's call it a base case where it just wouldn't make sense
to recursively or to cyclically ask the same question again.
So let's translate that idea now to code.
Let me go ahead and close sigma1 and open up sigma2 instead
and scroll down here and notice this part
of the program is now identical.
I still have a printf and a do-while loop.
I still have a sigma call storing the result and answer
and I still print out what the answer is.
The only that's different now is the implementation of sigma.
So let's scroll down here.
And look how relatively simple this now is.
No extra variables, no for loop, no plus plus,
no syntactic distraction.
There's like real elegance here.
In fact, if I get rid of these comments,
just look how simple it is to express this idea.
If M is less than or equal to zero, you better stop, right,
'cause bad things will happen if we go negative,
so let's just return zero.
Now, this is not necessarily the right answer
because this is not the sum if you actually try
to sum up negative numbers.
But we have to make a design decision
so we're not gonna support negative numbers.
So if M is less than or equal to zero, return zero otherwise,
what's the answer to the question?
What's the sum from one to M?
Well, it is M plus the sum of everything below it.
So, now, think about what's happening here.
Main gets called then--
and let's suppose the user types in the number three.
We'll keep it small for simplicity.
So the user types in three and Main gets called.
Main calls sigma with an argument of three.
What does sigma do?
Well, sigma says, all right, is three less
than or equal to zero?
No. So we do the second case, the else.
So what's the answer to the question?
What is the sum of one through three?
Well, it's three plus the sum of?
The sum of one to two which is otherwise expressed
as three plus sigma of two, all right, so what's sigma of two?
Well, sigma of two is two plus sigma of one.
What's sigma of one?
Well, it's one plus sigma of zero?
What's sigma of zero?
That's where we hit the base case, right?
So this is the thing I did not have a week or two ago
when I completely broke the program
by just having foo call itself again and again.
I never once said, if something is true, stop doing this.
But, indeed, with a recursive function like this,
if you do have a decision point that says stop the recursion
if something is true, you avoid that process
of overflowing the stack so to speak.
So let's see if this thing now works.
Let me go to sigma2.
Make sigma2.
Seems to compile okay, let me do sigma2, Enter.
And now, let me go ahead
and do positive integer, let's give it two.
So that works.
Let's give it three.
That works.
Let's give ten, seems to be working.
Let's give it a bigger number, seems to be working.
Let's give it an even bigger number.
Okay, interesting.
So just because we have a base case doesn't mean the solution
is perfect, right?
Even apparently calling this is, what,
one million times calling the same function a million times is
apparently bad.
But that's okay 'cause this technique
of recursion is still something we can leverage to solve, say,
the problem of sorting, because especially with sorting,
even if there are a million elements,
the goal of doing divide and concur recall is
to whittle these problems down to something much smaller,
much fewer steps than anything linear with N. So let's go ahead
and take a quick break but when we come back we'll now play this
idea to the solving of sorting.
[ Noise ]
>> All right, so before class I borrowed a few milk cartons
from Annenberg across the way to see
if we can take a human approach
to sorting these elements while still executing these relatively
straightforward instructions and let's see
if we can understand why and how Merge Sort is actually speeding
ahead so much more effectively than Bubble or Selection Sort.
>> For this, we need just one volunteer, someone perhaps
who hasn't been up here before to kind of run the show
with these eight milk cartons.
Come on down.
All right, so, let's see how well this works.
The algorithm itself is correct.
So let's see if we can now do it some justice.
What's your name?
>> Joseph.
>> Joseph?
Okay, good to meet you.
Come on up.
David. All right, so here are the same exact numbers
in the same exact order as last week.
And for logistical purposes, you wanna hop back
down on the ground floor there?
And the goal is gonna be to sort these things,
but thankfully this time we have some written instructions.
So the input here now is of size eight, so first thing,
I ask the question, is eight less than two?
>> No, it's not.
>> Okay, so no it's not, obviously so we proceed
with the else, so else I say sort left half of element.
So left half looks like these four here.
So now if you interpret the same algorithm, how are you going
to sort the left half of these elements?
>> I'm gonna cut them in half and do it again?
>> Okay, so he's gonna cut them in help and do it again.
And just hold it a little closer there.
So, okay, so cut it in half.
Why cut it half?
Well, Joseph needs an algorithm with which
to sort the left half.
The only algorithms we have are Bubble Sort and Selection Sort.
Today, those are disqualified.
It's way too slow.
So we only have Merge Sort, so let's do the same thing.
So here is now list of size four, so is four less than two?
>> No.
>> No. No.
So now we sort the left half of elements.
So you hand me this.
What do you do?
>> N is not less than two?
>> Not less than two 'cause it is two.
>> We cut in half again.
>> So we cut in half again.
So now here is a list of size one.
Is one less than two?
>> Yeah.
>> Okay, obviously, it is.
And so, what do you do?
>> Return.
>> Okay, so this is sorted, right.
This is progress now.
The left half of the left half of the left half is now sorted,
even though Joseph literally didn't need to lift a finger.
So what step comes next?
Where are we in the story?
>> We merge.
>> Careful.
>> We're at the else.
We return and then we call again.
>> Good. So we sorted the left half,
but what comes after sort left half?
>> We sort the right half.
>> So now we sort the right half.
Here is the right half on input.
N equals one.
Is one less than two?
>> Yeah.
>> It is. So he returns.
This is great.
Now, we have two bites of the problem solved,
so now what's the next step?
>> We merge them.
>> Okay, so we merge them.
So now you can finally do something.
Okay, so good.
This is actually pretty good progress.
We've sorted this part of the list.
Now, they're not necessarily in perfect order,
'cause two probably this shouldn't be out all the way
at the end 'cause there is a one.
Four shouldn't be there.
But at least this is progress.
So, now, mentally, we kind of have to start rewinding.
How did we get to the point of merging these two halves?
Well, we started here because this is the right half
of the input of size four, right, so you kind of have
to mentally recourse in backwards to where we started.
So here is input of four.
You just sorted the left half.
What comes next?
>> Right.
>> All right, so let's sort the right half.
How do we sort the right half?
>> Cut it in half again.
>> Okay. Here's the left half.
>> Return six.
>> Here's the right half.
>> Return eight.
>> Here's both of them together?
[ Inaudible Remark ]
>> Okay. Merge.
They're already merged.
All right, so that's good.
It's really minimal work so far.
So where are we in the story?
>> Now, we have to merge the two halves together again.
>> Perfect 'cause now, if you again rewind mentally,
we've sorted the left half, we just sorted the right half.
So what comes next?
Merge the sorted halves.
>> Now, it's a little more interesting, so go ahead
and implement this idea of merging.
>> Well.
>> Good, very well done.
So 2, 4, 6, 8, so we're done.
Hopefully, the right side is gonna be more interesting.
So where are we now in the story?
We've hit the bottom of that else condition.
This was the left half of the input of size?
>> Eight.
>> All right, so why don't we put you on autopilot now,
and do-- tell us, though, verbally what you're doing.
>> Okay, so now we're on the right half of the input
of size eight, so we cut that in half and look at the left half
and then we cut that in half and look at left half of that.
Return one, return three for the right half,
and those are already merged.
So then we come over here and we cut this half and half
and return seven, return five, and then merge these.
Beautiful!
[ Laughter ]
[ Noise ]
>> Very well done.
>> And now we have to merge the whole half with the whole half.
>> Good. Both halves are size four.
So now how do we do this?
And this part-- so, clearly, the real work is involved
in the merging, right?
Again, hence the name Merge Sort.
So be a little precise now verbally.
How are you gonna merge these two?
>> Okay, well--
>> And just to be clear, there is one half, there is the other.
>> Okay, so I say we look at the left hand of this half,
this half, and the left hand of that half and compare it over.
>> Okay, so comparison, another theme thus far.
>> Right. And so, if that entity is smaller than half entity,
we then merge those two first.
>> Okay, so good.
So it turns out here is one point worth making.
So we kind of need some extra space now, right,
because if we kind of take last week's approach
of just swapping these guys, then we're screwing
up all the work we just did.
It is a good thing that two is on the left over here.
It's a good thing that one is on the left of the right half.
So we can't just kinda arbitrarily swap two people
and say we'll fix that later, 'cause if we fix that later,
the supposedly fast Merge Sort algorithm is gonna start taking
even more time.
So it turns out the one that the hidden costs of Merge Sort
and one of the key ingredients to making it so fast
in those visualizations is
that Joseph actually needs extra space.
So it was actually deliberate that I left a foot or so
of space here in front of these buckets
because Merge Sort gains its efficiency.
It increases-- it decreases its time
by increasing its space requirement,
its memory requirement.
So put more-- technically, for Merge Sort, you need two arrays.
One empty, one is the original array, and use the empty one
to put the elements into by the end.
So now you have as much memory as you want; eight new spots.
So where are you gonna put one?
Okay, so one goes there.
And, actually, there, let's put them in different places
so separate arrays, but we can still let it peak through.
Okay, so now what happens next?
One was less than two,
so one goes into the left most location of the new array.
What do you wanna do next?
>> So then you-- but you still compare the left,
this array with the next element in the--
>> Perfect!
So you repeat.
So, you look at the left end of the left half,
the left end of the right half.
Compare those two values, turns out two is
in fact smaller, so where does 2 go?
>> Right there.
>> Right there?
And so let's put it into the new memory space.
All right, so now what are you gonna compare?
>> The left end of this and the left end of that.
>> So four versus three?
>> And three is smaller.
>> Okay. So even though this kind of feels
like there is a lot of work going on here,
notice one key takeaway.
Every time Joseph puts a number into the new array,
he never has to go back, right?
There is no looping back and forth
like KC had to do last week.
Moreover, he's only looking at each of these--
he's only moving to the left of these elements once.
As soon as he considers an element
and decides it's smaller, that's it.
It's out of rotation.
So how many elements in total do we have to merge?
>> Eight.
>> Eight, right?
Or really seven because the last one we get for free,
so N or N minus 1, so that two is key here.
The number of elements we need
to merge is maximally N 'cause we have N empty spots.
We have N buckets.
We need to put them into the empty spots, all right.
So, where are we in the story comparing what?
>> So now we're comparing four and five.
>> Four and five.
>> Four goes--
>> Okay. Now, we're comparing?
>> Six and five.
>> Okay.
>> It goes here.
>> Now, we're comparing?
>> Six and seven and 6 goes here and then eight and seven.
Put seven here and then the eight goes right there.
>> Done! Okay, a big round of applause for Joseph.
Well done!
[ Applause ]
>> So, as is always the case with these human demos,
it feels like that took a while, right?
It really did take some time but think about how much time
if we try to express it in those N terms that we did last week.
So, every time-- the way we started this algorithm is we
divided the list in half.
And then we divided the list in half.
Well, this is kind of an easy answer now to this part
of the question, how many times can you divide N things
in half formulaically?
>> Log N.
>> So that's log N, right?
It's technically log base 2N and even if you're a little hazy
on what the logarithms are, for now just know
that anytime we ask the question,
how many times can you divide something in half?
Well, it's gonna be log base 2 of the something
or really we again, just like last week, we said "Divided
by two plus two, who cares?
Let's ignore constant factors."
Same deal with the logarithms.
So, we'll almost always just say log N. So log N is what gives us
that nice shaped curve that was not straight but rather curved
and that's what gave us that added performance boost.
So, there is definitely something log N involved here.
So, a quick sanity check.
Can you sort N element in log N time?
All right, is that the answer?
It's actually not but why can--
does it take more than the log N steps to sort N elements?
[ Inaudible Remark ]
>> Okay, so that's actually the full answer but just logically.
If I've got N elements and I claim I can sort these
in log N steps, you can immediately say,
"Hmm, not possible."
Even if you have no idea how I'm claiming to do it because what?
In order to sort N elements,
you kind of just logically minimally need
to do what with each of them?
At least like look at it, right?
You at least have to check, is it in the right place?
So just logically, if you need to solve the problem
that involves sorting N elements, minimally,
the lower bound is going to be N steps because if it's any less
than that, you're just guessing.
You're just claiming sorted when you haven't even looked
at all of those elements.
So again, here too is kind of a mental rule of thumb.
You can decide, "Hmm, that's not realistic
because you can't possibly sort all N elements in less
than N steps because again, you need to look at each of them.
Now, a quick sanity check.
When we had Sean on video up at the board here,
he was able to find an element
in log N steps but that was okay.
>> When Sean was looking for the number seven, he didn't have
to look at all of the other elements, right?
When they were sorted, rather Sean was doing it randomly
but when we then did it ourselves up on stage,
we sorted the elements in advance and so you don't need
to look at all of the elements if you already know.
"Those are less-- those are smaller
than what I'm looking for.
Those are bigger than what I'm looking for."
You can throw elements away but not so with sorting.
So, with Merge Sort, we're gonna have the list log N times
and that's as many times as we can divide something in half.
But every time we have the list,
there is this key step of merging.
Well, suppose I have the list down to size 2,
how many steps are involved in merging a list of size 2?
It's like two or you know, it's like two or three, right?
You have to compare them.
Then you need to move one, then move the other.
So it feels like it's two or three, give or take.
But it's some linear factor of the number of bucket, same here.
How about when we had 2 halves like this?
These were sorted and these were sorted,
then we had to merge them.
How many steps did it take to merge these things?
Well, you can actually simplify this logically.
If these plastic bins were at this location a moment ago,
and this half was sorted, this half was sorted, now we needed
to sort-- now we needed to merge the two halves.
Well, how many steps does this take?
Well, you can just kind of infer well, this guy ultimately has
to move into his location.
This guy has to move into his location.
This guy has to be merged into his location and this guy
into his, so it's again four, maybe give or take
if we have to-- if it's actually--
maybe it's eight, right?
Maybe you need to compare them and then move it around,
but it's still linear because there are only four things you
need to merge in total.
So it feels like every time we have the list,
we have to do something as many as N times
for the merging process.
And so in the end, merge sorts
and we'll see this in just a moment.
Merge sort is what we'll say as in big O of N times log N. So,
this refers to the merging.
At the end of the day, you've got to merge N elements
but this refers to the number
of times you're gonna have the list again and again and again
so you get N log N. Now again, just quick sanity check
without dwelling on what a logarithm even is necessarily,
which of these are smaller, N or log N?
>> Log N.
>> So log N is smaller.
So then, why is Merge Sort so much fast--
why is merge sort so much faster
than Bubble Sort or Selection Sort?
Well, those things are N squared or N times N. This is the same.
This is bigger.
It's because this second factor is bigger than this
that you actually get that N squared feel,
that slowness to the algorithm.
Well, let's just see this another way rather
than just based on buckets.
We can express this actually completely formulaically,
very simple formula.
So recall our implementation of this was just this algorithm.
We have a base case at the top,
then we've got some recursion going on, sort the left,
sort the right and then merge.
So let's now slap some running times on this.
And here is another takeaway.
You don't even need to write or see code in order
to analyze the running time of an algorithm.
We can just kind of infer it from the pseudo code.
So, I claim that the running time of this algorithm--
call it T for time given an input of size N is gonna be zero
if N is less than two.
In other words, it takes me no time at all to sort a list
of size N if N is actually less than two,
if it's zero or one, right?
It's just done.
So, we'll claim the cost of that is zero.
Well, that's obviously not the running time or merge sort.
It's not zero.
There's got to be some approximation
of N log N, so let's get there.
So, what's the recursive case?
That was the base case.
So, in the recursive case,
what's the time involved to sort N elements?
Well, here is where we can kind of cheat with ourselves
and to say, "Hmm, it's this plus this."
The running time to sort N elements equals the running time
to sort N over 2 elements plus the running time to sort N
over 2 elements, left half plus right half plus the N is
the merging.
So again, a quick sanity check here.
If the very first step of the algorithm is sort the left half,
sort the right half, here is the left half,
here is the right half merging.
How do you merge?
Well, think about what Joseph was doing.
If I kind of do it with my fingers here, he was pointing
to the left end of the left half and the right end
of the right half, sorry, and the left end of right half.
And what was he doing?
He was comparing them, figuring out which is smaller.
Then he decided one is smaller, so he'll pick
that one out of the lineup.
Then what did he do with this finger?
He advanced it to the next left most elements of the left half.
What did he do next?
Well, in this here, here, then he would go here, here, here.
So think about how many times did my fingers move
from left to right.
Well, once per bucket, right?
I only moved to the left.
I never did this.
KC did a lot of this last week, going back
and forth, back and forth.
Joseph never did that.
So, where do we get this N factor?
You sort the left half, you sort the right half,
then you just essentially conceptually have to point
at each bucket once in order to move it
into place as Joseph did.
So, unfortunately this isn't the answer.
I don't even see a log N in here because now we have
to recursively answer our same question.
What's the running time involved in sorting N over 2 elements?
Well, what's it gonna be mentally?
T of N over 4 plus T of N over 4 plus N over 2,
but this is just gonna get very messy very quickly.
So, let's try to simplify this with just an example.
So that is in fact an algorithm.
It's a recursive formula rather.
Let's try to do this with actual numbers.
Suppose for the sake of discussion,
we've now got 16 buckets, 16 numbers just
so the math is a little more compelling than 8.
What's the running time to sort using this algorithm
16 elements?
Well, it's T of 8, plus T of 8, otherwise known
as 2 times T of 8 plus 16.
So to be clear, one of those T of 8s is the amount
of time involved to sorting 8 elements on the left,
the other T of 8 is 8 elements
on the right assuming a total of 16.
And what's the 16 for?
Merging those, right?
Taking 8 from both halves, merging them together
so that you get a collectively merged 16 elements.
So now we have to dive in and let's do this one
because it's relatively easy numerically.
What's T of 8?
Well, T of 8 is just 2 times T of 4 plus 8.
What's T of 4?
T of 4 is 2 times T of 2 plus 4.
What's T of 2?
T of 2 is 2 times T of 1 plus 2.
All right, I'm just halving, halving, halving.
So hopefully this is gonna bottom
out ad sure enough, what's T of 1?
If I hand you a list of size 1 and I say sort this just
as Joseph did, you hand it right back, you're done.
So now, what can we do?
Just algebraically, we can say all right,
well I've got this T of 1 here.
Well, I can plug this in here.
So this zero is gonna go here.
That's gonna give me two times zero which is plus two is two.
So now I know what T of 2 is.
So now I can plug that two in there.
So two times two is four, four plus four is eight.
So that means this thing is eight.
So let's change this.
So, two times eight, that's 16 plus eight, right, is--
come on, I'm the only doing it, 24.
And if we keep going with this, what should we get in the end?
Sixty four, all right, so 64, quick sanity check then, so,
I claim that this algorithm runs in N times log N. So I claim
that that's gonna be 16 times log base 2 of 16.
Well, for those who remember, what's this?
It's four, right?
So if log base 2 of 16 is four, 16 times four is 64.
So sure enough, this is frankly proof by example
which is an illegitimate way of proving any point
that you ever might need to make academically.
However, it at least confirms, albeit with one simple example
that we are getting numbers along the lines of N log N.
And even though again, this is just one simple example,
recall just what the implications are
when you actually run this.
If I go again to this tier, let's choose reversed.
So now this is the worst possible scenario for all
of these algorithms Merge Sort,
recall is on the bottom left here.
Let's see just how well it performs
in this potentially worst case scenario.
Last time, recall we started with random.
So those other performers, Heap, Quick, Shell,
those are still looking pretty good.
Merge Sort is pretty good.
So we chose a decent one, Insertion Sort
which we didn't talk about a little slower but my God,
Bubble Sort and Selection Sort are gonna be here all day
with these example.
So that is in fact N log N. So, it's one thing
to see these things graphically and to kind
of reason through them.
Something one person did on the internet
which is actually quite fascinating is actually assigned
audible frequencies to the lengths of these bars
so that you can actually hear these various
sorting algorithms.
This is about a minute of audible animation.
Let me go ahead and pull this to the forefront.
[ Pause ]
[ Background Noise ]
>> This is Insertion Sort.
[ Sound ]
[ Background Noise ]
>> This is Bubble Sort.
[ Sound ]
[ Background Noise ]
>> Again, sound aside, notice that Bubble Sort true
to its name, the big values are kind of bubbling
up to the top slowly but bubbling up to the top.
[ Sound ]
[ Background Noise ]
>> Selection Sort.
[ Sound ]
[ Background Noise ]
>> And again, remember Selection Sort keeps plucking the smallest
element so it makes sense that it's looking correct
on the left but yet the right.
[ Sound ]
[ Background Noise ]
>> Merge Sort where you can really see the halves
that Joseph was merging.
[ Sound ]
[ Laughter ]
[ Background Noise ]
>> This is something called Gnome Sort.
[ Sound ]
[ Applause ]
>> So, that's it.
This is N log N, this is CS50.
We will see you on Wednesday.
[ Noise ]
[ Silence ]