1
00:00:00,670 --> 00:00:03,160
Hi everyone, let's do this question.

2
00:00:03,160 --> 00:00:05,440
You are given an array of integers.

3
00:00:05,440 --> 00:00:12,160
Write a function that will take this array as input and return the sorted array using insertion sort.

4
00:00:12,160 --> 00:00:14,500
So this question is about insertion sort.

5
00:00:14,500 --> 00:00:16,720
So we will be given an array of integers.

6
00:00:16,720 --> 00:00:19,810
And we have to just return the sorted array.

7
00:00:19,810 --> 00:00:23,050
But the caveat is that we have to use insertion sort.

8
00:00:23,050 --> 00:00:26,620
So let's go ahead and try to learn insertion sort in this video.

9
00:00:26,620 --> 00:00:33,730
Now the insertion sort works on the principle of dividing the array which is given to us into two parts.

10
00:00:33,730 --> 00:00:39,880
Now the two parts, one part of the two parts, one part is going to be sorted and the other part is

11
00:00:39,880 --> 00:00:40,810
not sorted.

12
00:00:40,810 --> 00:00:47,560
And then we will just pick one element at a time from the non sorted part and insert it into its correct

13
00:00:47,560 --> 00:00:49,390
position in the sorted part.

14
00:00:49,390 --> 00:00:52,570
So this is how the insertion sort works at a high level.

15
00:00:52,570 --> 00:00:54,160
Now let's try to understand this.

16
00:00:54,160 --> 00:00:56,500
So again what is the sorted part.

17
00:00:56,500 --> 00:00:59,350
Let's say the array is 432 and one.

18
00:00:59,350 --> 00:01:01,750
Now we are going to split the array into two parts.

19
00:01:01,750 --> 00:01:03,430
And this is going to be one part.

20
00:01:03,430 --> 00:01:04,870
And this is the other part.

21
00:01:04,900 --> 00:01:08,530
Now if we have only one element then this is sorted right.

22
00:01:08,530 --> 00:01:09,790
Because it's just one element.

23
00:01:10,030 --> 00:01:12,010
That's why this part is going to be sorted.

24
00:01:12,010 --> 00:01:16,270
And this is the unsorted part because we don't know whether this is sorted or not.

25
00:01:16,270 --> 00:01:22,240
And then we are going to pick one element at a time and insert it into the sorted part and expand the

26
00:01:22,240 --> 00:01:22,870
sorted part.

27
00:01:22,870 --> 00:01:25,060
So this is how the insertion sort works.

28
00:01:25,060 --> 00:01:30,070
Now let's try to take an example and walk through it so that we can understand this thoroughly.

29
00:01:31,000 --> 00:01:34,240
So I have an array over here 73851.

30
00:01:34,240 --> 00:01:38,200
Now this part is going to be the sorted part which has just one element.

31
00:01:38,200 --> 00:01:40,360
And this is the not sorted part.

32
00:01:40,810 --> 00:01:41,260
All right.

33
00:01:41,260 --> 00:01:43,090
Now let's keep this aside.

34
00:01:43,810 --> 00:01:46,720
Now this is the array with which we are dealing with.

35
00:01:46,720 --> 00:01:47,170
Now.

36
00:01:47,170 --> 00:01:52,300
We are going to have a pointer to iterate through the array which is given to us.

37
00:01:52,300 --> 00:01:54,910
But we know that this part is already sorted.

38
00:01:54,910 --> 00:01:57,880
So we are going to start over here which is at index one.

39
00:01:57,880 --> 00:01:59,950
So I is let I is equal to one.

40
00:01:59,950 --> 00:02:01,570
So I is starting at index one.

41
00:02:01,570 --> 00:02:03,790
Now the value over here is three.

42
00:02:03,790 --> 00:02:07,750
So we are going to take out this value and store it in a temporary variable.

43
00:02:07,750 --> 00:02:10,750
Now we are going to have one more variable let's call it j.

44
00:02:10,780 --> 00:02:14,920
Now j is going to be equal to I minus one which is the previous element over here.

45
00:02:15,040 --> 00:02:17,650
So j is over here at index zero.

46
00:02:17,740 --> 00:02:22,990
Now we are going to check is the element in the given array at index j.

47
00:02:22,990 --> 00:02:26,230
Is it greater than the temp value which is three.

48
00:02:26,230 --> 00:02:29,500
So is array at j greater than temp or three.

49
00:02:29,530 --> 00:02:31,630
Now in this case we have seven over here.

50
00:02:31,630 --> 00:02:34,480
And yes seven is actually greater than three.

51
00:02:34,480 --> 00:02:36,790
So again what what is it that we are trying to do.

52
00:02:36,790 --> 00:02:41,500
We are trying to insert three into the sorted part which is just seven at this point.

53
00:02:41,500 --> 00:02:45,070
Now we have seen that the seven is greater than three.

54
00:02:45,070 --> 00:02:46,660
So we cannot leave it like this.

55
00:02:46,660 --> 00:02:46,900
Right.

56
00:02:46,900 --> 00:02:48,040
So seven comma three.

57
00:02:48,040 --> 00:02:49,060
The order would be wrong.

58
00:02:49,060 --> 00:02:50,020
So what do we do.

59
00:02:50,020 --> 00:02:52,420
We are going to shift this seven to the right.

60
00:02:52,420 --> 00:02:54,580
So we're going to shift this to the right.

61
00:02:54,580 --> 00:02:56,170
And we have seven over here.

62
00:02:56,170 --> 00:02:58,480
Now it looks like seven comma seven.

63
00:02:58,480 --> 00:03:00,730
And then J is going to be decremented.

64
00:03:00,730 --> 00:03:02,890
So j becomes minus one.

65
00:03:04,170 --> 00:03:11,670
Now because J is not greater than zero any longer, we know that we have nothing over here, and therefore

66
00:03:11,670 --> 00:03:17,550
we are going to insert this temp value at r I at j plus one and minus one plus one is zero.

67
00:03:17,550 --> 00:03:21,750
So therefore we are going to insert three at index zero which is over here.

68
00:03:21,750 --> 00:03:23,400
And we get three over here.

69
00:03:23,640 --> 00:03:27,450
So now you can see that the sorted part is three comma seven.

70
00:03:27,450 --> 00:03:30,780
And the unsorted part is eight comma five comma one.

71
00:03:30,780 --> 00:03:34,500
And you can see that the sorted part has increased in length.

72
00:03:34,500 --> 00:03:36,450
So what did what did we actually do.

73
00:03:36,450 --> 00:03:42,600
We took this one element and we inserted it in the correct position in the sorted part of the array.

74
00:03:42,600 --> 00:03:44,910
So this is how the insertion sort works.

75
00:03:44,910 --> 00:03:46,980
So let's make some space over here.

76
00:03:47,250 --> 00:03:49,020
Now let's proceed.

77
00:03:49,020 --> 00:03:50,970
Now initially I was over here right.

78
00:03:50,970 --> 00:03:53,010
So again now I is going to be over here.

79
00:03:53,010 --> 00:03:54,630
And remember this is now sorted.

80
00:03:54,630 --> 00:03:57,810
So this is the sorted part and this is the unsorted part.

81
00:03:57,810 --> 00:04:00,420
So I is going to increment from 1 to 2.

82
00:04:00,450 --> 00:04:04,140
That is I is going to point at the beginning of the unsorted part.

83
00:04:04,170 --> 00:04:05,940
Now we take this value eight.

84
00:04:05,940 --> 00:04:08,070
And we are going to store it in a temp value.

85
00:04:08,070 --> 00:04:12,180
And we have to decide where to insert this eight in the sorted part.

86
00:04:12,210 --> 00:04:16,710
Now J is going to be the other pointer and j is going to be equal to I minus one.

87
00:04:16,710 --> 00:04:18,780
So j is going to be equal to one okay.

88
00:04:18,780 --> 00:04:20,670
So it's going to point at index one.

89
00:04:20,670 --> 00:04:23,760
Now we are going to check is the value at index j.

90
00:04:23,760 --> 00:04:28,140
Is it greater than the temp value or is seven greater than eight.

91
00:04:28,910 --> 00:04:30,410
That's not the case, right?

92
00:04:30,590 --> 00:04:32,150
Seven is not greater than eight.

93
00:04:32,150 --> 00:04:37,970
So we can understand that already this element is at its right position.

94
00:04:37,970 --> 00:04:42,740
We don't need to keep checking towards its left, because we know that this part is already sorted.

95
00:04:42,740 --> 00:04:48,230
And because this value eight is greater than seven, or because seven is not greater than eight, so

96
00:04:48,230 --> 00:04:52,010
eight is already at its correct position and we can leave it as it is.

97
00:04:52,010 --> 00:04:54,950
Now we see that the sorted part has again increased.

98
00:04:54,950 --> 00:04:59,450
Now three, seven and eight are sorted and five and one are not sorted.

99
00:04:59,750 --> 00:05:01,100
So let's make some space.

100
00:05:01,100 --> 00:05:02,690
We again increment I.

101
00:05:02,720 --> 00:05:08,030
So I is going to point at index three and j is going to point at index two.

102
00:05:08,060 --> 00:05:08,270
Okay.

103
00:05:08,270 --> 00:05:09,950
So this is two and this is three.

104
00:05:09,980 --> 00:05:13,280
Now this value over here will be stored in our temp variable.

105
00:05:13,280 --> 00:05:19,310
And again we will check is the value at index j greater than the temp value or is eight greater than

106
00:05:19,310 --> 00:05:19,820
five.

107
00:05:19,820 --> 00:05:21,620
Yes eight is greater than five.

108
00:05:21,620 --> 00:05:24,050
So we cannot leave it like this right.

109
00:05:24,050 --> 00:05:26,450
So we're going to shift eight towards the right.

110
00:05:26,450 --> 00:05:28,520
So we're going to move it towards the right.

111
00:05:28,520 --> 00:05:34,400
And we say j at J plus one which is this over here is going to be equal to array j.

112
00:05:34,400 --> 00:05:36,200
So we get eight also over here.

113
00:05:36,200 --> 00:05:38,120
And then we are going to decrement j.

114
00:05:38,120 --> 00:05:39,830
So j comes over here.

115
00:05:40,610 --> 00:05:47,810
And again we're going to check is the value in the array at index j greater than temp or is seven greater

116
00:05:47,810 --> 00:05:48,470
than five.

117
00:05:48,470 --> 00:05:52,130
We see that's yes that's the case seven is greater than five.

118
00:05:52,130 --> 00:05:57,590
Therefore we cannot insert the element which we are looking at which is five over here.

119
00:05:57,590 --> 00:05:57,740
Right.

120
00:05:57,740 --> 00:06:02,360
We cannot insert it over here because this is greater than seven is greater than five.

121
00:06:02,360 --> 00:06:04,490
So we cannot it cannot insert five over here.

122
00:06:04,490 --> 00:06:06,680
So we're going to move seven to the right.

123
00:06:06,680 --> 00:06:07,100
All right.

124
00:06:07,100 --> 00:06:12,650
So we are going to say array at j plus one is equal to array at j or over here we are going to overwrite

125
00:06:12,650 --> 00:06:13,490
it with seven.

126
00:06:13,490 --> 00:06:15,290
And then we are going to decrement j.

127
00:06:15,290 --> 00:06:16,550
So j comes over here.

128
00:06:17,210 --> 00:06:21,170
And again we are going to check is the value at index j greater than five.

129
00:06:21,170 --> 00:06:23,000
So is three greater than five.

130
00:06:23,000 --> 00:06:24,650
No that's not the case right.

131
00:06:24,650 --> 00:06:27,590
So we no longer need to move three to the right.

132
00:06:27,590 --> 00:06:30,260
But we can insert the five over here.

133
00:06:30,260 --> 00:06:32,660
We can insert it over here at this position.

134
00:06:32,660 --> 00:06:37,190
And again so for this we will just say array at j plus one is equal to five.

135
00:06:37,190 --> 00:06:38,540
And seven is already over here.

136
00:06:38,540 --> 00:06:38,780
Right.

137
00:06:38,780 --> 00:06:40,610
So we are not losing any value.

138
00:06:40,610 --> 00:06:41,000
Right.

139
00:06:41,000 --> 00:06:46,070
So over here we were either to move three to this place or we were to insert five over here.

140
00:06:46,070 --> 00:06:51,650
Now at this point we can insert five over here because we have seen that three is not greater than five.

141
00:06:51,650 --> 00:06:53,180
So we get five over here.

142
00:06:53,180 --> 00:06:55,010
And then our array looks like this.

143
00:06:55,010 --> 00:06:58,310
Now we have 3578 and one.

144
00:06:58,310 --> 00:06:59,600
And this is the sorted part.

145
00:06:59,600 --> 00:07:03,860
And we just have one element over over here in the unsorted part.

146
00:07:03,890 --> 00:07:06,020
Now I is going to point at that element.

147
00:07:06,020 --> 00:07:08,780
And then j is going to point at the previous element.

148
00:07:09,440 --> 00:07:14,690
And again we're going to check is the element at index j greater than the temp value.

149
00:07:14,720 --> 00:07:16,550
Yes eight is greater than one.

150
00:07:17,120 --> 00:07:19,820
Therefore we are going to move eight to the right.

151
00:07:19,820 --> 00:07:20,120
All right.

152
00:07:20,120 --> 00:07:20,720
So let's do that.

153
00:07:20,720 --> 00:07:26,960
So we get eight over here and we decrement j again we are going to check is seven greater than one.

154
00:07:26,960 --> 00:07:27,440
We see.

155
00:07:27,440 --> 00:07:28,580
Yes that's the case.

156
00:07:28,580 --> 00:07:32,600
Therefore we move seven to the right and we decrement j by one.

157
00:07:32,600 --> 00:07:37,010
So we get j over here again we're going to check is five greater than one.

158
00:07:37,010 --> 00:07:38,510
Yes that's the case.

159
00:07:38,510 --> 00:07:40,850
Therefore we're going to move five to the right.

160
00:07:40,850 --> 00:07:42,740
And we decrement j by one.

161
00:07:42,740 --> 00:07:45,050
Again we are checking is three greater than one.

162
00:07:45,050 --> 00:07:46,370
Yes that's the case.

163
00:07:46,370 --> 00:07:50,720
So we move three to the right and we decrement j by one.

164
00:07:50,720 --> 00:07:52,760
And now j becomes minus one.

165
00:07:52,760 --> 00:07:55,610
So j is no longer greater than equal to zero.

166
00:07:55,610 --> 00:08:00,320
Therefore we know that we can just insert the element at j plus one.

167
00:08:00,320 --> 00:08:03,410
So that's minus one plus one which is index zero.

168
00:08:03,410 --> 00:08:07,070
So at index zero we're going to insert the temp value which is one.

169
00:08:07,070 --> 00:08:08,450
So we get one over here.

170
00:08:08,450 --> 00:08:11,150
And you can see that our array is now sorted.

171
00:08:11,150 --> 00:08:13,730
We have 1357 and eight.

172
00:08:13,730 --> 00:08:16,130
So this is how the insertion sort works.

173
00:08:16,130 --> 00:08:19,310
Now what about the complexity analysis of this solution.

174
00:08:19,310 --> 00:08:20,540
Let's take a look at it.

175
00:08:21,580 --> 00:08:26,050
Now let's say the array which is given to us is one, two, three, four.

176
00:08:26,080 --> 00:08:32,110
This is the best case scenario for the insertion sort, because initially I is going to point at index

177
00:08:32,110 --> 00:08:33,400
one right over here.

178
00:08:33,400 --> 00:08:35,320
And we will just make one comparison.

179
00:08:35,320 --> 00:08:37,630
And we will see that it's in the correct position.

180
00:08:37,630 --> 00:08:40,030
Then I is going to move to index two.

181
00:08:40,060 --> 00:08:43,630
We will make one comparison and we see that it's in the correct position.

182
00:08:43,630 --> 00:08:45,910
And again we move I to index three.

183
00:08:45,940 --> 00:08:49,060
We will make one comparison and we will see that it's at the correct position.

184
00:08:49,060 --> 00:08:53,890
So we only have to do n operations or n minus one operations to be exact.

185
00:08:53,890 --> 00:08:55,390
So n minus one operations.

186
00:08:55,390 --> 00:09:00,910
So we can say that the time complexity in the best case is of the order of n because this is just a

187
00:09:00,910 --> 00:09:01,330
constant.

188
00:09:01,330 --> 00:09:02,320
So we avoid this.

189
00:09:02,320 --> 00:09:07,030
Now in the worst case let's say the array looks like this 432 and one.

190
00:09:07,030 --> 00:09:09,490
So I initially would be at index one.

191
00:09:09,490 --> 00:09:11,530
And we would have to make one comparison.

192
00:09:11,530 --> 00:09:12,040
All right.

193
00:09:12,040 --> 00:09:15,130
And this changes to 342 and one.

194
00:09:15,130 --> 00:09:19,210
And then I would be at index two right which is over here.

195
00:09:19,210 --> 00:09:21,190
And then we would have to make two comparisons.

196
00:09:21,190 --> 00:09:21,370
Right.

197
00:09:21,370 --> 00:09:23,680
Because we'll have to get two over here.

198
00:09:23,680 --> 00:09:25,480
So it would be 2341.

199
00:09:25,480 --> 00:09:28,600
And then I is going to be over here at index three.

200
00:09:28,600 --> 00:09:30,670
And then we'll have to do three comparisons.

201
00:09:30,670 --> 00:09:30,940
Right.

202
00:09:30,940 --> 00:09:32,320
So this is the worst case.

203
00:09:32,320 --> 00:09:35,410
So over here three note is that we have four elements.

204
00:09:35,410 --> 00:09:38,170
That's why we stopped over here with three comparisons.

205
00:09:38,170 --> 00:09:41,710
So three over here is actually n minus one.

206
00:09:41,980 --> 00:09:48,820
So the total number of operations that we have to do is one plus two plus etc. up to n minus one.

207
00:09:49,470 --> 00:09:56,160
Now we know that one plus two plus three, etc. up to n is equal to n into n plus one divided by two.

208
00:09:56,190 --> 00:09:59,220
Now over here we just have to add till n minus one.

209
00:09:59,220 --> 00:10:02,370
So instead of n we can write n minus one over here.

210
00:10:02,370 --> 00:10:06,330
So we just have to change this n to n minus one and this to n minus one.

211
00:10:06,330 --> 00:10:12,570
So this over here sums up to n minus one into n minus one plus one by two which is equal to n minus

212
00:10:12,570 --> 00:10:13,890
one into n by two.

213
00:10:13,890 --> 00:10:17,820
And if you expand this you will get n square minus n by two.

214
00:10:17,850 --> 00:10:20,640
So you can see that there is an n square term.

215
00:10:20,640 --> 00:10:26,730
So that's why the time complexity, the worst time complexity is going to be of the order of n square.

216
00:10:27,460 --> 00:10:32,860
Now we have seen that the best case is O of N, and the worst case is O of n square.

217
00:10:32,860 --> 00:10:38,710
And the average case of the time complexity for the insertion sort is also going to be of the order

218
00:10:38,710 --> 00:10:39,790
of n square.

219
00:10:39,820 --> 00:10:42,250
Now what about the space complexity?

220
00:10:42,250 --> 00:10:47,500
The space complexity of this solution is O of one because we are not using any extra space.