1
00:00:00,570 --> 00:00:00,870
OK.

2
00:00:00,900 --> 00:00:06,630
Welcome back to another listen, everybody in this listen, we are going to be going over insertion

3
00:00:06,630 --> 00:00:13,920
sort, so this is a new sort and it is kind of like a bubble sword, not too much more complex.

4
00:00:14,280 --> 00:00:19,440
But the reason I'm introducing it is just because I think it's important for us to look to at least

5
00:00:19,440 --> 00:00:21,000
at a couple of swords.

6
00:00:21,450 --> 00:00:24,300
So I gave you that challenge to kind of come up with your own sort.

7
00:00:24,660 --> 00:00:30,150
But this will kind of expose you to other ideas that other people had to solve this sorting problem.

8
00:00:30,930 --> 00:00:36,240
And it's important for us to kind of look into these different things as well just to kind of intellectually

9
00:00:36,240 --> 00:00:40,830
challenge ourselves because we're getting into a portion of the course where we're needing to like manipulate

10
00:00:40,830 --> 00:00:41,730
data more.

11
00:00:42,570 --> 00:00:49,890
You know, the sorting challenge is kind of a an interesting one because we have to really focus on

12
00:00:50,430 --> 00:00:58,500
the values of things and think about the fastest way or most efficient way that we could get those into

13
00:00:58,500 --> 00:00:59,360
the right order.

14
00:00:59,370 --> 00:01:00,030
And so.

15
00:01:01,320 --> 00:01:03,900
There's some really cool sorting algorithms out there.

16
00:01:04,290 --> 00:01:14,400
The two kind of most renowned ones that performed the best in terms of efficiency are merge sort and

17
00:01:14,400 --> 00:01:15,180
quick sort.

18
00:01:16,470 --> 00:01:22,260
Those are kind of the de facto ones that people use for sorting because they are quite fast.

19
00:01:22,650 --> 00:01:29,760
I'm not going to get into this at this point in the course because they kind of sometimes rely on this

20
00:01:29,760 --> 00:01:35,070
concept that we haven't gone over, but that we're going to go over in the algorithms and data structures

21
00:01:35,070 --> 00:01:35,550
section.

22
00:01:35,550 --> 00:01:39,810
So I don't want to go over those quite yet.

23
00:01:39,810 --> 00:01:43,350
But if you would like to look into those like merge sort, it might be a good one.

24
00:01:44,070 --> 00:01:50,040
That one is a lot more efficient than both this insertion sort and bubble sort, so that could be a

25
00:01:50,370 --> 00:01:51,330
cool one to check out.

26
00:01:51,330 --> 00:01:54,980
But I felt like it was a little bit too confusing for this part of the course.

27
00:01:54,990 --> 00:01:59,340
So if you like, checked out in the hour and welcome to you and I'm going to go over another pretty

28
00:01:59,340 --> 00:02:04,230
basic sort, it's just slightly more complex than bubble sort, but not really.

29
00:02:04,350 --> 00:02:06,600
So let's go ahead and get into it.

30
00:02:07,650 --> 00:02:14,520
So insertion sort is kind of doing the opposite of bubbling remember bubbling with us and moving stuff

31
00:02:14,520 --> 00:02:18,900
from the left to the right, and it was kind of piling up one by one at the end here.

32
00:02:19,560 --> 00:02:26,670
But the goal of insertions or is to pull a new element into a left most sorted portion of the array

33
00:02:26,700 --> 00:02:30,540
and keep doing that until the end of the array of vectors reached.

34
00:02:30,540 --> 00:02:35,700
So let's just pretend that we start here on the left, which we don't, and that's what we're going

35
00:02:35,700 --> 00:02:36,060
to do.

36
00:02:36,660 --> 00:02:40,020
But what we want to do is say, OK, whatever to the right of me.

37
00:02:40,020 --> 00:02:42,390
Can I insert that into here?

38
00:02:42,810 --> 00:02:45,630
Is it like less then than this?

39
00:02:46,200 --> 00:02:51,390
If so, then what I can do is bring it in and then keep moving it until it's in the right position.

40
00:02:51,390 --> 00:02:57,060
And we're going to keep track of the sorted portion of the array, and I'll color that in green.

41
00:02:58,080 --> 00:02:59,640
So let's go ahead and start.

42
00:03:00,120 --> 00:03:05,910
So what we're going to do right off the bat is look at this first item eight and the item right after

43
00:03:05,910 --> 00:03:06,060
it.

44
00:03:06,060 --> 00:03:06,510
Three.

45
00:03:07,420 --> 00:03:12,470
And we noticed that what we can do is swap those to you because three is less than eight.

46
00:03:12,520 --> 00:03:21,190
So that's what we do and what we do now is we're going to consider this portion of the array as sorted

47
00:03:21,490 --> 00:03:23,290
because we have done this swap.

48
00:03:24,630 --> 00:03:27,240
When we start off, we just consider this as sorted.

49
00:03:27,630 --> 00:03:33,480
But now, since we've kind of swapped it, we're going to move to the next square here and we're going

50
00:03:33,480 --> 00:03:34,680
to consider that sorted.

51
00:03:34,690 --> 00:03:39,780
So I didn't market green in the beginning, but we can kind of think of this as being sorted.

52
00:03:40,410 --> 00:03:44,430
It just has the number eight eight one number by itself is sorted.

53
00:03:45,300 --> 00:03:48,840
So I didn't really want to show until we got to two.

54
00:03:48,840 --> 00:03:54,980
But now that we've swapped it, we have now moved over to here and now we are considering this square

55
00:03:56,220 --> 00:04:00,420
and we can say that since these two swap, this is sorted right?

56
00:04:00,430 --> 00:04:01,690
Three comes before eight.

57
00:04:01,710 --> 00:04:06,180
This section right here is a sorted portion of the whole array.

58
00:04:07,170 --> 00:04:11,130
So what we are doing is we are moving this way.

59
00:04:12,770 --> 00:04:18,650
And each time that we move one this way, we're trying to see if we can take this thing, the next thing

60
00:04:18,650 --> 00:04:24,530
in the gray area and move it into the green area if as long as it's less, and then we're just going

61
00:04:24,530 --> 00:04:29,780
to continue moving it through the green area until it arrives in the right position.

62
00:04:30,170 --> 00:04:34,880
So in this next instance, we're going to try and take two and see if it can be moved into the green

63
00:04:34,880 --> 00:04:36,080
area, which is sorted.

64
00:04:36,560 --> 00:04:41,720
And then we're going to make sure that we keep moving to to the left until it's at the right position.

65
00:04:43,060 --> 00:04:48,070
So you can already kind of think of this in terms of code you might be realizing, OK, well, we kind

66
00:04:48,070 --> 00:04:55,480
of have this one repeated thing of moving to the right and for every time that we move on to the right,

67
00:04:55,870 --> 00:05:00,730
we are going to potentially take an item and move it to the left a bunch.

68
00:05:01,240 --> 00:05:03,220
So think about that.

69
00:05:04,390 --> 00:05:10,300
We'll be getting into the code, of course, after we go over this theoretical portion, but now what

70
00:05:10,300 --> 00:05:15,100
we're doing, of course, like I said, is comparing two to eight is to less than eight.

71
00:05:15,130 --> 00:05:15,970
Yes, it is.

72
00:05:15,970 --> 00:05:18,060
So we can put it into the green area.

73
00:05:18,070 --> 00:05:19,990
So we swap these two, actually.

74
00:05:22,140 --> 00:05:28,350
And then so what we're going to do is now see if we can move to further through the green area, which

75
00:05:28,350 --> 00:05:32,430
we can write to is less than three as well, so we can swap two over.

76
00:05:32,820 --> 00:05:37,440
And now we're going to consider all of these three to be a small portion.

77
00:05:37,440 --> 00:05:39,690
So we're going to move over to the square now.

78
00:05:40,500 --> 00:05:42,090
So this is all sorted here.

79
00:05:42,270 --> 00:05:46,050
What we're going to do next now is see if we can move nine into the green area.

80
00:05:46,380 --> 00:05:50,760
Nine is not less than eight, though, so we're not going to move nine into that area.

81
00:05:51,630 --> 00:05:52,920
So we're going to move over.

82
00:05:53,050 --> 00:05:54,480
This is all sorted, right?

83
00:05:54,480 --> 00:05:55,590
Two three eight nine.

84
00:05:56,650 --> 00:05:58,810
Now we're going to see if we can move forward to the green area.

85
00:05:59,020 --> 00:06:02,740
As for less than nine, well, yes, it is, so we can move it in there.

86
00:06:03,130 --> 00:06:08,110
And now our job is to make sure that we move for into its correct position.

87
00:06:08,110 --> 00:06:10,420
So is for less than eight years.

88
00:06:10,430 --> 00:06:11,140
So swap.

89
00:06:12,280 --> 00:06:12,650
Let's go.

90
00:06:12,670 --> 00:06:13,940
Here it is for less than three.

91
00:06:13,960 --> 00:06:14,680
No, it's not.

92
00:06:14,680 --> 00:06:15,730
So leave that.

93
00:06:16,960 --> 00:06:21,550
And then now we move over another square, but we're at the last square, so we're pretty much done.

94
00:06:21,550 --> 00:06:25,630
Their whole array is sorted, so we have two three four eight nine.

95
00:06:27,030 --> 00:06:34,140
OK, so now I'm going to head over to the editor to do some code for this, so I'm going to go over

96
00:06:34,140 --> 00:06:34,980
to them.

97
00:06:34,980 --> 00:06:37,110
You can head over to whatever editor you would like.

98
00:06:39,270 --> 00:06:48,870
But I've kind of already made a file here, and I've included I stream Vector using a namespace and

99
00:06:48,870 --> 00:06:54,290
I made a main function, so I'm going to go ahead and make a vector just like we did for bubble sort.

100
00:06:54,330 --> 00:06:58,860
So I'm going to call it a vector type and animate part my vector.

101
00:06:59,460 --> 00:07:05,820
I'm also going to make an ant called my end so we can read into it just like we did with bubble sort.

102
00:07:06,900 --> 00:07:09,480
I will want to make attempts so I can do swaps.

103
00:07:09,480 --> 00:07:16,050
And then another two variables that I'm going to want to make is a variable for the actual item that

104
00:07:16,050 --> 00:07:20,640
we're going to try and moved into the storage portion.

105
00:07:20,640 --> 00:07:26,100
So an item that needs to be inserted from the gray section into the green section, right?

106
00:07:26,100 --> 00:07:32,040
So that next box, let's say we're on the lake, right?

107
00:07:32,040 --> 00:07:36,540
Most green box, so I can bring up the graphic here again.

108
00:07:37,410 --> 00:07:44,150
Let's say that we're here and we want to look to see if we can take this great item and insert in here.

109
00:07:44,160 --> 00:07:50,250
So this gray box, whatever stored here, which is nine, that is what we're going to consider for our

110
00:07:50,580 --> 00:07:52,740
variable to be inserted.

111
00:07:53,430 --> 00:07:55,320
So I'm going to make an integer variable for that.

112
00:07:55,320 --> 00:07:59,070
And then another thing I want to do is keep track of the positions in the green.

113
00:07:59,070 --> 00:08:04,920
So as we're moving to the left through the sorted portion, I want to have a variable to keep track

114
00:08:04,920 --> 00:08:05,380
of that.

115
00:08:05,400 --> 00:08:06,840
And why do I want to do that?

116
00:08:06,870 --> 00:08:13,740
Well, I think I'm going to use a while loop to be able to handle that because I want to keep swapping

117
00:08:13,740 --> 00:08:14,790
to the left.

118
00:08:15,480 --> 00:08:25,020
As long as the, you know, number that I'm considering is less than the number, the next number to

119
00:08:25,020 --> 00:08:25,590
the left.

120
00:08:26,370 --> 00:08:28,490
So I want that's a condition, right?

121
00:08:28,500 --> 00:08:31,110
And then I also want to make sure that I don't go off the end.

122
00:08:31,110 --> 00:08:36,570
So I don't want it to be zero so that I have to be another condition with that kind of calls for two

123
00:08:36,570 --> 00:08:37,230
variables, right?

124
00:08:37,230 --> 00:08:43,560
A variable for the inserted, the item that needs to be inserted into the green portion and then another

125
00:08:43,560 --> 00:08:47,280
variable that keeps track of whatever position we're on in that green portion.

126
00:08:47,460 --> 00:08:58,860
So I'm going to say like an insertion item and then I'll say, and this will just be sorted position.

127
00:09:00,060 --> 00:09:02,380
So what I'm going to do now is just make a for loop.

128
00:09:02,400 --> 00:09:08,490
In fact, I'm just going to start out with like that standard like five, we're going to have like something.

129
00:09:09,640 --> 00:09:16,030
They ask the user to enter five numbers, just like we started out with with bubble sort, so I'm just

130
00:09:16,030 --> 00:09:18,400
going to do that so we can have some continuity here.

131
00:09:19,840 --> 00:09:27,390
So I'll go ahead and print out, just enter a number and then I'll scan into that in the end.

132
00:09:28,300 --> 00:09:32,710
And then what I want to do is I want to push back to my vector, right?

133
00:09:32,710 --> 00:09:35,590
So I want to push back my end to the vector.

134
00:09:36,760 --> 00:09:45,640
Then now comes the part for sorting, so let's see or do so with the insertion stored portion.

135
00:09:46,300 --> 00:09:52,290
So we got to think about the fact that we're doing kind of two processes, right?

136
00:09:52,300 --> 00:09:58,800
So we're moving one to the right through the whole array, and that's us trying to make, you know,

137
00:09:58,840 --> 00:10:00,820
increase the sorted portion.

138
00:10:00,820 --> 00:10:06,550
So it's like move to the right one and now put a green box there, moved to the right one and put a

139
00:10:06,550 --> 00:10:07,270
green box there.

140
00:10:07,270 --> 00:10:11,550
And that's like us increasing the size of the green screen portion, right?

141
00:10:11,560 --> 00:10:13,720
So that's going to be an outer loop for us.

142
00:10:13,730 --> 00:10:21,420
So I'm going to say four and I equals and I equals zero.

143
00:10:21,430 --> 00:10:26,920
I less than my vector size I plus plus.

144
00:10:27,820 --> 00:10:34,720
And then what I want to do in here is I want to make sure to set that variable that we're currently

145
00:10:34,720 --> 00:10:36,910
considering to be inserted, right?

146
00:10:37,150 --> 00:10:48,490
So I have this insertion item, and what I'm going to do is say insertion item equals the current item

147
00:10:48,490 --> 00:10:50,290
that I am on right now.

148
00:10:50,290 --> 00:10:52,840
So I'm going to call that my effect.

149
00:10:52,840 --> 00:10:53,410
I.

150
00:10:54,640 --> 00:10:59,650
So we're just going to consider that we move over to like some gray box, right?

151
00:10:59,650 --> 00:11:08,920
And then we're going to consider moving that item in that gray box to the left into the green portion.

152
00:11:08,950 --> 00:11:13,870
So I also want to keep track of the position for that green portion.

153
00:11:13,870 --> 00:11:17,410
So what I'm going to do them is a sorted position.

154
00:11:18,220 --> 00:11:18,610
Oops.

155
00:11:19,390 --> 00:11:25,240
Sorry, position is equal to I minus one, right?

156
00:11:25,240 --> 00:11:29,240
Because we want to be one to the left of where we are.

157
00:11:29,260 --> 00:11:31,180
So let's go ahead and think about this.

158
00:11:31,180 --> 00:11:32,350
So what if we were here?

159
00:11:32,500 --> 00:11:34,140
This is going to be I.

160
00:11:34,690 --> 00:11:39,190
And so we are interested in whatever is there at.

161
00:11:39,220 --> 00:11:42,010
I write my vector is the insertion item.

162
00:11:42,460 --> 00:11:43,970
So in this case, it would be nine.

163
00:11:43,990 --> 00:11:45,370
This is our insertion item.

164
00:11:46,240 --> 00:11:53,490
But then our position that we want to start out with to consider for the green portion is one less right,

165
00:11:53,500 --> 00:11:54,800
one less right here.

166
00:11:55,570 --> 00:12:02,410
One position less is the start of the green portion and we're going to be moving this way through the

167
00:12:02,410 --> 00:12:03,220
green portion.

168
00:12:03,260 --> 00:12:03,610
All right.

169
00:12:04,330 --> 00:12:07,390
So that's why I'm saying sort of position equals I minus one.

170
00:12:07,390 --> 00:12:10,750
So we're going to start out there and then we need to move left.

171
00:12:12,400 --> 00:12:18,460
So since we're going to move left, what I'm going to do is use another loop, but I'm going to use

172
00:12:18,460 --> 00:12:21,190
a while loop because I want it to be based on a condition.

173
00:12:22,210 --> 00:12:31,030
So I'm going to say while and this is going to be well sorted, position is greater than or equal to

174
00:12:31,030 --> 00:12:33,300
zero because I don't want to go off the end, right?

175
00:12:33,310 --> 00:12:37,900
Like if I don't want to go here, here, here and then I'm at zero and then I keep trying going.

176
00:12:38,640 --> 00:12:42,400
So I keep keep trying to move to the left.

177
00:12:43,240 --> 00:12:44,110
I don't want to do that.

178
00:12:44,110 --> 00:12:46,930
So I'm going to make sure that I have that.

179
00:12:46,930 --> 00:12:50,650
And I must say, how long or what's the condition that we keep?

180
00:12:50,650 --> 00:12:53,140
We keep wanting to move through it, right?

181
00:12:54,200 --> 00:12:57,890
It's whether we're swapping like these items or not, right, so.

182
00:12:59,640 --> 00:13:04,170
Go ahead and present this, so we're swapping like B for over, right?

183
00:13:04,380 --> 00:13:06,090
So we had a for here.

184
00:13:06,840 --> 00:13:11,880
We move the floor into the sordid portion and then what do we do?

185
00:13:11,880 --> 00:13:13,590
So now we're in our while loop.

186
00:13:14,010 --> 00:13:18,030
So what we want to do is keep moving to the left.

187
00:13:18,540 --> 00:13:25,050
As long as this thing right here is less than this thing right here, right?

188
00:13:26,080 --> 00:13:28,330
So what is that going to be?

189
00:13:28,360 --> 00:13:38,740
Well, it's going to be as long as my vet sorted position.

190
00:13:42,490 --> 00:13:45,550
Is greater than.

191
00:13:45,760 --> 00:13:52,210
So that means that the thing that we're on in here, so like eight or something like that, as long

192
00:13:52,210 --> 00:14:01,400
as this is greater than what was four, well, four was actually our original insertion item here,

193
00:14:01,400 --> 00:14:01,660
right?

194
00:14:01,680 --> 00:14:04,180
So we wanted to take four.

195
00:14:04,190 --> 00:14:07,180
We inserted it into here, right?

196
00:14:07,180 --> 00:14:08,070
That's what we want to do.

197
00:14:08,080 --> 00:14:10,680
So this is our insertion item, right?

198
00:14:10,690 --> 00:14:13,360
So we're wanting to compare the thing to the left.

199
00:14:15,040 --> 00:14:16,990
To this insertion item.

200
00:14:17,770 --> 00:14:23,800
So that's what we're going to do, remember, these sordid position starts off one to the left.

201
00:14:24,190 --> 00:14:26,790
So just to kind of show again, it's going to be right here.

202
00:14:26,800 --> 00:14:28,630
So this is sort of position, right?

203
00:14:28,630 --> 00:14:29,680
Just this box.

204
00:14:30,160 --> 00:14:30,910
It's not nine.

205
00:14:30,910 --> 00:14:31,720
It's just this box.

206
00:14:31,720 --> 00:14:35,740
My vet index sort of position is the nine.

207
00:14:36,940 --> 00:14:41,740
So we're doing that, and we're wanting to compare it to the insertion item, right, the insertion

208
00:14:41,740 --> 00:14:44,130
item is this fall right here in this example.

209
00:14:45,230 --> 00:14:53,450
So as long as that and my vague sort of position is greater than my insertion item, then I want to

210
00:14:53,450 --> 00:14:54,530
keep moving to the left.

211
00:14:54,530 --> 00:14:59,000
And also, of course, as long as the sorted position is greater than or equal to zero, we do not want

212
00:14:59,000 --> 00:15:02,350
to go off the left end of the array or vector right.

213
00:15:03,740 --> 00:15:04,860
So what do we do now?

214
00:15:04,880 --> 00:15:07,270
Well, we're just going to keep swapping it through, right?

215
00:15:07,280 --> 00:15:08,870
So let's go ahead and use our tent.

216
00:15:09,170 --> 00:15:13,150
This is just us doing that similar swap code that we used for bubble sort.

217
00:15:13,160 --> 00:15:21,860
So I'm going to say temp equals my vet sorted position Exposicion.

218
00:15:23,270 --> 00:15:41,120
And then I'm going to say my vet storage position equals my vet sorted post this position plus one because

219
00:15:41,120 --> 00:15:46,280
I want the thing to the right of it to now be swapped into the current position mine.

220
00:15:46,760 --> 00:15:52,190
And since I made this temporary here, I can now say that my vague sort of position plus one should

221
00:15:52,190 --> 00:16:01,430
be temp so I can actually go over and just copy this, yank this and paste this here.

222
00:16:02,480 --> 00:16:09,680
So this is just code that you should be familiar with is similar to what we did in bubble soy.

223
00:16:09,680 --> 00:16:15,980
So it's just making attempts so we can hold this original value of my exalted position.

224
00:16:15,980 --> 00:16:20,990
And then we take the thing to the right and put it into where we're currently at in the vector.

225
00:16:20,990 --> 00:16:24,740
And then since we already have overwritten that, thankfully we saved it.

226
00:16:24,740 --> 00:16:29,150
We can say now the thing the position to the right should hold the temp that we saved.

227
00:16:30,740 --> 00:16:31,070
All right.

228
00:16:31,070 --> 00:16:36,350
So after swapping, all we have to do since we're in this wow loop is, of course, update our sort

229
00:16:36,350 --> 00:16:37,160
of position, right?

230
00:16:37,160 --> 00:16:39,560
Because we now need to move to the left again.

231
00:16:40,580 --> 00:16:49,850
So all I'm going to do is, say sorted position minus minus so I can move one to the left, and that's

232
00:16:49,850 --> 00:16:51,380
really all there is to it.

233
00:16:53,170 --> 00:17:02,170
This outer loop is to keep moving the through the array originally with increasing our sorted portion

234
00:17:02,860 --> 00:17:04,210
by one each time, right?

235
00:17:05,200 --> 00:17:09,730
And then we grab our insertion item, the thing that we want to put into that sordid portion and then

236
00:17:09,730 --> 00:17:15,580
we say, well, the start of the sordid portion is going to be wherever we're at for that insertion

237
00:17:15,580 --> 00:17:18,610
item minus one minus one.

238
00:17:19,240 --> 00:17:21,370
And then what we're going to do is say, OK, let's start.

239
00:17:21,370 --> 00:17:26,800
It loops to move something through this sort of position as long as it's greater.

240
00:17:26,830 --> 00:17:32,080
Of course, we don't want to even move it into the sort of position if it's not greater than it, right?

241
00:17:32,290 --> 00:17:32,680
Sorry.

242
00:17:32,980 --> 00:17:41,740
I mean, less than as long as the insertion item is less than that first position in the green portion.

243
00:17:42,610 --> 00:17:45,520
And then we just keep swapping it to the left through the green portion, right?

244
00:17:45,540 --> 00:17:47,040
And that's what this loop is doing right here.

245
00:17:47,050 --> 00:17:52,180
It's just a simple swap and then minus minus and then swap and then minus minus.

246
00:17:52,600 --> 00:17:58,030
And just keeps doing that until it gets to the very beginning of the array or whether it's in the right

247
00:17:58,030 --> 00:18:04,240
position because it's no longer wherever we're at is no longer greater than our insertion item, right?

248
00:18:06,580 --> 00:18:11,530
So all you got to do now is, of course, print it out to verify that it works.

249
00:18:11,540 --> 00:18:16,780
So I'm going to say that it was zero, just kind of have the same loop again.

250
00:18:16,810 --> 00:18:27,460
I have less than five plus plus and I'll go into here and I'm just going to say, see out my vet I and

251
00:18:27,460 --> 00:18:29,170
then I'll put some spaces here.

252
00:18:30,550 --> 00:18:33,370
And then, of course, I think I'll do a little end line here.

253
00:18:34,810 --> 00:18:35,200
All right.

254
00:18:35,210 --> 00:18:42,280
So this is just say like print out the whole piece or the vector.

255
00:18:43,060 --> 00:18:44,770
And yeah, this is our insertion.

256
00:18:44,770 --> 00:18:46,900
So let's just label some of this stuff.

257
00:18:46,900 --> 00:18:57,610
So they sent me an item to be inserted into some sort in an area.

258
00:18:59,740 --> 00:19:01,270
This is just,

259
00:19:04,360 --> 00:19:13,470
let's say that the right most edition of sorted area.

260
00:19:14,620 --> 00:19:17,170
And then here is us doing our loop.

261
00:19:17,230 --> 00:19:22,600
So this is like our walking loop.

262
00:19:23,860 --> 00:19:30,310
And then we, of course, do the swap.

263
00:19:30,700 --> 00:19:46,840
And then let's just say this is move our process in one two to the left and inside story area.

264
00:19:48,280 --> 00:19:50,590
So you some comments that kind of can explain it better.

265
00:19:51,480 --> 00:19:51,750
Right.

266
00:19:51,750 --> 00:19:53,950
So the outer loop this is this is just an assertion.

267
00:19:53,950 --> 00:19:54,820
So it starts here.

268
00:19:55,120 --> 00:19:59,710
Set the item to be inserted into the sorted area, set the right mouse position of the storage area.

269
00:19:59,710 --> 00:20:01,360
So that's the right mouse green box.

270
00:20:02,230 --> 00:20:05,710
Now we go into this swapping loop where we're going to move through our sorted area.

271
00:20:05,710 --> 00:20:08,250
So here's the actual swap these three lines here.

272
00:20:08,770 --> 00:20:13,060
And then this is just to move one position to the left inside that green sort of area.

273
00:20:13,060 --> 00:20:16,690
And then we go back up here and check the conditions and continue if we need to.

274
00:20:17,230 --> 00:20:19,360
And then now we're turning out that whole thing.

275
00:20:20,490 --> 00:20:25,950
So let's go ahead and compile this, and I say so sorry, I'm saying, Paul, this idea out.

276
00:20:27,290 --> 00:20:33,410
Uh, my sordid position was not declared in this, I just spelled that wrong.

277
00:20:33,620 --> 00:20:37,010
I forgot to put the I, so go ahead and fix that.

278
00:20:37,790 --> 00:20:38,750
Sorry about that.

279
00:20:38,990 --> 00:20:41,840
So it's like here it was a.

280
00:20:44,010 --> 00:20:46,330
Misspell air, hopefully you don't have any more.

281
00:20:46,360 --> 00:20:48,810
OK, that looks good, so let's go ahead and run this.

282
00:20:49,350 --> 00:20:51,600
So interior, no, let's just say.

283
00:20:51,690 --> 00:20:55,650
Or nine one three six.

284
00:20:56,550 --> 00:20:58,890
And then we go one three four six nine.

285
00:20:58,900 --> 00:21:00,400
That looks to be in Soviet order.

286
00:21:00,420 --> 00:21:04,560
Let's go ahead and try a bigger example, just like we did before with bubble sauce.

287
00:21:04,560 --> 00:21:12,150
So I'll go ahead and increase this to like 10, and then I'll go down here and increase this to 10.

288
00:21:15,600 --> 00:21:20,910
So let's go ahead and compile that and run this, so.

289
00:21:31,800 --> 00:21:32,220
All right.

290
00:21:32,400 --> 00:21:38,760
So let's see, one two, three five, seven, eight, nine, 11, 22, 44, it looks like that is in

291
00:21:38,760 --> 00:21:40,320
good, solid order as well.

292
00:21:41,940 --> 00:21:45,720
OK, so that's pretty much all I have to go over with insertion sort.

293
00:21:46,230 --> 00:21:52,800
Like I said, the reason that I introduced this was just to kind of give you another example of sorting

294
00:21:52,800 --> 00:22:00,240
and the like show you that there are multiple ways that you can solve the same problem, and that's

295
00:22:00,240 --> 00:22:02,430
going to be a really important thing as we move forward.

296
00:22:02,760 --> 00:22:06,330
You know, everyone might be coming up with their unique solution.

297
00:22:06,330 --> 00:22:11,010
And then eventually, when we get into the algorithms portion of the course, we're going to look at

298
00:22:11,010 --> 00:22:15,900
not only just coming up with a way to solve the problem, our own way of solving the problem.

299
00:22:15,900 --> 00:22:19,410
But we're going to compare different ways to solve the problem, to make sure that we can do it in the

300
00:22:19,410 --> 00:22:20,730
most efficient manner.

301
00:22:20,760 --> 00:22:21,090
Right.

302
00:22:21,360 --> 00:22:26,250
We're going to look at not only solving the problem, but kind of optimizing it, making it more efficient.

303
00:22:28,570 --> 00:22:28,980
All right.

304
00:22:29,020 --> 00:22:32,020
So with that, I will see you in the next lecture.