 ## 字幕表 動画を再生する

• [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.

• 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.

• 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]

B1 中級

# 挿入ソート (Insertion Sort)

• 0 0
林宜悉 に公開 2021 年 01 月 14 日