1
00:00:00,600 --> 00:00:01,590
Welcome back.

2
00:00:01,590 --> 00:00:06,960
Let's now go ahead and write the function to implement the insertion sort, which we discussed in the

3
00:00:06,960 --> 00:00:08,070
previous video.

4
00:00:08,070 --> 00:00:10,890
And we will call this function insertion sort.

5
00:00:10,950 --> 00:00:13,980
Now this function is going to take in an array.

6
00:00:15,170 --> 00:00:17,330
And that's the array that we need to sort.

7
00:00:17,360 --> 00:00:20,930
Now remember how this works is that we're splitting the array into two parts.

8
00:00:20,930 --> 00:00:26,540
For example, if the array which is given to us is four, three, two and one, then we are going to

9
00:00:26,540 --> 00:00:29,330
consider this over here as the sorted part.

10
00:00:29,330 --> 00:00:31,640
And then this is the not sorted part.

11
00:00:31,640 --> 00:00:37,640
And then we are going to pick one element at a time from the not sorted part, and then insert it at

12
00:00:37,640 --> 00:00:41,840
the correct position into the sorted part and expand the sorted part.

13
00:00:41,840 --> 00:00:43,070
So that is how this proceeds.

14
00:00:43,070 --> 00:00:48,290
So you can see that the not sorted part starts at index one, which is this index over here.

15
00:00:48,290 --> 00:00:50,300
So that is why we are going to have a for loop.

16
00:00:50,300 --> 00:00:53,870
And in the for loop we are going to start at index one.

17
00:00:53,870 --> 00:00:59,660
So for let I is equal to one I less than array dot length.

18
00:01:01,050 --> 00:01:02,190
I plus, plus.

19
00:01:05,650 --> 00:01:06,070
All right.

20
00:01:06,070 --> 00:01:11,080
Now, inside the for loop we have seen that we'll have another variable j.

21
00:01:11,080 --> 00:01:13,870
So j is going to be equal to I minus one.

22
00:01:13,870 --> 00:01:17,110
So j is going to start at the index before I.

23
00:01:17,140 --> 00:01:20,470
So j let j is equal to I minus one.

24
00:01:21,780 --> 00:01:24,150
And let's also have a temporary variable.

25
00:01:24,150 --> 00:01:27,090
Let temp is equal to array at I.

26
00:01:27,120 --> 00:01:30,870
So we are using this to store the value in the array at the ith index.

27
00:01:30,870 --> 00:01:35,760
Now again let's just try to take an example and walk through this over here so that we can understand

28
00:01:35,760 --> 00:01:36,540
what's happening.

29
00:01:36,540 --> 00:01:40,980
So let's say the array is 3578 and one.

30
00:01:40,980 --> 00:01:44,010
And let's say we have done already some sorting operations.

31
00:01:44,010 --> 00:01:46,050
And now I is over here.

32
00:01:46,050 --> 00:01:46,290
All right.

33
00:01:46,290 --> 00:01:49,680
So I'm taking this example I over here to make it more clear.

34
00:01:49,680 --> 00:01:51,690
So this is 01234.

35
00:01:51,690 --> 00:01:53,250
So let's say I is equal to four.

36
00:01:53,250 --> 00:01:53,730
All right.

37
00:01:53,730 --> 00:01:59,610
And then we want to insert this element over here in the correct position of this part.

38
00:01:59,610 --> 00:02:01,320
So this part is the sorted part.

39
00:02:01,320 --> 00:02:06,540
Again I'm repeating we are considering the case where the array was looking something different in the

40
00:02:06,540 --> 00:02:07,020
beginning.

41
00:02:07,020 --> 00:02:08,820
And we already sorted right.

42
00:02:08,820 --> 00:02:12,960
For example we will start with I over here and then we move over here.

43
00:02:12,960 --> 00:02:15,570
Then we move over here and then I will finally be over here.

44
00:02:15,570 --> 00:02:20,070
So we are just taking that instance, that snapshot to understand what's happening over here.

45
00:02:20,610 --> 00:02:23,100
So J is going to be equal to I minus one.

46
00:02:23,100 --> 00:02:25,860
So J is going to point to this index over here.

47
00:02:25,860 --> 00:02:29,700
And then we are going to check whether whatever is over here right.

48
00:02:29,700 --> 00:02:32,730
Whether whatever is over here is greater than this value.

49
00:02:32,730 --> 00:02:33,960
So that is what we want to check.

50
00:02:33,960 --> 00:02:37,470
So again that's why J is going to be I minus one which is this index.

51
00:02:37,470 --> 00:02:42,600
And then this is going to happen as long as j is greater than zero because this is over here.

52
00:02:42,600 --> 00:02:42,870
Right.

53
00:02:42,870 --> 00:02:44,100
Greater than equal to zero.

54
00:02:44,100 --> 00:02:46,170
So we are going to have a while loop for this.

55
00:02:46,170 --> 00:02:48,390
So let's go ahead and write that over here.

56
00:02:51,070 --> 00:02:51,760
All right.

57
00:02:52,360 --> 00:02:54,310
So we can say while.

58
00:02:55,760 --> 00:02:58,400
J greater than or equal to zero.

59
00:02:58,400 --> 00:03:00,440
And then there is one more condition, right.

60
00:03:00,440 --> 00:03:03,860
We need to keep checking only as long as our A at J.

61
00:03:05,500 --> 00:03:07,030
Is greater than temp.

62
00:03:10,150 --> 00:03:10,990
Now why is that?

63
00:03:10,990 --> 00:03:13,870
So if we see that the previous element is not greater.

64
00:03:13,870 --> 00:03:16,480
For example, let's take an example to understand this.

65
00:03:16,480 --> 00:03:23,350
Also, let's say the array is five seven and let's say over here we have eight.

66
00:03:23,350 --> 00:03:25,240
And let's say I is over here.

67
00:03:25,240 --> 00:03:25,660
All right.

68
00:03:25,690 --> 00:03:27,340
Now this is the sorted part.

69
00:03:27,340 --> 00:03:30,160
So because I is over here this is the not sorted part.

70
00:03:30,160 --> 00:03:34,510
Now we are trying to insert this in the correct place in the sorted part of the array.

71
00:03:34,510 --> 00:03:38,770
Now we are seeing that let's say array at J which is what we have over here.

72
00:03:38,770 --> 00:03:42,160
We see that it is not greater than this value which is there in temp.

73
00:03:42,160 --> 00:03:42,550
Right.

74
00:03:42,550 --> 00:03:47,530
In that case, these this is already sorted because we know this part is anyway sorted.

75
00:03:47,530 --> 00:03:47,800
Right.

76
00:03:47,800 --> 00:03:49,360
So we don't need to keep checking.

77
00:03:49,360 --> 00:03:55,060
So that's why we can stop when array at j is no longer greater than temp we can stop.

78
00:03:55,060 --> 00:03:57,220
So that's why this is the condition.

79
00:04:00,350 --> 00:04:02,150
Now, once inside the while loop.

80
00:04:02,150 --> 00:04:02,960
Let's continue.

81
00:04:02,990 --> 00:04:04,580
What is it that we have to do?

82
00:04:04,580 --> 00:04:08,510
So J is greater than or equal to zero and array at j is greater than temp.

83
00:04:08,510 --> 00:04:14,600
So in that case we are going to shift the value of array at j and put it to array at j plus one.

84
00:04:14,600 --> 00:04:17,660
So we're going to say array at j plus one.

85
00:04:19,960 --> 00:04:21,730
Is equal to r8 j.

86
00:04:23,650 --> 00:04:25,690
And then we're just going to decrement j.

87
00:04:25,690 --> 00:04:26,890
So j minus minus.

88
00:04:26,890 --> 00:04:28,450
And this keeps happening.

89
00:04:28,450 --> 00:04:31,030
Now we will come out of the while loop in two ways.

90
00:04:31,030 --> 00:04:34,030
Either j is no longer greater than or equal to zero.

91
00:04:34,030 --> 00:04:36,010
In that case we have to insert.

92
00:04:36,010 --> 00:04:37,360
So j will be minus one right.

93
00:04:37,360 --> 00:04:42,280
So in that case we have to insert the value the temp value at the zeroth index.

94
00:04:42,280 --> 00:04:44,950
So we can say array at j plus one.

95
00:04:45,920 --> 00:04:47,720
It is minus one plus one, which is zero.

96
00:04:47,720 --> 00:04:50,570
So j plus one is equal to temp.

97
00:04:50,690 --> 00:04:56,870
Now the other possibility why we came out of the y loop is that r I j is not greater than temp in that

98
00:04:56,870 --> 00:04:57,170
case.

99
00:04:57,170 --> 00:05:01,130
Also we just want to insert temp to arrive at j plus one right.

100
00:05:01,130 --> 00:05:02,360
So let's try to understand this.

101
00:05:02,360 --> 00:05:05,660
We'll take in we'll take an example and walk through this to understand this.

102
00:05:05,660 --> 00:05:07,430
Well now that's it.

103
00:05:07,430 --> 00:05:09,800
So once this is done we just have to return the array.

104
00:05:09,800 --> 00:05:10,610
And it is done.

105
00:05:12,630 --> 00:05:17,070
Now let's just test this and then we will take a sample input and walk through the code.

106
00:05:17,250 --> 00:05:18,720
So let's call the function.

107
00:05:19,850 --> 00:05:24,200
And let's say the array is four, three, two and one.

108
00:05:25,900 --> 00:05:27,460
And we're calling the function.

109
00:05:28,410 --> 00:05:30,600
And yes, you can see we're getting one, two, three, four.

110
00:05:30,630 --> 00:05:31,890
That is it sorted.

111
00:05:31,890 --> 00:05:35,670
Now let's take this example and try to understand what's happening over here.

112
00:05:35,670 --> 00:05:38,490
So initially the array is 4321.

113
00:05:38,490 --> 00:05:39,720
So let's write it over here.

114
00:05:41,520 --> 00:05:45,630
And we come over here, I is going to point at index one.

115
00:05:45,630 --> 00:05:46,380
This is one.

116
00:05:47,270 --> 00:05:47,780
This is two.

117
00:05:47,810 --> 00:05:48,650
This is three.

118
00:05:48,680 --> 00:05:49,400
This is zero.

119
00:05:49,400 --> 00:05:50,720
So I is equal to one.

120
00:05:50,720 --> 00:05:53,690
J is going to be equal to I minus one which is zero.

121
00:05:54,660 --> 00:05:59,130
So Jay is pointing to zero and then temp is going to be array at I which is this value.

122
00:05:59,130 --> 00:06:00,810
So this value is stored in temp.

123
00:06:00,810 --> 00:06:04,590
And then we see that j is greater than or equal to zero and array at j.

124
00:06:04,590 --> 00:06:07,470
Which is what we have over here is greater than temp.

125
00:06:07,470 --> 00:06:09,450
So yes we come inside the while loop.

126
00:06:09,450 --> 00:06:13,290
And then we are going to say array at j plus one is equal to array at j.

127
00:06:13,290 --> 00:06:14,310
So this is j.

128
00:06:14,310 --> 00:06:16,350
So j plus one is what we have over here.

129
00:06:16,350 --> 00:06:18,900
This is going to be array at j which is four.

130
00:06:18,900 --> 00:06:21,180
So basically we are shifting the value over here.

131
00:06:21,180 --> 00:06:23,220
And this is going to change to four.

132
00:06:23,220 --> 00:06:25,860
Now it's looking like 442 and one.

133
00:06:25,860 --> 00:06:27,210
And j is decremented.

134
00:06:27,210 --> 00:06:28,650
So j becomes minus one.

135
00:06:28,650 --> 00:06:31,620
And when we come and check over here is j greater than equal to zero.

136
00:06:31,620 --> 00:06:32,880
No that's not the case.

137
00:06:32,880 --> 00:06:36,030
So we are out of the while loop and then array at j plus one.

138
00:06:36,030 --> 00:06:37,470
That's minus one plus one.

139
00:06:37,470 --> 00:06:38,670
This is going to be zero.

140
00:06:38,670 --> 00:06:40,830
So array at zero is going to be temp.

141
00:06:40,830 --> 00:06:43,230
And we had stored the value three in temp.

142
00:06:43,230 --> 00:06:45,330
So we are going to insert three over here.

143
00:06:45,330 --> 00:06:49,710
And now the array looks like this 342 and one.

144
00:06:49,710 --> 00:06:51,780
Now you can see that this part is sorted.

145
00:06:51,780 --> 00:06:53,730
So the sorted part has expanded.

146
00:06:53,730 --> 00:06:56,490
All right so this part is sorted again.

147
00:06:56,490 --> 00:06:58,980
We come over here and I is incremented to two.

148
00:06:59,010 --> 00:06:59,970
So this is two right.

149
00:06:59,970 --> 00:07:00,840
This is index two.

150
00:07:00,870 --> 00:07:02,490
So I is going to point over here.

151
00:07:02,490 --> 00:07:05,490
And J is going to be I minus one which is over here.

152
00:07:05,490 --> 00:07:07,530
So J is going to point at index one.

153
00:07:08,160 --> 00:07:11,790
Now we are going to store the value at rate I, which is this two.

154
00:07:11,820 --> 00:07:13,560
This is going to be stored over here.

155
00:07:14,190 --> 00:07:16,200
Now we enter the while loop.

156
00:07:16,200 --> 00:07:17,490
Is J greater than zero.

157
00:07:17,490 --> 00:07:18,780
Yes j is equal to one.

158
00:07:18,780 --> 00:07:21,330
So that's greater than equal to zero and array at j.

159
00:07:21,390 --> 00:07:22,920
Is it greater than temp.

160
00:07:23,040 --> 00:07:25,620
Over here we have four and four is greater than two.

161
00:07:25,650 --> 00:07:26,970
So yes this is truthy.

162
00:07:26,970 --> 00:07:30,660
So we come inside and then we are checking is array at j.

163
00:07:30,810 --> 00:07:37,050
We are going to assign array at j plus one which is over here is going to be equal to array j.

164
00:07:37,050 --> 00:07:38,730
So we are shifting it in this direction.

165
00:07:38,730 --> 00:07:40,770
So this value is going to be four.

166
00:07:40,770 --> 00:07:42,900
And then we are doing j minus minus.

167
00:07:42,900 --> 00:07:45,360
So j is going to point to index zero now.

168
00:07:46,700 --> 00:07:47,960
So let's just wrap this.

169
00:07:49,490 --> 00:07:52,430
And then again we check is j greater than or equal to zero.

170
00:07:52,430 --> 00:07:52,730
Yes.

171
00:07:52,730 --> 00:07:53,270
This is zero.

172
00:07:53,270 --> 00:07:53,630
Right.

173
00:07:53,630 --> 00:07:55,700
And then is j which is three.

174
00:07:55,700 --> 00:07:57,620
Is it greater than temp which is two.

175
00:07:57,650 --> 00:07:58,700
Yes that's also true.

176
00:07:58,970 --> 00:08:04,160
So we come inside and then we are saying array at J plus one which is zero plus one which is one.

177
00:08:04,160 --> 00:08:05,300
So that's index one.

178
00:08:05,300 --> 00:08:08,840
So this over here is going to be equal to array AJ which is this value.

179
00:08:08,840 --> 00:08:10,610
So we are shifting this in this direction.

180
00:08:10,610 --> 00:08:12,320
So we are getting three over here.

181
00:08:12,320 --> 00:08:13,730
So we'll get three over here.

182
00:08:13,730 --> 00:08:17,090
And then we have three three and four and j is decremented.

183
00:08:17,090 --> 00:08:19,970
So J comes over here which is minus one.

184
00:08:19,970 --> 00:08:23,060
Again when we check is j greater than or equal to zero it's false.

185
00:08:23,060 --> 00:08:26,120
So we come out and then minus one plus one is again zero.

186
00:08:26,120 --> 00:08:27,950
So array at zero is going to be temp.

187
00:08:27,950 --> 00:08:29,780
So this is over here going to be two.

188
00:08:29,810 --> 00:08:33,110
So we get 234 and one.

189
00:08:33,110 --> 00:08:37,160
So you can see that this part is sorted and it's expanded expanding.

190
00:08:37,190 --> 00:08:37,580
All right.

191
00:08:37,580 --> 00:08:41,930
Now again we are going to take our I equal to three.

192
00:08:41,930 --> 00:08:42,950
So 0123.

193
00:08:42,950 --> 00:08:44,330
So this is going to be I.

194
00:08:44,330 --> 00:08:46,130
And then we'll have J over here.

195
00:08:47,370 --> 00:08:49,590
And then what will happen inside the while loop?

196
00:08:49,590 --> 00:08:50,430
We'll just shift, right?

197
00:08:50,430 --> 00:08:51,720
So we'll shift this over here.

198
00:08:51,930 --> 00:08:53,130
This is going to be four.

199
00:08:53,130 --> 00:08:56,910
And then we come over here J is going to point over here again we shifted.

200
00:08:56,910 --> 00:08:58,170
This is going to be three.

201
00:08:58,170 --> 00:08:59,880
And then we shift J over here.

202
00:08:59,880 --> 00:09:02,220
This is going to shift to two right.

203
00:09:02,220 --> 00:09:03,240
Because this is one.

204
00:09:03,240 --> 00:09:04,500
So this is going to be two.

205
00:09:04,500 --> 00:09:07,200
And then J will come over here which is minus one.

206
00:09:07,200 --> 00:09:09,780
So that's why at minus one plus one that's zero.

207
00:09:09,780 --> 00:09:12,300
At the index zero we will insert the temp value.

208
00:09:12,300 --> 00:09:12,990
And that's one.

209
00:09:12,990 --> 00:09:14,790
So that's how we get 1234.

210
00:09:14,790 --> 00:09:17,160
Now let me also take one more other case.

211
00:09:17,160 --> 00:09:22,050
Let's say we are having the array 432 and five.

212
00:09:22,050 --> 00:09:23,820
So let's take that example also.

213
00:09:23,820 --> 00:09:25,290
So let's just clear this up.

214
00:09:26,140 --> 00:09:30,670
So the example is let's have four, three, two and five.

215
00:09:30,700 --> 00:09:31,120
All right.

216
00:09:31,120 --> 00:09:33,550
So let's just walk through the code and see what's happening.

217
00:09:33,550 --> 00:09:34,870
So we are inside the function.

218
00:09:34,870 --> 00:09:36,910
Again I is going to be equal to one.

219
00:09:36,910 --> 00:09:37,810
So this is zero.

220
00:09:37,840 --> 00:09:41,800
This is one this is two this is three J is going to be equal to I minus one.

221
00:09:41,800 --> 00:09:44,140
And then we see that j is greater than or equal to zero.

222
00:09:44,140 --> 00:09:47,500
And I and j which is four is greater than temp which is three.

223
00:09:47,590 --> 00:09:48,970
So three is going to be in temp.

224
00:09:48,970 --> 00:09:50,170
So what are we going to do.

225
00:09:50,170 --> 00:09:51,550
We are going to shift in this direction.

226
00:09:51,550 --> 00:09:54,130
That is array at j plus one is equal to j.

227
00:09:54,130 --> 00:09:55,900
So this is going to be equal to four.

228
00:09:55,900 --> 00:09:57,430
And then j minus minus.

229
00:09:57,430 --> 00:09:58,870
So j becomes minus one.

230
00:09:58,870 --> 00:10:03,670
So we are going to say array at j plus one which is zero is equal to temp which is three.

231
00:10:03,670 --> 00:10:04,840
So we are getting three over here.

232
00:10:04,840 --> 00:10:07,930
So now it looks like this 342 and five.

233
00:10:07,930 --> 00:10:10,030
So the sorted part has increased.

234
00:10:10,030 --> 00:10:12,340
Again I is going to point to two.

235
00:10:12,370 --> 00:10:13,930
J is going to point over here.

236
00:10:13,930 --> 00:10:15,100
And then we shift this.

237
00:10:15,100 --> 00:10:20,500
So we get four over here J comes over here and then we get three over here J comes over here.

238
00:10:20,500 --> 00:10:22,540
And then this two is going to be inserted over here.

239
00:10:22,540 --> 00:10:25,540
So we'll get 234 and five.

240
00:10:25,540 --> 00:10:30,160
Again I is going to point to this index over here which is three.

241
00:10:30,160 --> 00:10:30,670
Right.

242
00:10:30,700 --> 00:10:34,060
So I is going to point to three J is going to point to two.

243
00:10:34,090 --> 00:10:35,590
So this is J this is I.

244
00:10:35,740 --> 00:10:38,290
At this point we will see that j is greater than zero.

245
00:10:38,290 --> 00:10:39,100
So that's true.

246
00:10:39,100 --> 00:10:41,320
But is array at j greater than temp.

247
00:10:41,320 --> 00:10:42,850
So is this greater than temp.

248
00:10:42,850 --> 00:10:44,320
No that's not the case right.

249
00:10:44,320 --> 00:10:45,550
So this is not greater.

250
00:10:45,550 --> 00:10:47,890
So we will just come out of the while loop.

251
00:10:47,890 --> 00:10:50,920
And then over here we'll just say array at J plus one is equal to temp.

252
00:10:50,920 --> 00:10:52,630
So j plus one is five itself.

253
00:10:52,630 --> 00:10:54,970
And five will be replaced with five itself.

254
00:10:54,970 --> 00:10:56,380
So nothing changes.

255
00:10:56,380 --> 00:10:58,360
And then we we we are we are done.

256
00:10:58,360 --> 00:10:58,510
Right.

257
00:10:58,510 --> 00:11:02,620
So we don't need to continue checking over here because we know that this part is sorted.

258
00:11:02,620 --> 00:11:07,450
So if this is greater than this, which is the greatest value in the sorted part, it will be greater

259
00:11:07,450 --> 00:11:08,260
than every value.

260
00:11:08,260 --> 00:11:10,630
So its correct position is over here itself.

261
00:11:10,630 --> 00:11:11,620
And then we stop.

262
00:11:11,620 --> 00:11:14,350
So this is how the insertion sort works.

263
00:11:14,890 --> 00:11:20,260
So basically we are splitting the array into two parts into the sorted part and the unsorted part.

264
00:11:20,260 --> 00:11:23,980
And then we are trying to increase the length of the unsorted part.

265
00:11:24,010 --> 00:11:27,040
Now over here you can see that we have nested loops.

266
00:11:27,040 --> 00:11:28,870
So we have a for loop over here.

267
00:11:28,870 --> 00:11:30,490
And then we have a while loop over here.

268
00:11:30,490 --> 00:11:35,050
So that's an indication why the time complexity is of the order of n square.

269
00:11:35,050 --> 00:11:35,530
Right.

270
00:11:35,770 --> 00:11:39,490
The time complexity of this solution is of the order of n square.

271
00:11:39,490 --> 00:11:41,260
And again we have taken an example also.

272
00:11:41,260 --> 00:11:44,710
For example let's say it's 432 and one.

273
00:11:44,710 --> 00:11:49,420
So initially I is going to point over here and we are going to make one comparison.

274
00:11:49,420 --> 00:11:51,400
Then we will shift it.

275
00:11:51,400 --> 00:11:53,080
So we'll have three over here and four over here.

276
00:11:53,080 --> 00:11:54,640
And I is going to be over here.

277
00:11:54,640 --> 00:11:56,350
Then we will make two comparisons.

278
00:11:56,350 --> 00:11:56,770
Right.

279
00:11:56,770 --> 00:11:58,360
So that's plus two.

280
00:11:58,360 --> 00:12:02,830
And then when I comes over here we'll have two three and four over here.

281
00:12:02,830 --> 00:12:03,730
And one is over here.

282
00:12:03,730 --> 00:12:06,730
And we'll have to make one, two and three comparisons.

283
00:12:06,730 --> 00:12:09,280
So that's how we've seen that mathematically.

284
00:12:09,280 --> 00:12:15,190
Also it's going to be O of N square because it's nothing but one plus two plus three etc. up to n minus

285
00:12:15,190 --> 00:12:15,580
one.

286
00:12:15,580 --> 00:12:21,730
And this sum will have n n square term because this can be simplified to n minus one.

287
00:12:22,610 --> 00:12:24,440
Into n divided by two.

288
00:12:24,440 --> 00:12:27,050
And when we simplify this there will be an n square term.

289
00:12:27,050 --> 00:12:31,070
So that's why the time complexity of this solution is O of n square.

290
00:12:31,070 --> 00:12:37,160
And the space complexity is going to be O of one because we are not using any extra space.

291
00:12:37,160 --> 00:12:38,900
So this runs in constant space.

292
00:12:38,900 --> 00:12:41,750
So the space complexity of this solution is O of one.