# 12. Searching and Sorting

47K+ views   |   507 likes   |   6 dislikes   |
48:31   |   Feb 15, 2017

### Thumbs    ### Transcription

• The following content is provided under a Creative
• Your support will help MIT OpenCourseWare
• To make a donation or view additional materials
• from hundreds of MIT courses, visit MIT OpenCourseWare
• at ocw.mit.edu.
• PROFESSOR: So, for the last two lectures
• we've been talking about analyzing algorithms,
• complexity, orders of growth.
• How do we estimate the cost of an algorithm
• as the size of the input grows?
• And as I've said several times, I'll
• say at least once more, how do we also
• turn it the other direction?
• How do we use thoughts about choices of pieces of algorithm
• in terms of implications on the cost
• it's going to take us to compute?
• We saw last time a set of examples-- constant algorithms,
• linear algorithms, logarithmic algorithms, linear algorithms,
• Today, what I'm going to do is fill
• in one more piece, a log linear algorithm-- something that's
• really a nice kind of algorithm to have-- and use it to talk
• about one last class of algorithms that
• are really valuable, and those are searching and sorting
• algorithms.
• So a search algorithm.
• Kind of an obvious statement.
• You use them all the time when you go to Google or Bing
• or whatever your favorite search mechanism on the web is.
• It's just a way to find an item or a group of items
• from a collection.
• If you think about it, that collection
• could be either implicit or explicit.
• So way back at the beginning of the term,
• we saw an example of a search algorithm
• when you were looking for square roots.
• And we saw simple things like exhaustive enumeration.
• We'd go through all the possibilities.
• We saw our first version of bisection search
• there, where you would do approximations.
• Newton-Raphson-- these are all examples of a search algorithm
• where the collection is implicit.
• So all the numbers between some point that some other point.
• More common is a search algorithm
• where the collection is explicit.
• I don't know.
• For example, I've got all the data records of students
• and I want to know how do I find a particular student,
• so I can record that A plus that everybody in this room
• is going to get next Tuesday on that exam?
• That's not a promise.
• Sorry.
• But we'll work on it.
• So could do it implicit, could do it explicit.
• Today I want to focus on doing search explicitly.
• And it could be on different kinds of collections,
• but I'm going to focus-- just as an example-- on search
• over lists.
• And to make it a little easier, let's just do search
• over lists of numbers.
• But it could obviously be other kinds of elements.
• Now you've already seen some of this, right?
• We did search where we said, we can do linear search.
• Brute force.
• Just walk down the list looking at everything
• till we either find the thing we're looking for
• or we get to the end of the list.
• Sometimes also called British Museum algorithm
• or exhaustive enumeration.
• I go through everything in the list.
• Nice news is, the list doesn't have to be sorted.
• It could be just in arbitrary order.
• What we saw is that the expected-- sorry, not expected.
• The worst case behavior is linear.
• In the worst case, the element's not in the list.
• I got to look at everything.
• So it's going to be linear in terms of complexity.
• And then we looked at bisection search,
• where we said the list needs to be sorted.
• But if it is, we can actually be much more efficient
• because we can take advantage of the sorting to cut down
• the size of the problem.
• And I'll remind you about both of those.
• There was our simple little linear search.
• Right?
• Set a flag that says, I haven't yet found it.
• And then just loop over the indices into the list.
• I could have also just looped directly over the list
• itself, checking to see if the ith member of the list
• is the thing I'm looking for.
• If it is, change the flag to true
• so that when I come out of all of this
• I'll return the flag-- either false because it
• was set that way initially or true because I found it.
• And of course what we knew is we have to look at everything
• to see if it's there or not.
• I could speed this up by just returning true at this point.
• While that would improve the average case,
• doesn't improve the worst case.
• And that's the thing we usually are concerned about,
• because in the worst case I've got to go through everything.
• And just to remind you, we said this
• is order length of the list.
• To go around this part-- the loop right
• here-- and inside the loop, it's constant work.
• I'm doing the same number of things each time.
• That's order n times order 1.
• And by our rules, that's just order n.
• So it's linear in the size of the problem.
• OK.
• We said we could do it on sorted lists.
• But just again, we'll walk down the list.
• Again, here I could loop over everything in the list,
• checking to see if it's the thing I want.
• Return true.
• And if I ever get to a point where the element of the list
• is bigger than the thing I'm looking for,
• I know it can't be in the rest of the list
• because all the things to the right are bigger yet.
• I could just Return false and drop out.
• In terms of average behavior, this
• is better because it's going to stop
• as soon as it gets to a point where it
• can rule everything else out.
• But in terms of complexity, it's still order n.
• Because I still on average have-- not average.
• In the worst case, I'm still going
• to be looking n times through the loop
• before I get to a point where I can decide to bail out of it.
• So order n.
• And then finally-- last piece of recap-- bisection search.
• Repeat again.
• The idea here is, take the midpoint of the list.
• Look at that element.
• If it's the thing I'm looking for, great.
• I just won the lottery.
• If it isn't, decide is the thing I'm
• looking for bigger or less than that middle point.
• If it's bigger than that, I only use the upper half of the list.
• If it's less than that, I only use the lower half of the list.
• And the characteristic here was, at each step,
• I'm reducing the size of the problem in half.
• I'm throwing away half of the remaining list at each step.
• And I'll just remind you of that code.
• I know it's a lot here, but just to remind you.
• It said, down here if I've got an empty list,
• it can't be there.
• I'm going to Return false.
• Otherwise call this little helper function
• with the list, the thing for which I'm searching,
• and the beginning and end point indices into the list.
• Initially the start and the very end.
• And this code up here basically says,
• if those two numbers are the same I'm down to a list of one.
• Just check to see if it's the thing I'm looking for.
• Otherwise, pick something halfway in between.
• And ignore this case for the moment.
• Basically then check to see, is the thing
• at that point bigger than e?
• In which case, I'm in general going
• to call this only with from the low point to the midpoint.
• Otherwise I'm going to call this with the midpoint to high.
• And that was just this idea of, keep cutting down
• in half the size of the list.
• Last piece of the recap-- the thing
• we wanted you to see here-- is there are the two recursive
• calls.
• I'm only going to do one because I'm making a decision.
• At each step, I'm cutting down the problem by half.
• And that says the number of steps, the number of times
• I'm going to iterate through here,
• And if that still doesn't make sense to you, it says,
• I need to know when 1 over 2 to the k-- where
• k is the number of steps-- is equal to 1.
• Because in each step, I'm reducing by half.
• And that's when k is log base 2 of n.
• So that's why it's log linear.
• And so this just reminds you.
• Again, that recap.
• Number of calls reduced-- or, sorry.
• The call gets reduced by a factor or two each time.
• I'm going to have a log n work going around it.
• And inside it's a constant amount of work
• because I'm just passing the pointers,
• I'm not actually copying the list.
• And that's a nice state to be.
• OK, so-- sounds good.
• Could just use linear search.
• It's going to be linear.
• When you use binary search or bisection search,
• we can do it in log time.
• That's great.
• We assumed the list was sorted, but all right.
• So that lens basically says, OK.
• So when does it make sense to sort the list
• and then do the search?
• Right?
• Because if I can sort the list cheaply,
• then the search is going to be logarithmic.
• That's really what I would like.
• This little expression basically says,
• let's let sort be the cost of sorting the list.
• I want to know when that cost plus something that's order
• log n-- which is what it's going to cost me to do this search.
• When is that less than something that's order n?
• Because then it's going to be better to do the sort first
• than do the search.
• And so I can just rearrange it.
• It needs to be, when does the cost of sorting-- when is it
• last than this expression?
• Which basically says, when is sorting
• going to be less expensive than the linear cost?
• Crud.
• Actually, good news for you, right?
• This is a really short lecture.
• Because it says it's never true.
• Ouch.
• Don't worry.
• We've got more to go on the lecture.
• The reason it can't be true-- if you think about it
• just informally-- is, if I've got a collection of n elements
• and I want to sort it, I've got to look
• at each one of those elements at least once.
• Right?
• I have to look at them to decide where they go.
• Oh, that's n elements.
• So sorting must be at least order n,
• because I got to look at everything.
• And in fact as it says there, I'm
• going to have to use at least linear time to do the sort.
• Sounds like we're stuck, but we're not.
• And the reason is, often when I want
• to search something I'm going to do multiple searches,
• but I may only want to sort the list once.
• In fact, I probably only want to sort the list once.
• So in that case, I'm spreading out the cost.
• I'm amortizing the expense of the sort.
• And now what I want to know is, if I'm going to do k searches,
• the cost of those k searches I know
• is going to be k log n-- because it's log to do the search.
• And I simply need to know, is the cost
• of sorting plus this-- can I have
• something where it's less than k searches just using
• linear search?
• And the answer is, yes.
• There are going to be, for large k's, ways
• in which we can do the sort where the sort time becomes
• irrelevant, that the cost is really
• dominated by this search.
• And so what I want to do now is look at-- all right.
• How could we do the sort reasonably efficiently?
• It's going to have to be at least linear.
• We're going to see it's going to be a little more than linear.
• But if I could do it reasonably, I'm going to be in good shape
• here.
• So what I want to do is show you a number of ways in which we
• can do sorting-- take a list of elements
• and sort them from, in this case, smaller to higher
• or increasing order.
• So here's my goal.
• I want to efficiently sort a list.
• I want to see if we can do this as efficiently as possible.
• I'm going to start, you might say,
• with a humorous version of sort.
• You're all convinced that my humor is non-existent.
• You're right.
• But it sets the stage for it.
• This is a sort.
• You can look it up.
• It's called monkey sort, BOGO sort, stupid sort, slow sort,
• permutation sort, shotgun sort.
• And here's how it works.
• Anna has nicely given me a set of numbers on cards here.
• Here's how you do BOGO sort.
• I got to do that better.
• I got to spread them out randomly, like this.
• Oh good.
• I'm going to have to-- sorry, Tom.
• I'm not walking.
• And now I pick them up, saying, is that less than this?
• Which is less than-- oh, crud.
• They're not sorted.
• All right.
• I pick them all up and I do it again.
• A little brain damage, right?
• Now it's intended to get your attention.
• I did.
• I heard a couple of chuckles.
• Those are A students, by the way.
• I heard a couple of chuckles here.
• We could actually do this exhaustively.
• Basically it's called permutation sort
• because you could search through all possible permutations
• to see if you find something that's sorted.
• That, by the way-- the complexity of that
• is something like n factorial, which for large n
• is n to the nth power.
• And if n's anything bigger than about 2, don't do it.
• Right?
• But it would be a way to think about doing this.
• All right.
• Now, having caught the humorous version of this, how could
• we do this a little bit better?
• Oh sorry.
• I should say, what's the complexity?
• There's a nice crisp definition of BOGO sort.
• Its best case is order n, because I just
• need to check it's sorted.
• Its average case is n factorial and its worst case,
• if I'm just doing it randomly, is God knows.
• Because I could be doing it here forever.
• So we're going to move on.
• Here's a second way to do it called bubble sort.
• I'm going to do this with a small version of this.
• I'm going to put out a set.
• I'll turn these up so you can see them in a second.
• The idea of bubble sort is, I'm going
• to start at-- I'm going to call this the front end of the list.
• And I'm going to walk down, comparing elements pairwise.
• And I'm always going to move the larger one over.
• So I start here and I say, 1 is less than 11.
• I'm OK.
• 11's bigger than five.
• I'm going to bubble that up.
• 11's bigger than 6.
• I'm going to bubble that up.
• 11's bigger than 2.
• I've basically bubbled 11 to the end.
• Now I go back here.
• I say, 1 is less than 5.
• That's good.
• 5 is less than 6.
• That's good.
• Ah, 6 is bigger than 2.
• Bubble that.
• 6 is less than 11.
• You get the idea-- comparison, comparison, and swap.
• Comparison, comparison.
• And now if I go back to this part and do it,
• you'll notice that's in the right order.
• That's in the right order.
• That's in the right order.
• That's in the right order.
• I'm done.
• Small round of applause, please.
• I was able to sort five elements.
• Thank you.
• The little video is showing the same thing.
• You can see the idea here.
• It's called bubble sort because you're
• literally bubbling things up to the end of the list.
• It's pretty simple to do.
• You're just swapping pairs.
• And as you saw, when I get to the end of the list
• I go back and do it until I have a pass where
• I go all the way through the list and I don't do any swaps.
• And in that case I know I'm done because everything's in order,
• and I can stop.
• One of the properties of it is that the largest unsorted
• element is always at the end after the pass.
• In other words, after the first one
• I know that the largest element's at the end.
• After the second one, the largest thing left
• is going to be in the next place.
• And that tells me, among other things,
• that this is going to take no more than n times
• through the list to succeed.
• It might actually take fewer than that.
• OK.
• Again let's look at some code for it.
• Let's look at its complexity and let's actually run this.
• So here is a little simple version of bubble sort.
• I'm going to set a flag up here.
• I'm going to call its swap initially to false.
• That's going to let me tell when I'm
• done, when I've gone through everything in the list
• without doing a swap.
• And then I'm going to loop.
• As long as swap is false-- so the first time through it's
• going to do that loop.
• I set swap initially to true, and notice what I then do.
• I let j range from 1 up to the length of the list,
• and I look at the jth element and the previous element.
• If the previous element is bigger, I'm going to flip them.
• Right there.
• And that's just doing that swap, what I just did down here.
• And if that's the case, I'm going to set the flag to false.
• Which says, I've done at least one bubble as part of this.
• Which means when I come out of here
• and go back around to the loop, it's going to do it again.
• And it will do it until all of this
• succeeds without this ever being true, in which case
• that's true, which makes that false.
• And it will drop out.
• OK?
• Let's look at an example of this running.
• It's just to give you a sense of that,
• assuming I can find the right place here.
• So there is, again, a version of bubble sort on the side.
• And I'm going to bring this down to the bottom I've
• got a little test list there.
• And I've put a print statement in it.
• So you can see each time through the loop,
• what's the form of the list as it starts.
• And assuming I've done this right-- here you go.
• There's the list the first time through.
• Notice after one pass, 25's at the end of the list--
• the biggest element.
• Exactly what I like.
• But you can also see a few other things have flipped.
• Right?
• Right in there, there have been some other swaps
• as it bubbled through.
• And in fact, you can see it's-- well, you can see that idea.
• You can see 25 moving through.
• Notice on the next step, a whole bunch of the list
• is actually in the right order.
• It's just because I got lucky.
• All I can guarantee is that the second largest
• element is the second from the end of the list.
• But you can see here.
• Even though the list is, I think,
• nine long, it only took us four passes through.
• So this is nice.
• It says, at most, n times through the list.
• And at the end, we actually get out
• something that's in the right form.
• OK.
• So let's go back to this and basically say,
• what's the complexity?
• Well that's length n, right?
• Has to be.
• I'm going through the entire list.
• And inside of there is just constant work.
• Four operations.
• I'm doing a test.
• Sorry, five.
• I'm doing a test.
• And then depending whether that test is true or not,
• I'm setting a flag and doing some movement of things around.
• But it's just constant.
• I don't care about the five.
• And there, how many times do I go around the loop?
• In the worst case, n.
• All I can guarantee is, after the first pass
• the biggest thing is here.
• After the second pass, the second biggest thing is there.
• After the third pass-- you get the idea.
• So I've got order and things inside the loop,
• and I'm doing that loop n times.
• And I hope that looks familiar.
• Right?
• This is nested loops.
• What's this?
• So it's order n squared, where n is the length of the list.
• Now as you also saw, on average, it could be less than that.
• But it's going to be order n squared.
• OK.
• That's one possibility.
• Here's a second nice, simple, sort algorithm.
• It's called selection sort.
• You can kind of think of this as going the other way.
• Not completely, but going the other way.
• And when I say going the other way,
• the idea here is that I'm going to find the smallest
• element in the list.
• And I'm going to stick it at the front of the list
• when I'm done, and simply swap that place with whatever
• was there.
• Flip them.
• I might do a few other flips along the way,
• depending how I implement this.
• Next, pass.
• I'm just going to look at everything
• but the first element, because I know that one's done.
• I'm going to do the same thing.
• Find the smallest element remaining in the list,
• put it in the second spot, and keep doing that.
• What I know is, if I implement this correctly,
• after i steps the first i elements of the list
• will be sorted.
• And everything in the rest of the list
• has to be bigger than the largest thing
• in the first part of the list.
• OK.
• So we could build that.
• Before we do it, I'm going to show you a little video
• starring Professor Guttag.
• This is his cameo performance here.
• But I want to just show you an example of this
• using not numbers, but people.
• [VIDEO PLAYBACK]
• - All right.
• So now we're going to do selection sort.
• The idea here is that each step we're
• going to select the shortest person
• and put them next in line of the sorted group.
• So we'll bring the leftmost person forward,
• and we will compare her to everybody else.
• So one at a time, step forward.
• You're still the winner.
• You go back.
• PROFESSOR: And watch the number of comparisons that go on,
• by the way.
• We're going to come back to that.
• - Next.
• Still the winner.
• Next.
• Ah.
• A new winner.
• All right.
• So you can take her place.
• PROFESSOR: So here, we're choosing to actually insert
• into the spot in the Line We could
• have put her back at the front, but either one will work.
• - Now we'll compare.
• Same old winner.
• Same winner.
• No change.
• It's getting kind of boring.
• Don't fall, that-- same winner.
• PROFESSOR: This is a tough one.
• - Oh.
• Close, but I think you're still shorter.
• All right.
• Next.
• No change, which means you are the first in line.
• Congratulations.
• PROFESSOR: So, smallest element now going to be the first slot.
• - Now you step forward, and we'll compare you.
• PROFESSOR: I would invite you to watch
• the left hand of the list.
• Notice how it is slowly building up at each stage
• to have that portion sorted.
• And we deliberately admit students
• to be of different heights, so John can do this demo.
• - You are the winner.
• Take your place in line.
• Next.
• It's you.
• And once again, we have a lovely group
• of students sorted in height order.
• [END PLAYBACK]
• [APPLAUSE]
• PROFESSOR: And check out-- I want
• you to remember number of comparisons-- 55.
• Not that the [INAUDIBLE], but I want you to see a comparison
• as we go on in a second.
• So again, selection sort.
• This is this idea of, find the smallest element.
• Put it at the front.
• I might do a little number of flips,
• as you can see, here along the way.
• But this is the same animation of that.
• So let's first of all convince ourselves
• it will do the right thing, and then look at some code,
• and then run the code.
• So to convince ourselves that this
• is going to do the right thing, we
• could talk about something that we often refer to as a loop
• invariant.
• We're going to write a loop, but we're
• going to walk through this.
• And the invariant here-- and we want
• to just demonstrate if it's true at the beginning
• and it's true at each step.
• Therefore, by induction as we did earlier,
• I can conclude it's true always.
• Is that if I'm given the prefix or the first part
• of a list from 0 up to i, and a suffix or a second part
• of the list from i plus 1 up to the end of the overall list--
• given that, then I want to assert that the invariant is
• that the prefix is sorted and no element of the prefix
• is larger than the smallest element of the suffix.
• Just what I said earlier.
• It says, at any stage here-- if this is the amount of sort
• I've done so far-- I can guarantee, I'm going to claim,
• this will be sorted.
• And everything here is bigger than that thing there.
• How do I prove it?
• Well the base case is really easy.
• In the base case, the prefix is empty.
• I don't have anything, so it's obviously sorted.
• And everything in the suffix is bigger
• than anything in the prefix.
• So I'm fine.
• And then I just want to say, as long as I write my code so
• that this step is true, then I'm going to move the smallest
• element from the suffix-- the second part of the list--
• to the end of the prefix.
• Since the prefix was sorted, this is now sorted.
• And everything in the suffix is still
• going to be bigger than everything in the prefix.
• And as a consequence, by induction,
• this is going to give me something that says it's always
• going to be correct.
• So here's code that would do that.
• Here.
• I'm just going to set a little thing called the start
• of suffix, or soft start.
• Initially it's going to point to the beginning of the list.
• And then I'm going to run a loop.
• And as long as I still have things
• to search in the list, that that pointer doesn't
• point to the end of the list, what am I going to do?
• I'm going to loop over everything
• from that point to the end of the list,
• comparing it to the thing at that point.
• If it's less than, I'm going to do a swap
• because I wanted to move it up.
• And you can see, by the time I get
• through this loop I will have found the smallest element
• in the remainder of the list.
• And I would have put it at that spot, whatever
• suffix start points to.
• And when I've done all of that, I just change this by one.
• Having found the smallest element,
• I've stuck it at spot zero.
• I'll do the same thing.
• Having found the next smallest element,
• I know it's at point one.
• And I'll just continue around.
• One of the things you can see here
• is, as opposed to bubble sort, this one
• is going to take n times around the loop
• because I'm only moving this pointer by one
• So it starts at 0, and then 1, and then 2, all the way up
• to n minus 1.
• You can also see in this particular implementation,
• while I'm certainly ensuring that the smallest element goes
• into that spot, I may do a few other flips along the way.
• I'm going to find something I think is the smallest element,
• put it there and put that element here.
• And then when I find another smaller element,
• I may do that flip.
• I could have implemented this where I literally
• search for the smallest element and only move that.
• Doesn't make any difference in terms of the complexity.
• All right.
• What's the complexity here?
• I will loop n times, because I start at 0 and then 1.
• You get the idea.
• Inside of the loop I'm going to walk down
• the remainder of the list, which is initially n.
• And then n minus 1, and then n minus 2 times.
• But we've seen that before as well.
• While they get shorter, that complexity is still quadratic.
• Order n times going through this process.
• Within the process, order n things that I have to compare.
• And yes, n gets smaller.
• But we know that that n term, if you like to dominate.
• So again, this is quadratic.
• OK.
• Before you believe that all sorting algorithms are
• quadratic, I want to show you the last one,
• the one that actually is one of the-- I think--
• the prettiest algorithms around, and a great example
• of a more efficient algorithm.
• It's called merge sort.
• Merge sort takes an approach we've seen before.
• We talked about divide and conquer.
• Break the problem down into smaller versions
• of the same problem.
• And once you've got those solutions,
• bring the answer back together.
• For merge sort, that's pretty easy.
• It says, if I've got a list of 0 or 1 elements, it's sorted.
• Duh.
• OK.
• If I got a list of more than 1 element, here's my trick.
• I'm going to split it into two lists.
• I'm going to sort them.
• And when I'm done, I'm just going to merge those two lists
• into one list.
• And the merge is easy.
• Because if I've got two lists that are sorted,
• I just need to look at the first element of each,
• take the one that's smaller.
• Add it to my result. And keep doing that until one
• of the lists is empty.
• And then just copy the remainder of the other list.
• You can probably already get a sense
• of what the cost is going to be here, because this
• is cutting the problem in half.
• Now I've got two pieces.
• So I need to think about both of them.
• I want to give you a couple of visualizations of this.
• Here's the first one.
• It says, basically, I've got a big unsorted list.
• I'm going to split it.
• And I'm going to split it.
• And I'm going to split it.
• Until I get down to just lists that are either 0 or 1, which
• by definition are sorted.
• And once I'm at that level, then I just
• have to merge them into a sorted list
• and then merge them pairwise into a sorted list.
• And you get the idea.
• So it's divide and conquer.
• The divide is dividing it up into smaller pieces.
• The conquer is merging them back together.
• And we have Professor Guttag back for an encore,
• together with his students.
• So let's show you an example of merge sort.
• [VIDEO PLAYBACK]
• - So we're about to demonstrate merge sort.
• And we're going to sort this rather motley collection of MIT
• students by height.
• So the first thing we need to do is,
• we're going to ask everyone to split into a group of two.
• So you split a little bit.
• You two are together.
• You two are together.
• You two are together.
• You two are together.
• And you are all by yourself.
• I'm sorry.
• PROFESSOR: Poor Anna.
• - All right.
• So now let's take the first group.
• Take a step down.
• And what we do is, we sort this group by height,
• with the shortest on the left.
• And look at this.
• We don't have to do anything.
• Thank you.
• Feel free to go back up.
• We then sort the next pair.
• And it looks to me like we need to switch.
• All right.
• Take a step back.
• And again, OK.
• PROFESSOR: Notice each subgroup is now sorted.
• Which is great.
• - And I think you're in the correct order.
• Now what we do is, we take these groups and merge the groups.
• So let's have these two-- going to sort these groups,
• have them step forward.
• And now what we're doing is, we're
• doing a merge of the two sorted groups.
• So we start by merging them.
• We'll take the leftmost person in this group
• and compare her to the first person in this group,
• and decide.
• She's still the shortest.
• Take a step back.
• Now we're going to look at you and say,
• you're actually taller than this fellow.
• So you now step up there.
• And we're good here.
• Both of you take a step back.
• Now we'll take these two groups and follow the same procedure.
• We'll merge them.
• Let's see.
• We'll compare you-- the first person
• in this group to the first person in this group.
• Now it's a little tricky.
• So let's see, the two of you compare.
• Let's see, back to back.
• We have a winner.
• Step back.
• And now we need to compare the shortest person in this group
• to the shortest person in this group.
• We have a winner.
• It's you.
• I'm sorry.
• And now we just-- we're OK.
• Now we'll have these two groups come forward.
• We'll compare the shortest person in this group
• to the shortest person in that group.
• I actually need you guys to get back to back here.
• You are the winner.
• And it's pretty clear that the shortest person in this group
• is shorter than the shortest person in that group.
• So you go there and you step back.
• PROFESSOR: Notice the groups.
• Now all sorted.
• - And now we repeat the same process.
• PROFESSOR: And notice how the whole subgroup now
• goes up once we know that one group is empty.
• - And you can see that we have a group of students
• sorted in order by height.
• [END PLAYBACK]
• [APPLAUSE]
• PROFESSOR: Remember the first number, right?
• 55, 28.
• Now it's just numbers but you can
• see the expectation is, this is going to take less time.
• And it certainly did there.
• So again just to demo another way visually.
• I'm sorting-- sorry.
• I am splitting down until I get small things,
• and then just merging them up.
• I may have to do multiple passes through here,
• but it's going to be hopefully faster
• than the other methods we looked at.
• I'm going to show you code in a second,
• and then we're going to run it just to see it.
• But let me stress one more time just the idea of merging.
• You can see the idea.
• I keep splitting down till I got something small enough.
• And I want to merge them back.
• The idea of merging-- you've seen it from Professor Guttag.
• But I just want to highlight why this is going to be efficient.
• If I've got two lists: list 1 and list 2,
• the things left there.
• Process is very simple.
• I pull out the smallest element of each.
• I compare them.
• And I simply put the smallest one into the result,
• move on in that first list.
• So the 1 disappears from that left list.
• And now again I pull up just the smallest element of each one,
• do the comparison.
• Smallest one goes to the end of my result.
• And I drop that element from its list.
• So I've now taken 1 from list 1 and one from list 2.
• You get the idea.
• The reason I want to give you this visualization-- sorry.
• Let me do the last step.
• Once I get to a place where one of the lists is empty,
• just copy the rest of the list onto the end.
• You can see already a hint of the code.
• And that is, that I'm only going to ever look
• at each element of each sublist once as I do the merge.
• And that's a nice property.
• Having had them sorted, I don't need
• to do lots of interior comparisons.
• I'm only comparing the ends of the list.
• I only, therefore, look at each element--
• the number of comparisons, rather, I should say.
• I may look at each element more than once.
• The number of comparisons is going
• to be, at most, the number of elements in both lists.
• And that's going to be a nice Q as we
• think about how to solve it.
• So here's the code to merge, and then we'll write Merge Sort.
• And I know there's a lot of code here,
• but we can walk through it and get a good sense of it.
• I'm going to set up a variable called Result that's
• going to hold my answer.
• And I'm going to set up two indices, i and j, that
• are initially 0.
• They're pointing to the beginning.
• And remember, the input here is two lists
• that we know are sorted-- or should be sorted,
• or we screwed up in some way.
• So initially, i and j are both pointing to the beginning
• of the left and right list.
• And look at what we do.
• We say, as long as there's still something in the left list
• and still something in the right list-- i
• is less than the length of left, j
• is less than the length of right.
• Do the comparison.
• If the left wants smaller, add it to the end of result.
• To the end of result, right?
• I'm appending it because I want it to be in that sorted order.
• And increase i.
• If it's not, add the right one to the end of result
• and increase j.
• And I'll just keep doing that until I
• exhaust one of the lists.
• And when I do I can basically say,
• if the right list is empty, I know if I get out of here
• they can't both be true.
• In other words, if there's still something in the left list,
• just put it on the end.
• Otherwise if the only things left are in the right list,
• just put them on the end.
• So I'm just walking down the list, doing the comparison,
• adding the smallest element to my result. And when I'm done,
• I just return result.
• Complexity we can already begin to see here, right?
• This says the left and right sublists are ordered,
• so I'm just moving the indices depending on which
• one holds the smaller element.
• And when I get done, I'm just returning the rest of the list.
• So what's the complexity here?
• You could actually do that kind of relationship
• I did last time.
• But what am I doing?
• I'm going through the two lists, but only one time
• through each of those two lists.
• I'm only comparing the smallest elements.
• So as I already said, this says that the number of elements
• I copy will be everything in the left list and everything
• in the right list.
• So that order is just the length of left
• plus the length of right.
• And how many comparisons do I do?
• The most I have to do is however many are in the longer list.
• Right?
• That's the maximum number I need to have.
• Oh, that's nice.
• That says, if the lists are of order n-- I'm doing order n
• copies, because order n plus order
• n is just 2n, which is order n-- then
• I'm doing order n comparisons.
• So it's linear in the length of the lists.
• OK.
• Sounds good.
• That just does the merge.
• How do I do merge sort?
• Well we said it.
• Break the problem in half.
• Keep doing it until I get sorted lists.
• And then grow them back up.
• So there's merge sort.
• It says, if the list is either empty or of length 1,
• just return a copy of the list.
• It's sorted.
• Otherwise find the middle point--
• there's that integer division-- and split.
• Split the list everything up to the middle point
• and do merge sort on that.
• Split everything in the list from the middle point on.
• Do merge sort on that.
• And when I get back those two sorted lists, just merge them.
• Again, I hope you can see what the order of growth
• should be here.
• Cutting the problem down in half at each step.
• So the number of times I should have to go through this
• should be to log n the size of the original list.
• And you can see why we call it divide and conquer.
• I'm dividing it down into small pieces
• until I have a simple solution and then
• I'm growing that solution back up.
• So there is the base case, there's the divide,
• and there's the nice conquer [INAUDIBLE] piece of this.
• OK.
• I'm going to show you an example of that.
• But let's actually look at some code-- sorry about that.
• Let's look at some code to do this.
• And in fact I meant to do this earlier and didn't.
• I also have a version of bubble sort here.
• Sorry-- selection sort.
• I've already done bubble sort.
• There is selection sort.
• Let's uncomment this.
• And let's run both of those and just see
• the comparison between them.
• Yeah, sorry-- just make that a little easier to read.
• There we go.
• So we saw a bubble sort.
• It only went through four times, so less than n times.
• There's selection sort.
• And as I said to you, it has to do
• n passes it because it can only ever guarantee that it gets
• one element at the beginning.
• So you can in fact see, in this case, from the first
• or after the initial input until the end of the first step,
• it looks like it didn't do anything
• because it determined eventually that one was in the right spot.
• And similarly I think there's another one
• right there where it doesn't do any--
• or appears not to do anything.
• All it's guaranteeing is that the next smallest
• element is in the right spot.
• As we get through to the end of it,
• it in fact ends up in the right place.
• And then let's look at merge sort
• and do one more visualization of this.
• Again let me remove that.
• If we run it-- again, I've just put some print statements
• in there.
• Here you can see a nice behavior.
• I start off calling Merge Sort with that,
• which splits down into doing Merge Sort of this portion.
• Eventually it's going to come back down there and do
• the second one.
• It keeps doing it until it gets down to simple lists
• that it knows are sorted.
• And then it merges it.
• Does the smaller pieces and then merges it.
• And having now 2 merged things, it
• can do the next level of merge.
• So you can see that it gets this nice reduction of problems
• until it gets down to the smallest size.
• So let's just look at one more visualization of that
• and then get the complexity.
• So if I start out with this list-- sorry about that.
• What I need to do is split it.
• Take the first one, split it.
• Keep doing that until I get down to a base case
• where I know what those are and I simply merge them.
• Pass it back up.
• Take the second piece.
• Split it until I get down to base cases.
• Do the merge, which is nice and linear.
• Pass that back up.
• Having done those two pieces, I do one more merge.
• And I do the same thing.
• I want you to see this, because again you
• can notice how many levels in this tree log.
• Because at each stage here, I went from a problem
• of 8 to two problems of 4.
• Each of those went to two problems of 2,
• and each of those went to two problems of size 1.
• All right.
• So the last piece is, what's the complexity?
• Here's a simple way to think about it.
• At the top level, I start off with n elements.
• I've got two sorted lists of size n over 2.
• And to merge them together, I need to do order n work.
• Because as I said I got to do at least n comparisons where
• n is the length of the list.
• And then I've got to do n plus n copies, which is just order n.
• So I'm doing order n work.
• At the second level, it gets a little more complicated.
• Now I've got problems of size n over 4.
• But how many of them do I have?
• 4.
• Oh, that's nice.
• I know that I have to copy each element at least once.
• So not at least once.
• I will copy each element exactly once.
• And I'll do comparisons that are equal to the length
• of the longer list.
• So I've got four sublists of length n over 4
• that says n elements.
• That's nice.
• Order n.
• At each step, the subproblems get smaller
• but I have more of them.
• But the total size of the problem is n.
• So the cost at each step is order n.
• How many times do I do it?
• Log n.
• So this is log n iterations with order n work at each step.
• And this is a wonderful example of a log linear algorithm.
• It's n log n, where n is the length of the list.
• So what you end up with, then, is-- all right, a joke version,
• some reasonable ways of doing sort
• that are quick and easy to implement but are quadratic,
• and then an elegant way of doing the search that's n log n.
• And I'll remind you I started by saying, as long as I
• can make the cost of sorting small enough
• I can amortize that cost.
• And if you go back and look at last lecture's notes,
• you'll see n log n grows pretty slowly.
• And it's actually a nice thing to do.
• It makes it reasonable to do the sort.
• And then I can do the search in order n time.
• And here's the last punchline.
• It's the fastest we can do.
• I'm going to look at John again.
• I don't think anybody has found a faster sort algorithm.
• Right?
• This is the best one can do.
• Unless you do-- sorry, the best worst case.
• I'm sorry.
• John is absolute right.
• There are better average cases.
• Again, our concern is worst case.
• So this is as good as we're going
• to do in terms of a worst case algorithm.
• So there you now have sorting algorithms and searching
• algorithms, and you've now seen--
• excuse me, sorry-- constant, log, linear,
• log linear, quadratic, and exponential algorithms.
• I'll remind you, we want things as high up
• in that hierarchy as possible.
• All right.
• I have six minutes left.
• Some of you are going to leave us.
• We're going to miss you, but that's OK.
• I'm sure we'll see later on.
• For those of you hanging around, this isn't a bad time just
• to step back and say, so what have we seen?
• And I want to do this just very quickly.
• I'm sorry.
• And I'll remind you, we started by in some sense giving you
• a little bit of a contract of things
• we were going to show you.
• And I would simply suggest to you, what have we done?
• We've given you a sense of how to represent knowledge
• with data structures, tuples, lists, dictionaries, more
• complicated structures.
• We've shown you some good computational metaphors,
• iteration, and loops.
• Recursion has a great way of breaking problems down
• into simpler versions of the same problem.
• And there really are metaphors.
• There are ways of thinking about problems.
• We've given you abstraction, the idea of capture a computation,
• bury it in a procedure.
• You now have a contract.
• You don't need to know what happens inside the procedure
• as long as it delivers the answer it says it would.
• Or another way of saying it, you can delegate it
• to somebody and trust that you're going
• to get what you like out of it.
• We've seen classes and methods as a wonderful way
• to modularize systems, to capture combinations
• of data and things that operate on them in a nice, elegant way.
• And we just spent a week and a half
• talking about classes of algorithms
• and their complexity.
• If you step up a level, what we hope you've gotten out of this
• are a couple of things.
• You've begun to learn computational modes
• of thinking.
• How do I tackle a problem and divide and conquer?
• How do I think about recursion as a tool
• in dealing with something?
• You've begun to-- begun, I will use that word deliberately--
• to master the art of computational problem solving.
• How can you take a problem and turn it into an algorithm?
• And especially, you've begun to have the ability
• to make the computer do what you want it to.
• To say, if I've got a problem from biology or chemistry
• or math or physics or chemical engineering
• or mechanical engineering, how do I take that problem and say,
• here's how I would design an algorithm
• to give me a simulation and a way of evaluating what it does.
• And so what we hope we've done is,
• we've started you down the path to being able to think and act
• like a computer scientist.
• All right.
• Don't panic.
• That doesn't mean you stare at people's shoes
• when you talk to them.
• Not all computer scientists do that, just faculty.
• Sorry, John.
• So what do computer scientists do?
• And this is actually meant to be serious.
• And I put up two of my famous historical figures
• of computer scientists.
• They do think computationally.
• So the three A's of computational thinking.
• And in the same way that traditionally you
• computational thinking we hope is becoming a fundamental
• that every well-educated person is going to need.
• And that says, you think about the right abstraction.
• When you have a problem in your [INAUDIBLE]
• what's the right abstraction?
• How do I pull apart the pieces?
• How do I think about that in terms of decomposing things
• into a relationship that I can use to solve problems?
• How do I automate?
• How do I mechanize that abstraction?
• How do I use what I know happens inside of the machine
• to write a sequence of steps in a language I'm
• using to capture that process?
• And then finally, how do I turn that into an algorithm?
• And that not only means I need a language for describing
• those automated processes, and if you
• like allowing the abstraction of details,
• but frankly also a way to communicate.
• If you have to think crisply about how do I
• describe an algorithm, it's actually
• giving you a way to crystallize or clarify
• This is not to say you should talk to your friends in Python.
• I don't recommend it.
• But it does say you should use that thinking
• as a way of capturing your ideas of what you're going to do.
• And that leads, then, to this idea of,
• how difficult is a problem?
• How best can I solve it?
• We've shown you these complexity classes
• and we've hinted at the idea that in fact some problems
• are inherently more difficult than others.
• That's something I hope you come back to as you go along.
• And especially we want you to start thinking recursively.
• We want you to think about how do I take a hard problem,
• break it up into simpler versions of the same problem,
• and then construct the solution.
• And that shows up lots of places.
• Right?
• Recursion is in all sorts of wonderful places.
• So just to give you an example, I could say to you recursively,
• "This lecture will end when I'm done
• will end when I'm done--"
• All right.
• You don't like infinite recursion.
• Good luck on the exam.

### Description

MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
View the complete course: http://ocw.mit.edu/6-0001F16
Instructor: Prof. Eric Grimson

In this lecture, Prof. Grimson explains basic search and sort algorithms, including linear search, bisection search, bubble sort, selection sort, and merge sort.