0:00

[MUSIC]

Â So now we're ready to analyze the performance of some of the sorting

Â algorithms that we've already talked about.

Â So by the end of this video,

Â you'll be able to state and justify the asymptotic performance, so

Â the big O classes for the running time, of both selection sort and insertion sort.

Â And we'll be thinking about them, both in the best case and in the worst case.

Â Now, for both of these sorting algorithms if you need a refresher just go back

Â to the first course in the specialization.

Â That's when we talked about them in quite a bit of detail.

Â But, we'll be doing an overview now, as well.

Â So, our goal is to fill in this table with big O classes that represent the best and

Â worst case performance for these two sorting algorithms.

Â 0:43

So let's start with selection sort, and

Â in selection sort we take a list or an array of data.

Â And what we'd like to do is organize it so that it's presented

Â in order from smallest to biggest based on some measure of smallest and biggest.

Â And so our strategy is going to look at each position in the array in turn.

Â And for each of those positions, find the right element to put in there.

Â And so we look at all of the possible elements remaining in the array.

Â And figure out which one of those is smallest and

Â put it in this current position.

Â Okay, so that's the algorithm.

Â And so now, let's think ahead about what insertion sort algorithm is going to do.

Â It's a little bit different.

Â We're still going through all of the positions in the array in turn.

Â But instead of looking for the correct elements to put in each time,

Â what we're doing is looking at the current value that we're focused in and nudge

Â it over to its correct position relative to the elements that are already listed.

Â So we're still going step by step and increasing the part of the array that's

Â sorted each time, but doing it in a slightly different strategy.

Â And we'll see the impact of these different strategies

Â on their performance of the two algorithms.

Â So let's start with selection sort, and

Â let's think about the performance of this sorting algorithm.

Â So we actually used selection sort in a previous support video where

Â we went through the code for selection sort and computed its performance.

Â This was an example of nested for

Â loops that were really interesting to analyze and we used some cool identities.

Â But notice that when we did that analysis, we could say,

Â this algorithm is big O of n squared, it's quadratic, and when we did that,

Â it was before we said anything about best case, worst case, average case.

Â We weren't even thinking about the input or

Â how it was organized, because this sorting algorithm, if you think about it,

Â doesn't really care what the input looks like when you first get it.

Â It goes through and

Â does the same sequence of steps no matter how its input is organized.

Â So the number of steps, the performance of the sorting algorithm,

Â only depends on the size of the array that it starts with.

Â It doesn't depend on how the contents of the array are organized and

Â that means that the best case and

Â the worst case performance of this algorithm are exactly the same.

Â It's the same as the average case.

Â It's the same as any case, so for any array of size n, the best case and

Â worst case performance of selection sort, is big O of n squared.

Â 3:26

Okay, so that's the one algorithm.

Â Now let's think about the insertion sort algorithm, and

Â try to fill in some of those questions marks, and we haven't analyzed it yet.

Â So let's do it now, and what we're trying to do,

Â as I mentioned earlier, is focus on one new element of the array at a time.

Â And for that new element put it in its correct location relative to the earlier

Â ones that have been sorted already.

Â And so we assume that at each point we have that initial

Â piece of the arrays already sorted.

Â And so what we need to do is figure out where the next element goes and

Â we do that by comparing that next element to,

Â well, the highest element in the sorted part of the array and

Â see, well should I swap their locations or not?

Â And then maybe I'm gonna need to swap again, and

Â maybe I need to swap again until the new element gets to its correct

Â relative location based on the previously sorted pieces of the array.

Â Okay, so what would the best case of this algorithm look like?

Â And in order to do that, we need to focus in on that for loop.

Â Where that for loop looks at each position in the array and

Â says, I'm going to put the element in this position, in its correct location.

Â And the piece that really depends on the values is the inner while loop.

Â So, the inner while loop maybe gets executed

Â a different number of times, based on the relative

Â size of the consecutive pairs of elements in the array.

Â So, let's think about the best case first.

Â So, in the best case,

Â what we would have, is that we don't need to make very many swaps at all.

Â So we're looking at a new element in the array, and we'd like to find its correct

Â relative position, relative to the earlier elements in the array.

Â And if we're really lucky then it's already going to be in that position.

Â Well what that would mean is that it's bigger

Â than the biggest element in the already sorted part of the array.

Â And so, what we need to check is that the current index has,

Â 5:35

the value of that current index is already bigger than the value

Â at the last piece of the already sorted part of the array.

Â So when does that happen?

Â Well, it happens when the array that we start with is already sorted.

Â Every time we look at a new element, it's already in its correct location

Â relative to the earlier ones, so we don't need to do anything.

Â The body of the while loop never executes.

Â And so when we look at the performance in this case,

Â that means that every time we try to start executing the while loop,

Â all we need to do is do that just one test, and it's going to evaluate to false.

Â And we go away from it, and we go to the next iteration of the for loop.

Â And so that means that the body of the for loop in this case,

Â when the array's already sorted, every time we go through the for loop,

Â we just execute a constant number of instructions.

Â And so all in all, we have n iterations of the for loop, each time doing

Â just a constant amount of work, and so all in all we have just O(n) work.

Â So when the array is already sorted, in this best-case lucky,

Â lucky scenario, insertion sort just takes big O(n) time.

Â Cool. That's much, much better than quadratic,

Â which was selection sort.

Â So that's interesting, okay.

Â Is it gonna be good all the time?

Â Is it a big win?

Â Well, so let's think about the worst case.

Â So what input might we get that would require us to run many, many steps?

Â And remember the piece that we're focusing in on is that inner while loop.

Â Where we're nudging the current value that we're looking at to its correct location

Â within that first part of the array that's already sorted.

Â So, if we think about what might make us really unlucky

Â is if we have to do a lot of the nudging, a lot of the swaps over.

Â And so, if we think of our arrays being really far from sorted, then we're gonna

Â have to do a lot of work to keep moving these elements to their correct location,

Â relative to the sorted part of the array.

Â So, thinking about an array that's given to us in reverse sorted order,

Â we're going to have to do a lot of work in this algorithm in order to get it

Â to the correct form,

Â namely going from one through five, rather than from five through one.

Â So in this worst case analysis what we see is that when we are looking at,

Â for example, at the second position, so position equals 1,

Â then when we want to nudge 4 over to its correct location we have to do a swap.

Â And then when we look at the next index at position 2, then in order to move 3

Â to its correct location we're going to have to swap it twice.

Â And so every time we're going to have to swap all the way over to

Â the head of the array and so all together what's going to happen is that

Â on average we're gonna have about O(n) many swaps for each position.

Â And that happens n many times as we go through all the positions.

Â And so we get to O(n) squared amount of work.

Â And so the analysis at the end was a little brief but

Â it's really similar to what we do when we think about analyzing selection sort.

Â So go back and

Â revisit that support video if you'd like to see a little bit more detail.

Â Now what we wanna keep in mind, though, is that the worse case for

Â insertion sort happened when our input array was in reverse order.

Â And so this is really illustrating how

Â the structure of the input can determine the performance of our algorithm.

Â And when we're thinking about worst-case analysis, we want to think about

Â the kinds of inputs that will make us do the most amount of work.

Â