Placeholder Image

Subtitles section Play video

  • [MUSIC PLAYING]

  • DOUG LLOYD: So in this video, we're going

  • to take a look at insertion sort, which is another algorithm that you

  • can use to sort an array.

  • And in this example, we're going to use an array of integers.

  • An algorithm, recall, is a step by step set

  • of instructions for completing a task.

  • The idea with insertion sort is as follows,

  • we're going to build the sorted array in place, shifting elements that

  • were previously considered sorted, if we need to,

  • in order to fit those elements in the right position

  • in the sorted portion of the array.

  • This is fundamentally different than how we've done things

  • with selection sort or bubble sort.

  • Recall with those algorithms what we do is,

  • we usually end up just sorting one element.

  • We have to go through the entire array to put

  • one element in the correct position.

  • For bubble sort, it's usually the largest element that's available.

  • For selection sort, it's usually the smallest element.

  • But we're only getting one at a time.

  • We're not making-- you know, we have to go through this array multiple times.

  • With insertion sort, we only are going to move forward through the array once.

  • We might have to look back at things we've already sorted to sort of shift

  • them around to make room.

  • But we only have to make one forward pass of the entire array.

  • So that's sort of a fundamental difference.

  • And the way we do this is we get started, we just

  • say the first thing we see is sorted.

  • It's the only thing we've seen so far.

  • So it might as well be sorted.

  • Then we just do the following for every element that remains.

  • We look at that element and we maybe shift things

  • that we previously considered sorted, just

  • to make room for it, until we get through every single element.

  • This will probably make a little bit more sense when you see it visually.

  • So let's illustrate that now with this array.

  • In this array, what I want to do is everything that's red is unsorted,

  • everything that's blue is sorted.

  • So keep that in mind as we go through this example.

  • So recall that the first thing we do is we

  • declare the first element of the array is sorted.

  • So that's five.

  • We just see it.

  • We're like, got it.

  • This one is sorted.

  • So we have the sorted portion in blue.

  • And we this five element unsorted portion in red.

  • Now we're going to repeat the following process

  • until everything else is sorted.

  • We look at the next unsorted element and we maybe

  • shift things around in the blue section in order

  • to put that element in the correct sorted position.

  • So the first element that we see is two.

  • We take a look, we see is there anything we need

  • to do to put two in the right spot.

  • The answer is yes.

  • We need to shift five over in order to put two in front of it.

  • So we slide five over.

  • And then we put two where five basically was in memory.

  • And now two, five is sorted and the red portion is unsorted.

  • Let's repeat this process again.

  • The next thing we see is a one.

  • We take a look at the blue portion.

  • What do we have to move?

  • Well here, again, we have to move everything,

  • because one comes before both two and five.

  • So both of them slide over.

  • And that leaves one vacancy to put the one.

  • The next thing we see is three.

  • What do we have to move this time in order to get everything into position?

  • Well, it's not everything this time.

  • We just have to move the five over.

  • So we move the five to where the three was.

  • And then we put the three where the five just vacated.

  • The next element that we see is 6.

  • And this is sort of a special case of insertion sort, where

  • it's larger than everything in the sorted portion, which

  • is great because then we don't have to move anything at all.

  • We just say, all right, well, six is in the right spot.

  • We can just declare six to be sorted.

  • And then the final element we have here is four.

  • So we take a look at that.

  • We look back at the blue portion, the sorted portion of the array.

  • We figure out what we need to slide over.

  • It's just the five and the six.

  • They slide over which makes room for the four.

  • And now we have sorted our entire six element array using the insertion sort

  • algorithm.

  • Now again, this feels very different than anything we've seen before.

  • But unfortunately it's still n squared algorithm.

  • So for example, imagine if the array is in reverse order.

  • So it's six, five, four, three, two, one.

  • In that case, we have to shift each of the elements n positions every time we

  • want to make an insertion.

  • So we see this six, five, four, three, two, one array.

  • The six is good.

  • Then we see the five.

  • We have to shift the six over.

  • Then we see the four.

  • We have to shift of six and the five over.

  • Then we see the three.

  • We have to shift the six and the five and the four.

  • So we just keep getting worse.

  • We have to keep making all these shifts.

  • And each one of those costs us.

  • So even though this looks and feels very different

  • than a bubble sort or a selection sort, this is still n squared, unfortunately.

  • In the best case scenario though, the array is perfectly sorted.

  • And this is sort of that example we saw a second ago with the five and the six,

  • where we just said, oh, well that's kind of convenient.

  • The six is greater than everything in the sorted portion,

  • so we just kind of moved the line over.

  • We just changed it from red to blue without changing anything.

  • In the best case scenario, we just do that for every element-- one, two,

  • three, four.

  • We just keep changing them red to blue, no shifts.

  • And so if we think about this in asymptotic notation, that

  • means that this algorithm is a big O of n squared, but it's still omega of n.

  • I'm Doug Lloyd.

  • This is CS50.

[MUSIC PLAYING]

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

B1 sorted array element insertion sort portion

Insertion Sort

  • 0 0
    林宜悉 posted on 2020/04/13
Video vocabulary