1
00:00:01,070 --> 00:00:03,290
Hi everyone, let's do this question.

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

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

4
00:00:12,110 --> 00:00:17,390
So in this question we are going to learn selection sort which is a very famous sort algorithm.

5
00:00:17,390 --> 00:00:20,900
And again it's not very efficient but still let's it's very important to know.

6
00:00:20,900 --> 00:00:22,370
So let's go ahead and learn this.

7
00:00:22,370 --> 00:00:24,770
So we will be given an array of integers.

8
00:00:24,770 --> 00:00:27,110
And we have to return the sorted array.

9
00:00:27,110 --> 00:00:30,110
And the caveat is we have to use the selection sort.

10
00:00:30,140 --> 00:00:33,890
Now let's go ahead and try to understand how we can approach this question.

11
00:00:33,890 --> 00:00:36,260
And let's try to learn the selection sort.

12
00:00:36,260 --> 00:00:39,170
So over here we have the array an array let's say.

13
00:00:39,170 --> 00:00:45,560
And the selection sort works on the principle that in each pass where we iterate through the array which

14
00:00:45,560 --> 00:00:50,870
is given to us, we will identify the smallest number and put it towards the front.

15
00:00:50,870 --> 00:00:53,780
So in the first pass we will identify the smallest one.

16
00:00:53,780 --> 00:00:56,690
And that would be put over here at index zero.

17
00:00:56,690 --> 00:01:02,240
And then among the remaining ones again we will iterate through the array, find the next smallest one

18
00:01:02,240 --> 00:01:03,350
and put it over here.

19
00:01:03,350 --> 00:01:04,730
And so on and so forth.

20
00:01:04,730 --> 00:01:06,740
So this is how this algorithm works.

21
00:01:06,740 --> 00:01:09,830
Now let's try to see how it works and trace the algorithm.

22
00:01:09,830 --> 00:01:11,810
So again we have our array over here.

23
00:01:11,810 --> 00:01:13,940
Now let's write the indices of the given array.

24
00:01:13,940 --> 00:01:16,070
So we have 0 to 5 over here.

25
00:01:16,070 --> 00:01:18,110
Now we will be using two pointers.

26
00:01:18,110 --> 00:01:21,080
So let's say one is I and the other one is J.

27
00:01:21,080 --> 00:01:23,720
Initially I is going to point at index zero.

28
00:01:23,720 --> 00:01:28,160
And we are going to say smallest is equal to this index zero over here.

29
00:01:28,700 --> 00:01:31,910
And J is going to be the second pointer.

30
00:01:31,910 --> 00:01:36,650
And we will say j is equal to I plus one which is the next index which is one over here.

31
00:01:36,650 --> 00:01:38,480
So j is pointing at one.

32
00:01:38,480 --> 00:01:41,300
Now we are going to keep I over here itself.

33
00:01:41,300 --> 00:01:46,880
And then we will move J across the remaining part of the array in this manner.

34
00:01:46,880 --> 00:01:52,820
And keep comparing the value at j and the value at the smallest index.

35
00:01:52,820 --> 00:02:00,140
Now this is going to be modified if we find a value which is smaller than the value currently at this

36
00:02:00,170 --> 00:02:00,530
index.

37
00:02:00,530 --> 00:02:03,230
So let's just walk through the code and we will just understand it.

38
00:02:03,230 --> 00:02:08,390
So at this point at index zero the value is four and j is pointing at index one.

39
00:02:08,390 --> 00:02:09,560
The value is eight.

40
00:02:09,560 --> 00:02:11,780
Now is eight less than four.

41
00:02:11,780 --> 00:02:13,160
No it's not the case right.

42
00:02:13,160 --> 00:02:16,280
So therefore we are just going to move J to the next index.

43
00:02:16,280 --> 00:02:17,870
So we move j forward.

44
00:02:17,870 --> 00:02:19,970
Now j is pointing at index two.

45
00:02:19,970 --> 00:02:22,520
Now is the value over here which is two.

46
00:02:22,550 --> 00:02:24,980
Is it less than the value at index zero.

47
00:02:24,980 --> 00:02:26,060
Which is four.

48
00:02:26,060 --> 00:02:27,290
Is two less than four.

49
00:02:27,290 --> 00:02:27,590
Yes.

50
00:02:27,740 --> 00:02:29,180
Yes two is less than four.

51
00:02:29,210 --> 00:02:34,460
Therefore we are going to modify smallest and we are going to put the index two over here.

52
00:02:34,460 --> 00:02:34,760
All right.

53
00:02:34,760 --> 00:02:36,500
So this is this index over here.

54
00:02:36,500 --> 00:02:39,290
So the index is tracked in the variable smallest.

55
00:02:39,290 --> 00:02:41,300
Again we are going to move j forward.

56
00:02:42,370 --> 00:02:42,760
All right.

57
00:02:42,760 --> 00:02:45,130
Now Jay is pointing at index three.

58
00:02:45,160 --> 00:02:46,840
The value is equal to six.

59
00:02:46,840 --> 00:02:49,390
Now at index smallest which is two.

60
00:02:49,420 --> 00:02:51,790
We have the value two is six less than two.

61
00:02:51,820 --> 00:02:53,170
No it's not the case.

62
00:02:53,170 --> 00:02:54,580
So we don't change this.

63
00:02:54,580 --> 00:02:56,770
And we're going to just move Jay forward.

64
00:02:56,800 --> 00:02:58,990
Now Jay is pointing at index four.

65
00:02:58,990 --> 00:03:00,580
And the value over here is one.

66
00:03:00,580 --> 00:03:02,620
Is one less than this two over here.

67
00:03:02,620 --> 00:03:05,080
Yes it is less than two.

68
00:03:05,110 --> 00:03:09,100
Therefore we are going to modify smallest to four which is this index over here.

69
00:03:09,100 --> 00:03:10,900
So this is modified to four.

70
00:03:10,900 --> 00:03:14,740
And again we move Jay forward and we get the value five over here.

71
00:03:14,740 --> 00:03:17,800
And then we are going to check is five less than one.

72
00:03:17,800 --> 00:03:18,940
No it's not the case.

73
00:03:18,940 --> 00:03:22,540
So you can see we have moved across the remaining part of the array.

74
00:03:22,540 --> 00:03:25,600
We have iterated through the array using the Jay pointer.

75
00:03:25,600 --> 00:03:29,020
And we have found the smallest value which is equal to one.

76
00:03:29,020 --> 00:03:35,530
So now we are just going to swap the value one with the value at index I which is this four.

77
00:03:35,530 --> 00:03:35,980
Over here.

78
00:03:35,980 --> 00:03:40,900
Now you can see effectively what we're doing is we are bringing the smallest value in the array to the

79
00:03:40,900 --> 00:03:41,770
zeroth index.

80
00:03:41,770 --> 00:03:43,570
So let's go ahead and swap these two.

81
00:03:43,600 --> 00:03:46,360
So we get one over here and four over here.

82
00:03:46,360 --> 00:03:48,010
Now our array looks like this.

83
00:03:48,010 --> 00:03:51,820
So we have found the smallest value and we have put it at index zero.

84
00:03:51,820 --> 00:03:54,640
So now we are going to move I ahead.

85
00:03:56,150 --> 00:03:56,450
All right.

86
00:03:56,450 --> 00:03:57,950
So I is now pointing at one.

87
00:03:57,950 --> 00:04:03,200
Now what we are going to do is we are going to iterate through this part of the array, identify the

88
00:04:03,200 --> 00:04:05,660
smallest value, and then put it at index one.

89
00:04:05,660 --> 00:04:06,980
So this is how this proceeds.

90
00:04:06,980 --> 00:04:07,340
All right.

91
00:04:07,340 --> 00:04:09,110
So this is how the selection sort works.

92
00:04:09,110 --> 00:04:12,260
So now again smallest is initialized as I.

93
00:04:12,290 --> 00:04:14,060
So smallest is equal to one.

94
00:04:14,060 --> 00:04:15,290
Now we have j.

95
00:04:15,290 --> 00:04:19,010
So j is going to move through the indexes 234 and five.

96
00:04:19,010 --> 00:04:19,490
All right.

97
00:04:19,490 --> 00:04:24,830
So then when when we do that initially J is going to point at index two we see the value two.

98
00:04:24,830 --> 00:04:26,870
And we will see that two is less than eight.

99
00:04:26,870 --> 00:04:29,330
So we will modify smallest to two right.

100
00:04:29,330 --> 00:04:32,480
So smallest will become two again J comes over here.

101
00:04:32,480 --> 00:04:34,130
Now six is not less than two.

102
00:04:34,160 --> 00:04:37,730
So J moves ahead J comes over here four is not less than two.

103
00:04:37,760 --> 00:04:40,610
So again J moves ahead five is not less than two.

104
00:04:40,610 --> 00:04:41,240
And that's it.

105
00:04:41,240 --> 00:04:42,860
So J has reached the last index.

106
00:04:42,860 --> 00:04:48,710
So therefore in this pass we will identify that the next smallest value is this two over here which

107
00:04:48,710 --> 00:04:49,790
is at index two.

108
00:04:49,790 --> 00:04:55,370
Now we are going to just swap the values at index I and at index smallest which is eight and two.

109
00:04:55,400 --> 00:04:57,380
So these are two are going to be swapped.

110
00:04:58,090 --> 00:05:01,450
All right, so we get two over here and eight over here.

111
00:05:01,660 --> 00:05:03,310
Now our array looks like this.

112
00:05:03,310 --> 00:05:06,790
So you can see we have identified the two smallest values.

113
00:05:06,790 --> 00:05:08,650
And they are in the beginning of the array.

114
00:05:08,680 --> 00:05:10,210
Now again we move I ahead.

115
00:05:10,210 --> 00:05:12,250
So I is going to point at index two.

116
00:05:12,250 --> 00:05:15,190
And now we are initializing smallest as two again.

117
00:05:15,190 --> 00:05:16,810
And then we will use j.

118
00:05:16,810 --> 00:05:19,270
We will iterate through this part of the array.

119
00:05:19,270 --> 00:05:22,360
And then you can see that the smallest value is going to be this one over here.

120
00:05:22,360 --> 00:05:22,600
Right.

121
00:05:22,600 --> 00:05:26,890
So we will identify that smallest is equal to four by doing the same thing.

122
00:05:26,890 --> 00:05:32,590
And then we are just going to swap the values at index I and at index smallest.

123
00:05:32,590 --> 00:05:34,390
So these two are going to be swapped.

124
00:05:34,390 --> 00:05:36,790
So we get four over here and eight over here.

125
00:05:36,790 --> 00:05:38,440
So this is how the array looks like.

126
00:05:38,440 --> 00:05:40,810
Now again I is going to be moved ahead.

127
00:05:40,810 --> 00:05:42,700
Now I is pointing at index three.

128
00:05:42,700 --> 00:05:44,650
So smallest is initialized to three.

129
00:05:44,650 --> 00:05:48,310
And then we are going to use j to iterate through these parts.

130
00:05:48,310 --> 00:05:51,460
And we find that the next smallest value is at index five.

131
00:05:51,460 --> 00:05:51,730
Right.

132
00:05:51,730 --> 00:05:55,450
So this value over here therefore we are just going to swap these two.

133
00:05:55,450 --> 00:05:59,500
So small smallest will be found to be equal to five which is this index over here.

134
00:05:59,500 --> 00:06:04,870
Now the values at index I and at index smallest which is six and five will be swapped.

135
00:06:04,870 --> 00:06:05,080
Right.

136
00:06:05,080 --> 00:06:06,370
So we will swap these two.

137
00:06:06,370 --> 00:06:09,130
So we get five over here and six over here.

138
00:06:09,130 --> 00:06:10,960
Now our array looks like this.

139
00:06:10,960 --> 00:06:13,690
So you can see this part of here over here is now sorted.

140
00:06:13,690 --> 00:06:14,020
Right.

141
00:06:14,020 --> 00:06:15,340
Again we move I ahead.

142
00:06:15,340 --> 00:06:17,770
So I is going to point at index four.

143
00:06:18,250 --> 00:06:20,560
Now J is going to point over here.

144
00:06:20,560 --> 00:06:22,720
Now we see that six is less than eight.

145
00:06:22,720 --> 00:06:25,840
So smallest is going to be modified from 4 to 5.

146
00:06:25,840 --> 00:06:27,880
So smallest will be equal to five.

147
00:06:27,880 --> 00:06:29,800
And then we will just swap these two values.

148
00:06:29,800 --> 00:06:32,080
So six comes over here and eight is over here.

149
00:06:32,080 --> 00:06:34,540
And you can see we have got the array sorted.

150
00:06:34,540 --> 00:06:36,790
So this is how the selection sort works.

151
00:06:36,790 --> 00:06:41,560
Now you can see when compared with bubble sort it does lesser number of swaps.

152
00:06:41,560 --> 00:06:45,700
So bubble sort swaps at every index every time it keeps swapping many times.

153
00:06:45,700 --> 00:06:51,190
But over here we are just I we, we are moving through the array, finding the next smallest and then

154
00:06:51,190 --> 00:06:51,970
swapping ones.

155
00:06:51,970 --> 00:06:53,830
So this is how selection sort works.

156
00:06:53,830 --> 00:06:58,210
Now let's take a quick look at the complexity analysis of this solution.

157
00:06:58,210 --> 00:07:03,250
The time complexity of the solution or the selection sort is going to be of the order of n square.

158
00:07:03,250 --> 00:07:06,550
And the space complexity is O of one, which is constant space.

159
00:07:06,550 --> 00:07:07,900
Again, this is straightforward.

160
00:07:07,900 --> 00:07:11,050
We have not used any extra or auxiliary space.

161
00:07:11,050 --> 00:07:13,690
So that's why the space complexity is O of one.

162
00:07:13,690 --> 00:07:17,440
Now let's try to understand why the time complexity is O of n square.

163
00:07:17,440 --> 00:07:20,110
Now for this let's make a table over here.

164
00:07:20,110 --> 00:07:23,170
So we have I and the number of comparisons.

165
00:07:23,170 --> 00:07:26,350
Now initially we have seen that I is going to point at index zero.

166
00:07:26,350 --> 00:07:29,020
And we have to make five comparisons.

167
00:07:29,020 --> 00:07:29,200
Right.

168
00:07:29,200 --> 00:07:33,580
Because J had to move from here then to here then to here, then to here and then to here.

169
00:07:33,580 --> 00:07:35,560
And in each instance we made comparisons.

170
00:07:35,560 --> 00:07:38,050
So that's one, two, three, four and five.

171
00:07:38,050 --> 00:07:41,350
So when I is equal to zero we made five comparisons.

172
00:07:41,770 --> 00:07:47,110
Later I moved to one and J moved from 2 to 3 to 4 to 5.

173
00:07:47,110 --> 00:07:49,540
So over here you can see that's four comparisons.

174
00:07:49,540 --> 00:07:52,660
So when I is equal to one we had to make four comparisons.

175
00:07:52,660 --> 00:07:56,980
And in this way when I is equal to two we will have to make three comparisons etc..

176
00:07:56,980 --> 00:08:01,630
Finally, when I is equal to five then we don't need to make any comparisons.

177
00:08:01,630 --> 00:08:06,730
So if we take the total number of comparisons that we have to make that we had to make, it's going

178
00:08:06,730 --> 00:08:10,180
to be one plus two plus three plus four plus five, right.

179
00:08:10,180 --> 00:08:15,730
And again, if we generalize this over here we have five because the total number of elements was six.

180
00:08:15,730 --> 00:08:18,430
So this five over here is actually n minus one.

181
00:08:18,430 --> 00:08:24,970
So we are actually adding from one till n -1 or 1 plus two plus three etc. up to n minus one.

182
00:08:24,970 --> 00:08:27,790
So this is the total number of operations that we had to do.

183
00:08:27,790 --> 00:08:33,190
Now this series over here is equal to n minus one into n divided by two.

184
00:08:33,220 --> 00:08:33,700
All right.

185
00:08:33,700 --> 00:08:36,790
And this simplifies to n square minus n by two.

186
00:08:36,820 --> 00:08:39,280
So you can see there is a n square term over here.

187
00:08:39,280 --> 00:08:43,420
And that's why the time complexity is going to be of the order of n square.

188
00:08:43,420 --> 00:08:45,730
Because this is the dominating uh factor.

189
00:08:45,730 --> 00:08:46,000
Right.

190
00:08:46,000 --> 00:08:48,970
So that's why the time complexity is of the order of n square.

191
00:08:48,970 --> 00:08:53,320
Now, if you don't know this, this is something that you should know if you take the numbers from one

192
00:08:53,320 --> 00:08:58,660
to x, for example, one plus two plus three etcetera up to x.

193
00:08:58,900 --> 00:09:04,630
In this case this sum over here is going to be equal to x into x plus one divided by two.

194
00:09:04,660 --> 00:09:06,280
So this is something that you should know.

195
00:09:06,280 --> 00:09:06,640
All right.

196
00:09:06,640 --> 00:09:09,700
So if you don't know it make don't know it make a note of it.

197
00:09:09,700 --> 00:09:12,250
Because it's going to be useful in many cases.

198
00:09:12,280 --> 00:09:14,980
Now for example let's try this out.

199
00:09:14,980 --> 00:09:17,830
So one plus two plus three up to five.

200
00:09:17,830 --> 00:09:18,250
All right.

201
00:09:18,250 --> 00:09:23,230
So this is going to be equal to five into five plus one which is six divided by two.

202
00:09:23,260 --> 00:09:25,360
So this simplifies to 15.

203
00:09:25,360 --> 00:09:29,200
Now if you add one plus two plus three plus four plus five you will get 15.

204
00:09:29,200 --> 00:09:29,560
All right.

205
00:09:29,560 --> 00:09:34,180
So in a similar manner over here instead of x I am just writing n minus one.

206
00:09:34,180 --> 00:09:39,310
So this is n minus one into n minus one plus one which is n itself divided by two.

207
00:09:39,340 --> 00:09:40,840
So that's how we are getting this over here.

208
00:09:40,840 --> 00:09:45,340
And this when you expand this bracket you get n square minus n by two.

209
00:09:45,340 --> 00:09:46,690
And then two is a constant.

210
00:09:46,690 --> 00:09:50,890
So we neglected and among n square and n n square is the bigger factor.

211
00:09:50,890 --> 00:09:52,270
So we can just neglect this.

212
00:09:52,270 --> 00:09:57,490
And that's why we can say the time complexity of this solution or the selection sort is of the order.

213
00:09:57,610 --> 00:09:58,570
Rough n square.